Cím: Néhány érdekesség a Fibonacci- és a Fibonacci-típusú sorozatokról
Szerző(k):  Énekes Béla ,  Kós Géza 
Füzet: 2000/december, 517 - 523. oldal  PDF file
Témakör(ök): Szakmai cikkek
Hivatkozás(ok):Feladatok: 2000/szeptember: A.244

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.

I. rész

 

A KöMaL 2000. szeptemberi számában tűztük ki a következő feladatot:
 
 
A. 244. Egy számsorozatot nevezzünk Fibonacci-típusúnak, ha a harmadiktól kezdve mindegyik eleme az előző kettő összege. Bizonyítsuk be, hogy a pozitív egész számok halmaza felbontható olyan Fibonacci-típusú végtelen sorozatok uniójára, amelyek közül semelyik kettőnek nincs közös eleme.
 

A cikk első részében közelebbről meg fogjuk vizsgálni a ,,Fibonacci-típusú'' sorozatokat. Eközben a Fibonacci-sorozat néhány érdekes tulajdonságára is fény derül. A második részben, amely a KöMaL következő számában fog megjelenni, több különböző megoldást mutatunk a feladatra.
Terjedelmi okokból nem bizonyítunk precízen minden egyes állítást; lesznek olyanok, amelyek igazolását feladat formájában az Olvasóra hagyjuk. Ez azonban nem fog meggátolni minket abban, hogy a feladatként kimondott állításokat is felhasználjuk más állítások igazolásához.
 
 
A Fibonacci-sorozat
 
 


A természetes számokból álló sorozatok között az egyik legismertebb és legérdekesebb a Fibonacci sorozat. A sorozat elemei, a Fibonacci számok a legváltozatosabb és legmeglepőbb helyeken fordulnak elő, bukkannak fel nem csak a matematikában, de a természetben is. Bár a Fibonacci-sorozatot szinte minden középiskolás ismeri, nem árt újra felírni a definícióját. Különösen azért, hogy a továbbiakban az elemeket egységesen jelöljük és számozzuk.
A sorozatot a következő rekurzióval definiáljuk:
F0=0;F1=1;Fn+1=Fn+Fn-1(n2).(1)

A rekurzióból könnyen kiszámolhatjuk az első néhány Fibonacci-számot: F2=1, F3=2, F4=3, F5=5, F6=8, F7=13, F8=21, F9=34, F10=55, ...
 
 
Fibonacci-típusú sorozatok
 
 

Egyelőre egyetlen Fibonacci-típusú sorozatot láttunk: magát a Fibonacci-sorozatot. Először tehát nézzük meg, hogyan készíthetünk további ilyen sorozatokat. Egy lehetséges módszer, hogy a már ismert Fibonacci-típusú sorozatokból próbálunk újabbakat készíteni.
 
1. lemma. Fibonacci-típusú sorozatot kapunk minden esetben, ha
*a) Egy Fibonacci-típusú sorozatnak elhagyjuk az első néhány elemét, vagy pedig olyan elemeket írunk elé, hogy a képzési szabály érvényes maradjon;
*b)Egy Fibonacci-típusú sorozat összes elemét megszorozzuk ugyanazzal a számmal;
*c)Néhány Fibonacci-típusú sorozat megfelelő elemeit összeadjuk.

 
 
1. feladat. Bizonyítsuk be az 1. lemmát.
 

Egy másik lehetőség, hogy az (1) rekurzióban más számokat választunk a sorozat első két elemének. A leghíresebb ilyen sorozat az úgynevezett Lucas-sorozat:
L0=2,L1=1,L2=3,Ln+1=Ln+Ln-1,
de az első két elem helyére nyilván tetszőleges valós számokat írhatunk.
 
1. definíció. Tetszőleges a, b valós számokra ,,az (a,b) paraméterű Fibonacci-típusú sorozatnak'' nevezzük azt a számsorozatot, amelyet a következő rekurzív képzési szabály definiál:
F0(a,b)=a;F1(a,b)=b;Fn+1(a,b)=Fn(a,b)+Fn-1(a,b)(n1).
 

