Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

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 December 15, 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 solutionss.

Problems in Mathematics of KöMaL, November 2008