Feladat: F.2242 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Danyi Pál 
Füzet: 1980/október, 63. oldal  PDF file
Témakör(ök): Rekurzív eljárások, Természetes számok, Feladat
Hivatkozás(ok):Feladatok: 1980/február: F.2242

Legyen xn azon n jegyű, csak 0, 1, 2 számjegyeket tartalmazó számoknak a száma, amelyekben bármely két szomszédos számjegy legfeljebb 1-gyel tér el egymástól. Igazoljuk, hogy tetszőleges n2-re xn+1=2xn+xn-1.

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.

Minden n+1 jegyű szám egyértelműen előáll úgy, hogy egy n jegyű végére írunk egy számjegyet. Legyen an a 0-ra, bn az 1-re, cn a 2-re végződő, a feltételeknek megfelelő n jegyű számok száma. Ekkor xn=an+bn+cn. Ha egy, a feltételeknek megfelelő számban az n+1-edik jegy 0, ez előtt csak 0 vagy 1 állhat, tehát

an+1=an+bn.(1)
Ha az (n+1)-edik jegy 1, ezt 0, 1 és 2 egyaránt megelőzheti, tehát bn+1=an+bn+cn=xn. Ezt az összefüggést még egyszer felhasználva bn=xn-1, azaz
bn+1=an+xn-1+cn.(2)
Végül 2 előtt csak 1 vagy 2 állhat, tehát
cn+1=bn+cn.(3)
Az (1), (2), (3) összegeként kapott összefüggés épp a bizonyítandó állítást adja:
xn+1=2(an+bn+cn)+xn-1=2xn+xn-1.

 (K.M)
 
 Danyi Pál (Pécs, Nagy Lajos Gimn., I. o. t.)