Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 4129. feladat (2008. november)

B. 4129. Az (an) sorozatot a következő rekurzióval definiáljuk: a0=0, a1=1, n>1 esetén pedig an=2an-1+an-2. Igazoljuk, hogy ha 2^k\mid n, akkor 2^k\mid a_n.

(5 pont)

A beküldési határidő 2008. december 15-én LEJÁRT.


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}.


Statisztika:

59 dolgozat érkezett.
5 pontot kapott:Á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 pontot kapott:11 versenyző.
3 pontot kapott:3 versenyző.
2 pontot kapott:2 versenyző.
0 pontot kapott:1 versenyző.
Nem versenyszerű:2 dolgozat.

A KöMaL 2008. novemberi matematika feladatai