KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem B. 4129. (November 2008)

B. 4129. Sequence (an) is defined by the recursion a0=0, a1=1 and an=2an-1+an-2 for n>1. Prove that if 2^k\mid n, then 2^k\mid a_n.

(5 pont)

Deadline expired on 15 December 2008.


Sorry, the solution is available only in Hungarian. Google translation

Megoldás: Ha n=0, akkor az állítás nyilván igaz, így elegendő annyit megmutatni, hogy minden m pozitív egész számra 2a_m\mid a_{2m} teljesül. Ekkor ugyanis k szerinti teljes indukcióval könnyen megmutatható, hogy 2^ka_m\mid a_{2^km}, tehát n=2km esetén, lévén a sorozat elemei egész számok, 2^k\mid a_n valóban teljesül.

A sorozat képzési szabálya szerint 2am=am+1-am-1, ahonnan

a_{m+1}\equiv a_{m-1}\pmod{2a_m}.

Most i szerinti teljes indukcióval megmutatjuk, hogy minden 0\lei\lem esetén

a_{m+i}\equiv (-1)^{i+1}a_{m-i}\pmod{2a_m}

teljesül. Ez i=0 esetén magától értetődő, i=1 esetén pedig az imént láttuk be. Ha pedig 2\lei\lem és kisebb i értékek esetén az állítást már igazoltuk, akkor

a_{m+i}=2a_{m+i-1}+a_{m+i-2}\equiv 2\cdot(-1)^ia_{m-i+1}+(-1)^{i-1}a_{m-i+2}
\pmod{2a_m},

és itt a jobb oldalon tényleg (-1)i+1am-i=(-1)i+1(am-i+2-2am-i+1) áll. A kapott eredményt i=m esetén alkalmazva a_{2m}\equiv (-1)^{m+1}a_0=0 \pmod{2a_m} adódik, ami éppen azt jelenti, hogy 2a_m\mid a_{2m}.


Statistics:

59 students sent a solution.
5 points:Ágoston Tamás, Aujeszky Tamás, Bálint Dániel, Baranyai Zoltán, Beke Lilla, Blázsik Zoltán, Bodor Bertalan, Cséke Balázs, Éles András, Énekes Péter, Fekete Dorottya, Fonyó Dávid, Frankl Nóra, Gévay Gábor, Horowitz Gábor, Huszár Kristóf, Keresztfalvi Tibor, Kiss 902 Melinda Flóra, Kovács 729 Gergely, Kovács 888 Adrienn, Kovács 999 Noémi, Lelkes Ádám, Lovas Lia Izabella, Mester Márton, Mészáros András, Nagy 648 Donát, Orosz Ákos, Perjési Gábor, Ratku Antal, Réti Dávid, Somogyi Ákos, Strenner Péter, Szabó 928 Attila, Varga 171 László, Viharos Andor, Vuchetich Bálint, Wang Daqian, Weisz Ágoston, Weisz Gellért, Zsakó András.
4 points:11 students.
3 points:3 students.
2 points:2 students.
0 point:1 student.
Unfair, not evaluated:2 solutions.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley