Feladat: N.160 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Bérczi Gergely ,  Gyenes Zoltán ,  Horváth Gábor ,  Kun Gábor ,  Lippner Gábor ,  Lukács László ,  Mecz Balázs ,  Végh A. László 
Füzet: 1998/október, 422. oldal  PDF file
Témakör(ök): Rekurzív sorozatok, Nehéz feladat
Hivatkozás(ok):Feladatok: 1998/január: N.160

Definiáljuk az (an) sorozatot a következőképpen: a0=a1=0, a2=1, an+3=an+1+1998an. Mutassuk meg, hogy tetszőleges pozitív egész n-re:
a2n-1=2anan+1+1998an-12.(4)


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.

Jelölje Gn azt az irányított gráfot, amelynek a csúcsai A0, A1, ..., An, az élei pedig: Ai-ből Ai+2-be megy egy él, Ai-ből Ai+3-ba pedig 1998 darab él megy, minden szóbajövő i esetére. Jelölje az A0An irányított utak számát bn.
Látható, hogy a2=b0=1, a3=b1=0, a4=b2=1. Legyen a továbbiakban n3. Ekkor An-be el lehet jutni (irányított út mentén) An-2-ből egyféleképpen, An-3-ból pedig 1998-féleképpen. Mivel minden A0An útnak érintenie kell An-2-t vagy An-3-at, így bn=bn-2+1998bn-3; tehát bn=an+2. Ezek szerint a b2n-3=2bn-1bn-2+1998bn-32 összefüggést kell igazolni.
Az A2n-3-ba vezető utak a következők lehetnek:
a) An-1-en keresztül menő;
b) An-2-n keresztül menő;
c) sem An-1-et, sem An-2-t nem érintő.

Nyilván minden út e három fajta közül pontosan az egyikbe tartozik. Az a), ill. b) típus nyilván bn-1bn-2, ill. bn-2bn-1 utat tartalmaz. Ha egy út c)-típusú, akkor át kell haladnia An-3-on és An-en is; az ilyen utak száma ezért bn-31998bn-3. Tehát b2n-3=bn-1bn-2+bn-2bn-1+bn-31998bn-3, ami éppen a feladat állítása.

 Kun Gábor (Bp., Piarista Gimn., 12. o.t.)
 
 Lukács László (Miskolc, Földes F. Gimn., 11. o.t.)