Ezzel a jelöléssel Fibonacci eredeti sorozata Fn(0,1), a Lucas-sorozat pedig Fn(2,1).
Világos, hogy az 1. definícióban felírt sorozatok az összes Fibonacci-típusú sorozatot tartalmazzák, hiszen az első két elem egyértelműen meghatározza a többit. Ennek egy másik fontos következménye, hogy ha két Fibonacci-típusú sorozatról be akarjuk bizonyítani, hogy ugyanazok, akkor elég az első két elemről ellenőrizni, hogy megegyeznek.
Ha elkezdjük formálisan felírni az (Fn(a,b)) sorozat elemeit, érdekes dolgot vehetünk észre:
F2(a,b)=F1(a,b)+F0(a,b)=1a+1bF3(a,b)=F2(a,b)+F1(a,b)=1a+2bF4(a,b)=F3(a,b)+F2(a,b)=2a+3bF5(a,b)=F4(a,b)+F3(a,b)=3a+5bF6(a,b)=F5(a,b)+F4(a,b)=5a+8b
Ezekből már megsejthetjük a következő tételt:
 
1. tétel. a) A Fibonacci-sorozatból kiindulva, az 1. lemmában felsorolt lépésekkel bármelyik Fibonacci-típusú sorozatot előállíthatjuk.
b) Tetszőleges a, b valós számokra az (a,b) paraméterű Fibonacci-típusú sorozat elemei felírhatók a következő alakban:
Fn(a,b)=Fn-1a+Fnb(n1).(2)

 
Bizonyítás. Legyenek a és b tetszőleges valós számok. Ha a Fibonacci-sorozat elejére odaírjuk az 1-et, akkor az 1, 0, 1, 1, 2, 3, 5, 8, ... Fibonacci-típusú sorozatot kapjuk. Ha ennek a-szorosához hozzáadjuk a Fibonacci-sorozat b-szeresét, akkor a kapott sorozat az aFn-1+bFn sorozat lesz. Ennek 0. eleme a1+b0=a, 1. eleme a0+b1=b, vagyis a sorozat nem más, mint az (a,b) paraméterű Fibonacci-típusú sorozat. Az (Fn(a,b)) sorozatot tehát elő tudtuk állítani az 1. lemmában leírt lépésekkel, az előállítást formálisan a (2) képlet írja le.
 
 
Fibonacci-típusú mértani sorozatok
 
 

A Fibonacci-sorozat nem mértani sorozat. Ha kiszámítjuk a szomszédos Fibonacci-számok hányadosát, láthatjuk, hogy a hányadosok különbözők:
11=1;21=2;32=1,5;531,667;85=1,6;138=1,625;21131,615;34211,6190;55341,6176;...
Azt is láthatjuk azonban, hogy a hányadosok egyre közelebb vannak egy számhoz, amelynek tizedestört alakja 1,618-del kezdődik.
Ugyanezt az eredményt kapjuk sok más Fibonacci-típusú sorozat esetében. Például a Lucas-sorozatra
31=3;431,333;74=1,75;1171,571;18111,636;29181,611;47291,621;76471,617;123761,6184;...

A Fibonacci-típusú sorozatok tehát bizonyos értelemben hasonlítanak egy olyan mértani sorozatra, amelynek hányadosa ez a titokzatos q=1,618... szám.
A q szám pontos kiszámításához keressünk olyan mértani sorozatot, amelyik Fibonacci-típusú is. Legyen a sorozat első eleme a1, hányadosa q. Ekkor tetszőleges n-re
an+2=an+1+an,a1qn+1=a1qn+a1qn-1,
azaz
q2=q+1.(3)

Ennek az egyenletnek két irracionális valós gyöke van: q1=1+521,618034 és q2=1-52-0,618034. Tehát a keresett szám: q=1+52.
Érdekesség, hogy egy másik Fibonacci-típusú mértani sorozatot is találtunk; ennek hányadosa a negatív 1-52. A q2 hányadosú sorozatban egyre kisebb abszolút értékű számok szerepelnek, váltakozó előjellel.
Ezzel bebizonyítottuk a következő tételt:
 
