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 -nel a keresett számot. Megmutatjuk, hogy esetén . Soroljuk a sorozatokat három osztályba: 1. A nem -re végződő sorozatok száma , mert ezekre pontosan annak kell teljesülni, hogy , és minden tag az indexével azonos paritású. 2. Az a sorozat, amelynek utolsó tagja és nem tartalmaz -nél kisebb elemet. Ilyen pontosan egy van: páratlan esetén az egy darab -esből álló, páros esetén pedig az , sorozat. 3. Azok a sorozatok, amelyek utolsó tagja és tartalmaznak -nél kisebb elemet. Ezeket úgy kapjuk, hogy veszünk egy -nél nem nagyobb elemekből álló sorozatot (az ilyenek száma ); ha ennek legnagyobb eleme -nel azonos paritású, akkor a sorozathoz hozzátesszük az és számokat, ha pedig az utolsó elem -nel ellentétes paritású, akkor az számot (minden esetben csak egyféleképpen lehet a sorozatot folytatni). A háromféle sorozatból összesen darab van, a rekurziót igazoltuk. Legyen az -edik Fibonacci-szám . Teljes indukcióval igazoljuk, hogy . Ha , akkor sorozat van: az egyetlen -esből álló, tehát . Ha , akkor az és az sorozatokra teljesül a feltétel, tehát . Az állítás tehát teljesül -re és -re. Legyen és tegyük fel, hogy teljesül -re és -re. Ekkor a bizonyított rekurzió és a Fibonacci-sorozat definíciója alapján | |
vagyis az állítás -ra is igaz. Tehát a kérdéses sorozatok száma .
Megjegyzés. Ismeretes, hogy Ennek felhasználásával explicit képletet is nyerhetünk -re:
| |
Tichler Krisztián (Fazekas M. Főv. Gyak. Gimn., IV. o. t.) |