Feladat: Gy.3097 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Babos Attila ,  Barát Anna ,  Bérczi Gergely ,  Csikvári András ,  Dedinszky Zsófia ,  Devecsery András ,  Dezső Balázs ,  Gyenes Zoltán ,  Hangya Balázs ,  Lázár Zsófia ,  Lippner Gábor ,  Naszódi Gergely ,  Nyul Gábor ,  Páles Csaba ,  Pap Júlia ,  Pogány Ádám ,  Szabadka Zoltán ,  Szabó Péter ,  Szűcs Gábor ,  Terék Zsolt ,  Terpai Tamás ,  Várady Gergő ,  Varga Tamás ,  Zábrádi Gergely ,  Zawadowski Ádám 
Füzet: 1997/szeptember, 346 - 347. oldal  PDF file
Témakör(ök): Számsorozatok, Természetes számok, Rekurzív eljárások, Fibonacci-sorozat, Gyakorlat
Hivatkozás(ok):Feladatok: 1996/december: Gy.3097

Jelölje an azt a természetes számot, ahányféleképpen az n felírható 1-esek, 3-asok és 4-esek összegeként. (A sorrend számít, pl. a4=4.) Bizonyítsuk be, hogy a1996 négyzetszám. (H)

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Könnyen kiszámolható, hogy a1=1, a2=1, a3=2, a4=4. Ha n>4-re a lehetséges összeg első tagja 1, akkor a többi tag an-1-féle lehet, ha az első tag 3, akkor a többi an-3-féle lehet, ha az első tag 4, akkor a többi an-4-féle lehet. Tehát an=an-1+an-3+an-4.
Ezzel a rekurziós képlettel tovább számolva kapjuk, hogy a5=6, a6=9, a7=15, a8=25, a9=40, a10=64, ...Az elemek között szabályosság fedezhető fel: az a sejtésünk, hogy a2n mindig négyzetszám lesz ‐ így tehát a1996 is. Ennél azonban többet is beláthatunk: az 12, 22, 32, 52, 82 ... sorozatban az alapok mindegyike az előző kettő összege. Az f1=1, f2=1, fn+2=fn+1+fn (n1) sorozat az úgynevezett Fibonacci-sorozat. Be fogjuk bizonyítani, hogy a2n=fn+12, és a2n+1=fn+1fn+2. Teljes indukciót használunk: n=1-re és 2-re az állítás igaz, és lássuk be, hogy (n+1)-re is igaz ez a két összefüggés. Ekkor

a2(n+1)=a2(n-1)+a2n-1+a2n+1=fn2+fnfn+1+fn+1fn+2==fn(fn+fn+1)+fn+1fn+2=fnfn+2+fn+1fn+2=fn+2(fn+fn+1)=fn+22,
és
a2n+3=a2n-1+a2n+a2n+2=fnfn+1+fn+12+fn+22=fn+1(fn+fn+1)+fn+22==fn+1fn+2+fn+22=fn+2(fn+1+fn+2)=fn+2fn+3,
tehát az állítás minden n-re igaz. Ezzel azt is bebizonyítottuk, hogy an minden páros n-re négyzetszám, így a1996 is az.