2. tétel. Kétféle Fibonacci-típusú mértani sorozat létezik; ezeknek a hányadosa
q=1+52, illetve q2=1-52.
 

Azt még nem tisztáztuk, hogy a Fibonacci-sorozat milyen értelemben hasonlít erre a q hányadosú mértani sorozatra; erre később, a 3. tételben térünk majd vissza.
 
 
A Fibonacci-sorozat és a q=1+52 szám hatványai
 
 

Játsszunk most el egy kicsit a q számmal úgy, hogy csak a q2=q+1 azonosságot használjuk fel. A q magasabb hatványait felírhatjuk aq+b alakban:
q3=q2q=(q+1)q=q2+q=(q+1)+q=2q+1;q4=q3q=(2q+1)q=2q2+q=2(q+1)+q=3q+2;q5=q4q=(3q+2)q=3q2+2q=3(q+1)+2q=5q+3;q6=q5q=(5q+3)q=5q2+3q=5(q+1)+3q=8q+5;

 
2. lemma. Tetszőleges n pozitív egészre
qn=Fnq+Fn-1.(4)

 
1. bizonyítás. Mivel (4) mindkét oldalán Fibonacci-típusú sorozat áll, ezért elég az első két elemre ellenőrizni.
n=1:q=F1q+F0=q,n=2:q2=F2q+F1=q+1.

 
2. bizonyítás. Az 1, q, q2, ... sorozat nem más, mint az (1,q) paraméterű Fibonacci-típusú sorozat, ezért a 1. tétel szerint n1 esetén
qn=Fn(1,q)=Fn-11+Fnq.

 
2. feladat. Bizonyítsuk be a 2. lemmát teljes indukcióval is.
 

Most már bebizonyíthatjuk, hogy a szomszédos Fibonacci-számok hányadosa q-hoz tart, sőt ennél kicsit többet.
 
3. feladat. Bizonyítsuk be teljes indukcióval, hogy n1 esetén
13qn<Fn<12qn.

 
3. tétel. Tetszőleges n pozitív egészre
|Fn+1Fn-q|<12Fn2.

 
Bizonyítás. A 2. lemma akkor is igaz marad, ha a q helyére a q2 számot írjuk, tehát
Fn+1q2+Fn=q2n+1.(5)
Akár a ViŠte-képletekből, akár közvetlenül könnyen ellenőrizhető, hogy q2=-1q. Ezt beírva (5)-be és rendezve,
-Fn+1q+Fn=(-1)n+1qn+1,|Fn+1Fn-q|=|(-1)nqnFn|=1qnFn<12Fn2.
(Az utolsó lépésben a 3. feladat felső becslését használtuk fel.)
 

A 3. tétel nem csak annyit mond, hogy az Fn+1Fn értéke ,,körülbelül'' q; azt is állítja, hogy ez a becslés nagyon pontos: a hiba 12Fn2-nél kisebb.*

 
 
 
Hogyan készítsünk végtelen sok azonosságot a Fibonacci-számokkal?
 
 

A 2. lemma állítását felhasználhatjuk arra, hogy olyan azonosságokat gyártsunk, amelyekben a Fibonacci-számok szerepelnek. Ehhez először is szükség van a következő lemmára:
 
3. lemma. Ha egy valós számot fel lehet írni aq+b alakban alkalmas a, b egész számokkal, akkor ez a felírás egyértelmű. Más szóval, ha valamely a, b, c, d egész számokra aq+b=cq+d, akkor a=c és b=d.
 
Bizonyítás. Az egyenletet átrendezve (a-c)q=d-b. Mivel q irracionális, ez csak úgy lehetséges, ha d-b=0 és a-c=0.
 

