Feladat: F.2916 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Csörnyei Marianna ,  Dőtsch András ,  Marx Gábor ,  Tichler Krisztián ,  Waldhauser Tamás 
Füzet: 1993/március, 116 - 117. oldal  PDF file
Témakör(ök): Fibonacci-sorozat, Számsorozatok, Teljes indukció módszere, Rekurzív sorozatok, Feladat
Hivatkozás(ok):Feladatok: 1992/szeptember: F.2916

Legyen n rögzített pozitív egész. Hány olyan 1a1<a2<...<akn sorozat van, amelyben a páratlan indexű tagok páratlan, a páros indexűek páros egész számok?

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öljük An-nel a keresett számot. Megmutatjuk, hogy n3 esetén An=An-1+An-2+1.
Soroljuk a sorozatokat három osztályba:
1. A nem n-re végződő sorozatok száma An-1, mert ezekre pontosan annak kell teljesülni, hogy 1a1<a2<...<akn-1, és minden tag az indexével azonos paritású.
2. Az a sorozat, amelynek utolsó tagja n és nem tartalmaz (n-1)-nél kisebb elemet. Ilyen pontosan egy van: páratlan n esetén az egy darab n-esből álló, páros n esetén pedig az (n-1), n sorozat.
3. Azok a sorozatok, amelyek utolsó tagja n és tartalmaznak (n-1)-nél kisebb elemet. Ezeket úgy kapjuk, hogy veszünk egy (n-2)-nél nem nagyobb elemekből álló sorozatot (az ilyenek száma An-2); ha ennek legnagyobb eleme n-nel azonos paritású, akkor a sorozathoz hozzátesszük az (n-1) és n számokat, ha pedig az utolsó elem n-nel ellentétes paritású, akkor az n számot (minden esetben csak egyféleképpen lehet a sorozatot folytatni).
A háromféle sorozatból összesen An-1+An-2+1 darab van, a rekurziót igazoltuk. Legyen fn az n-edik Fibonacci-szám (f0=0,f1=1,fn+1=fn+fn-1). Teljes indukcióval igazoljuk, hogy An=fn+2-1.
Ha n=1, akkor 1 sorozat van: az egyetlen 1-esből álló, tehát A1=1=f3-1.
Ha n=2, akkor az (1) és az (1,2) sorozatokra teljesül a feltétel, tehát A2=2=f4-1.
Az állítás tehát teljesül n=1-re és n=2-re. Legyen k3 és tegyük fel, hogy teljesül n=k-1-re és n=k-2-re. Ekkor a bizonyított rekurzió és a Fibonacci-sorozat definíciója alapján

Ak=Ak-1+Ak-2+1=(fk+1-1)+(fk-1)+1=(fk+1+fk)-1=fk+2-1,

vagyis az állítás n=k-ra is igaz.
Tehát a kérdéses sorozatok száma fn+2-1.
 
Megjegyzés. Ismeretes, hogy
fn=(1+52)n-(1-52)n5.
Ennek felhasználásával explicit képletet is nyerhetünk An-re:
An=(1+52)n+2-(1-52)n+25-1.

 

 Tichler Krisztián (Fazekas M. Főv. Gyak. Gimn., IV. o. t.)