A B. 4129. feladat (2008. november)

B. 4129. Az (a_n) sorozatot a következő rekurzióval definiáljuk: a₀=0, a₁=1, n>1 esetén pedig a_n=2a_n-1+a_n-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=2^km 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 2a_m=a_m+1-a_m-1, ahonnan

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

Most i szerinti teljes indukcióval megmutatjuk, hogy minden 0 $\le$ i $\le$ m 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 $\le$ i $\le$ m é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)ⁱ⁺¹a_m-i=(-1)ⁱ⁺¹(a_m-i+2-2a_m-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

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.

Már regisztráltál?
Új vendég vagy?