Írjunk most fel egy tetszőleges azonosságot q hatványaival, például azt, hogy qn+k=qnqk, és helyettesítsük be a 2. lemmában látott kifejezéseket a hatványok helyére:
qn+k=qnqk,Fn+kq+Fn+k-1=(Fnq+Fn-1)(Fkq-Fk-1),Fn+kq+Fn+k-1=FnFkq2+(FnFk-1+Fn-1Fk)q+Fn-1Fk-1,Fn+kq+Fn+k-1=FnFk(q+1)+(FnFk-1+Fn-1Fk)q+Fn-1Fk-1,Fn+kq+Fn+k-1=(FnFk+FnFk-1+Fn-1Fk)q+(FnFk+Fn-1Fk-1),
amiből az egyértelműség miatt például
Fn+k-1=FnFk+Fn-1Fk-1.(6)

 
4. feladat. Bizonyítsuk be teljes indukcióval a (6) azonosságot.
 
 
A Fibonacci-típusú sorozatok explicit alakja
 
 

Most a Fibonacci-típusú sorozatokat egy explicit, rekurzió nélküli formában fogjuk felírni. Ehhez az 1. lemma lépéseit fogjuk alkalmazni, de nem a Fibonacci-sorozatra, hanem az 1, q, q2, ... és a 1, q2, q22, ...sorozatokra.
 
4. lemma. Tetszőleges a, b valós számokhoz léteznek olyan c, d valós számok, amelyekre a=c+d és b=cq+dq2.
 
Bizonyítás. A c és d kiszámításához csupán meg kell oldanunk a lineáris egyenletrendszert. Mint könnyen ellenőrizhető,
c=b-q2aq-q2ésd=qa-bq-q2.(7)

 
4. tétel. Tetszőleges a, b valós számokra az (a,b) paraméterű Fibonacci-típusú sorozat n-edik eleme felírható a következő alakban:
Fn(a,b)=cqn+dq2n,(8)
ahol c=b-q2aq-q2 és d=qa-bq-q2.

 
Bizonyítás. A (8) mindkét oldalán Fibonacci-típusú sorozat áll. Az egyenlőség az n=0 és n=1 esetekben a 4. lemma szerint teljesül.
 

A Fibonacci-sorozat paraméterei (0,1). Egy kis számolással kapjuk, hogy ezekre a számokra c=15 és d=-15. Ezzel máris bebizonyítottuk a Fibonacci-sorozat explicit felírását:
 
5. tétel. Tetszőleges n nem-negatív egész számra
Fn=qn-q2n5=(1+52)n-(1-52)n5.

 
5. feladat. Írjuk fel explicit alakban az n-edik Lucas-számot.
 
6. feladat. Az 1. tétel szerint, ha a Fibonacci-sorozatból indulunk ki, akkor az 1. lemma lépéseivel az összes Fibonacci-típusú sorozatot előállíthatjuk, nincs szükség több sorozatra. A 4. tételben miért nem volt elég csak az egyik sorozat? Magyarázzuk meg!
 

A Fibonacci-számok és Fibonacci-típusú sorozatok explicit felírásának ismeretében nagyon sok azonosság bizonyítása egyszerűvé válik: csupán be kell helyettesítenünk az explicit képletet a bizonyítandó azonosságba. A számelméleti és kombinatorikus tulajdonságok bizonyításában, így az A. 244. feladat megoldásában azonban további ötletekre van szükség.
Énekes Béla, Kós Géza


*Ismeretes, hogy tetszőleges α irracionális számhoz végtelen sok olyan pozitív egész P, Q számpár létezik, amelyre |PQ-α|<12Q2. Akik erről a témáról többet szeretnének tudni, azoknak ajánljuk, hogy olvassák el Gyarmati Edit‐Turán Pál: Számelmélet c. jegyzetének Diofantikus approximáció c. fejezetét vagy Erdős Pál‐Surányi János: Válogatott fejezetek a számelméletből c. könyvének Racionális és irracionális számok. Számok megközelítése racionális számmal. (diofantoszi approcimáció) c. fejezetét.