Fibonacci-számok

A Fibonacci-számok (ejtsd: fibonaccsi) a matematikában az egyik legismertebb másodrendben rekurzív sorozat elemei. A nulladik eleme 0, az első eleme 1, a további elemeket az előző kettő összegeként kapjuk. Képletben:

Egymás mellé helyezett négyzetek, melyek élhosszúságai a Fibonacci-számsorozat tagjait alkotják

$F_{n}={\begin{cases}0,&{\mbox{ha }}n=0;\\1,&{\mbox{ha }}n=1;\\F_{n-1}+F_{n-2},&{\mbox{ha }}n\geq 2.\end{cases}}$

A Fibonacci-számok végtelen, növekvő sorozatot alkotnak; ennek első néhány eleme a nulladiktól kezdve 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. Fibonacci-számok több nagy listája is szabadon letölthető az internetről.

Eredet

A sorozatot először 1150-ben írta le két indiai matematikus, Gopala és Hemacsandra, akik a szanszkrit költészet elméleti kérdéseit vizsgálva ütköztek egy összegre bontási problémába (hányféleképpen lehet rövid és hosszú szótagokkal kitölteni egy adott időtartamot, ha egy hosszú szótag két rövidnek felel meg?). Nyugaton tőlük függetlenül találta meg 1202-ben Fibonacci, aki Liber Abaci (Könyv az abakuszról) című művében egy képzeletbeli nyúlcsalád növekedését adta fel gyakorlófeladatként: hány pár nyúl lesz n hónap múlva, ha feltételezzük, hogy

• az első hónapban csak egyetlen újszülött nyúlpár van;
• az újszülött nyúlpárok két hónap alatt válnak termékennyé;
• minden termékeny nyúlpár minden hónapban egy újabb párt szül;
• és a nyulak örökké élnek?

Kepler 1611-es De nive sexangula (A hatszögletű hópehelyről) című könyvében újra felfedezte, és különféle természeti jelenségekkel hozta kapcsolatba.

A ma használt elnevezést E. Lucastól kapta.

Binet-formula

A szomszédos Fibonacci-számok aránya ($F_{n+1}/F_{n}\,$) $\phi \,$-hez, az aranymetszés értékéhez tart:

$x\,$	$=\lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}$
	$=\lim _{n\to \infty }{\frac {F_{n}+F_{n-1}}{F_{n}}}$
	$=1+\lim _{n\to \infty }{\frac {F_{n-1}}{F_{n}}}$
	$=1+{\frac {1}{\lim _{n\to \infty }{\frac {F_{n}}{F_{n-1}}}}}$
	$=1+{\frac {1}{x}}$

azaz

$x^{2}=x+1\,$,

ennek a másodfokú egyenletnek pedig éppen $\phi \,$ és $1-\phi \,$ a megoldásai.

(Valójában ennél több is elmondható: az $F_{n+1}/F_{n}\,$ törtek éppen a $\phi \,$ lánctörtbe fejtésével kapott közelítő törtek.)

Az egyenlet mindkét oldalát $x^{n}$-nel beszorozva a

$x^{n+2}=x^{n+1}+x^{n}\,$

egyenlőséget kapjuk.

Ez azt jelenti, hogy a $n\mapsto \phi ^{n}$ és a $n\mapsto (1-\phi )^{n}$ sorozatok (és minden lineáris kombinációjuk) kielégítik a Fibonacci-rekurziót.

Az együtthatók megfelelő megválasztásával elérhetjük, hogy a helyes $F_{0}=0\,$ és $F_{1}=1\,$ értékeket kapjuk:

$F_{n}={\phi ^{n} \over {\sqrt {5}}}-{(1-\phi )^{n} \over {\sqrt {5}}}$

Az így kapott

$F_{n}={(1+{\sqrt {5}})^{n}-(1-{\sqrt {5}})^{n} \over {\sqrt {5}}\cdot 2^{n}}$

képlet a Fibonacci-számok zárt alakja, ezt nevezzük Binet-formulának.

Ugyanezt a képletet kapjuk a generátorfüggvények módszerével is.

Ha n tart a végtelenhez, a második tag nullához konvergál, azaz a Fibonacci-számok a $\phi ^{n}/{\sqrt {5}}$ sorozathoz tartanak, ebből adódik az arányuk konvergenciája. Mi több, a második tag már kezdetben is olyan kicsi, hogy a Fibonacci-számokat úgy is megkaphatjuk, hogy csak az első tagot számoljuk ki, és kerekítünk a legközelebbi egészre.

A Fibonacci-sorozat leírható lineáris rekurziók kétdimenziós rendszerével:

${F_{k+2} \choose F_{k+1}}={\begin{pmatrix}1&1\\1&0\end{pmatrix}}{F_{k+1} \choose F_{k}}$

vagy

${\vec {F}}_{k+1}=A{\vec {F}}_{k}$

Az A mátrix sajátértékei $\phi \,$ és $(1-\phi )\,$, a sajátvektorok pedig ${\phi \choose 1}$ és ${1 \choose -\phi }$.

Általánosítások

A Fibonacci-sorozat kifejezést általánosabb értelemben minden olyan g sorozatra alkalmazzuk, ami a $g_{n+2}=g_{n}+g_{n+1}$ rekurzív képlettel adható meg. Belátható, hogy minden ilyen sorozat átírható $g_{n}=aF_{n}+bF_{n+1}$ alakba, más szóval a Fibonacci-sorozatok egy vektorteret alkotnak az $F_{n}$ és $F_{n+1}$ sorozatokkal mint bázissal.

A Fibonacci-sorozatok további általánosítása a Lucas-sorozatok.

Egy másfajta általánosítás a Fibonacci-polinomok.

Lucas-számok

Az $L_{0}=2$, $L_{1}=1$, $L_{n+2}=L_{n}+L_{n+1}$ Fibonacci-sorozat elemeit Lucas-számoknak nevezzük. Először Euler írta le őket 1748-ban, az Introductio in Analysin Infinitorum c. művében. Jelentőségük, hogy az aranymetszést n-edik hatványra emelve az eredmény ${\frac {L_{n}+F_{n}{\sqrt {5}}}{2}}$ lesz.

Néhány összefüggés a Fibonacci- és a Lucas-számok között:

$L_{n}=F_{n-1}+F_{n+1}\$

$F_{n}={\begin{matrix}{\frac {1}{5}}\end{matrix}}(L_{n-1}+L_{n+1})$.

$F_{n+1}={\begin{matrix}{\frac {1}{2}}\end{matrix}}(F_{n}+L_{n})$.

$F_{2n}=F_{n}L_{n}\$

$F_{m+n}={\begin{matrix}{\frac {1}{2}}\end{matrix}}(F_{m}L_{n}+F_{n}L_{m})$.

$F_{m-n}={\begin{matrix}{\frac {1}{2}}\end{matrix}}(-1)^{n}(F_{m}L_{n}-F_{n}L_{m})$.

$\lim _{n\to \infty }{\frac {L_{n}+F_{n}}{L_{n}-F_{n}}}=(1+\phi )=\phi ^{2}$

Polibonacci-számok

A Tribonacci-számokat a Fibonacci-számokhoz hasonlóan számítjuk, de kettő helyett három korábbi elemet adunk össze. (Az első néhány elem: 1, 1, 2, 4, 7, 13, 24, 44, 81, 149…) OEIS számuk A000073. Hasonlóan definiáljuk a tetranacci, pentanacci stb. számokat, de a kutatók nem tartják őket különösebben érdekesnek.

Kiterjesztés a negatív számokra

Ha a számok generálásához használt képletet a sorozat korábbi indexeinek előállításához használjuk, akkor megkapjuk a negatív Fibonacci-számokat, azaz a „negafibonacci” sorozatot.

$F_{-n}=(-1)^{n+1}F_{n}.$

F−8

F−7

F−6

F−5

F−4

F−3

F−2

F−1

F0

F1

F2

F3

F4

F5

F6

F7

F8

−21

13

−8

5

−3

2

−1

1

0

1

1

2

3

5

8

13

21

Kiterjesztés a valós számokra

A Binet-formulából kiindulva a Fibonacci-számok kiterjeszthetőek sorozatból valós függvénnyé:

$F_{\nu }={\frac {1}{\sqrt {5}}}\left(\left({\frac {1+{\sqrt {5}}}{2}}\right)^{\nu }-\left({\frac {2}{1+{\sqrt {5}}}}\right)^{\nu }\cos(\nu \pi )\right)$

A Fibonacci-számok valós számokon értelmezett függvénye

Tulajdonságai

Az egyetlen Fibonacci-szám, ami egyben négyzetszám is (a 0-t és az 1-et kivéve) a 144. 1982-ben igazolta Pethő Attila, hogy csak véges sok Fibonacci-szám teljes hatvány. Legújabban Y. Bugeaud, M. Mignotte és S. Siksek bebizonyította, hogy csak 8 és 144 teljes hatványok.

$F_{10^{n}}$ számjegyeinek száma éppen ${\frac {1}{{\rm {arcsh}}\,2\log 10}}$ tizedestört alakjának első n számjegye.

$F_{n}$ számjegyeinek száma éppen $n*lg(\phi )-lg(5)/2+1$ egészrésze, ha $n>1$ és $\phi =1,618...$ az aranymetszés értéke – mivel a Fibonacci-számok a $\phi ^{n}/{\sqrt {5}}$ sorozathoz tartanak.

Azonosságok

• $\sum _{i=0}^{n}F_{i}=F_{n+2}-1$
• $\sum _{i=0}^{n}iF_{i}=nF_{n+2}-F_{n+3}+2$
• $\sum _{i=0}^{n}F_{i}^{2}=F_{n}F_{n+1}$
• $F_{2n}=F_{n+1}^{2}-F_{n-1}^{2}$
• $F_{2n+1}=F_{n}^{2}+F_{n+1}^{2}$
• $F_{n+1}F_{n-1}-F_{n}^{2}=(-1)^{n}$ (Cassini-azonosság, a korábbi mátrixazonosságból a két oldal determinánsát véve nyerhető.) Általánosabb formája: $F_{n}^{2}-F_{n+r}F_{n-r}=(-1)^{n-r}F_{r}^{2}$ (Catalan-azonosság).
• $F_{m}F_{n+1}-F_{m+1}F_{n}=(-1)^{n}F_{n-m}\,$ (d'Ocagne-azonosság)
• $F_{m}F_{n+1}+F_{m-1}F_{n}=F_{n+m}\,$, amiből adódik, hogy $F_{k}|F_{nk}\,$. Ennél több is igaz: egy tetszőleges k-ra $k|(F-m)\wedge k|F_{n}\Leftrightarrow k|F_{(m,n)}\,$, továbbá $(F_{m},F_{n})=F_{(m,n)}\,$.
• Annak az n×n-es mátrixnak, aminek a főátlójába 1-et, a főátló fölötti és alatti mezőkbe pedig i-t írtunk, a determinánsa éppen $F_{n+1}$.
• Összefüggés a Csebisev-polinomokkal: $F_{n}=i^{n-1}U_{n-1}(-{\begin{matrix}{\frac {1}{2}}\end{matrix}}-i)$

Generátorfüggvény

A Fibonacci-sorozat generátorfüggvénye, az $s(x)=\sum _{n=1}^{\infty }F_{n}x^{n}$ hatványsor $|x|<1/\phi \,$ esetén az alábbi zárt alakba írható:

$s(x)={\frac {x}{1-x-x^{2}}}$.

Ebből $x={\frac {1}{10}}$ mellett adódik, hogy $\sum _{n=1}^{\infty }{\frac {F_{n}}{10^{n+1}}}={\frac {1}{89}}$.

Reciprokok összege

A Fibonacci-számok reciprokainak összegéből képzett sor konvergens:

$\sum _{n=1}^{\infty }F_{n}^{-1}=3,359885\dots$

(OEIS: A079586)

Erdős Pál vetette fel a kérdést, hogy irracionális-e ez a szám, és R. André-Jeannin bizonyította be 1989-ben, hogy az. Zárt képletet nem ismerünk rá.

Repfigitek

A repfigitek (repetitive Fibonacci-like digit, ismétlődő Fibonacci-szerű számjegy) vagy Keith-számok olyan számok, amiknek a számjegyeiből egy lineáris rekurzív sorozatot alkotva a sorozat tartalmazza magát a számot. A kétjegyű repfigitek (ezeknél a lin. rek. sorozat Fibonacci-sorozat): 14, 19, 28, 47, 61, 75.

(OEIS: A007629)

Fibonacci-számok kiszámítása

Rekurzív eljáráshívással

A rekurzív implementáció a legegyszerűbb, de közvetlenül nem alkalmas nagy Fibonacci-számok kiszámítására, mert a korábbi Fibonacci-számokat sokszor ki kell számítani hozzá, amitől a futásidő exponenciálissá válik, mint például az alábbi Perl illetve Java implementációkban:

# Exponenciális futásidejű rekurzív eljárás
# a Fibonacci-számok kiszámítására.
sub fibonacci {
    my $n = shift;
    if ( (0 == $n) || (1 == $n) ) {
        return $n;
    } else {
        return &fibonacci($n-1) + &fibonacci($n-2);
    }
}

/**
 * Exponenciális futásidejű rekurzív eljárás
 * a Fibonacci-számok kiszámítására.
 */
public int fibonacci(int n) {
    if ( (0 == n) || (1 == n) ) {
        return n;
    } else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

(Nem exponenciális a futásidő, ha a használt programnyelv „megjegyzi” az egyszer már kiszámított értékeket – ez a helyzet például bizonyos funkcionális nyelveknél.)

Ciklussal

Lineáris futásidő érhető el két változó használatával, amelyek kezdetben 0 és 1 értékeket kapnak, majd az elsőt minden lépésben felülírjuk a másodikkal, a másodikat pedig a kettő összegével. Ezt szemlélteti az alábbi Perl és Java implementáció:

# Lineáris futásidejű eljárás ciklussal
# a Fibonacci-számok kiszámítására.
sub fibonacci {
    my $n = shift;
    ($F, $prev) = (0, 1);
    for ($i = 0; $i < $n ; ++$i) {
        ( $F, $prev ) = ( $F + $prev, $F );
    }
    return $F;
}

/**
 * Lineáris futásidejű eljárás ciklussal
 * a Fibonacci-számok kiszámítására.
 */
public int fibonacci(int n) {
    int a = 0, b = 1, x = 0;
    while (x++ < n) 
    {
        b += a;
        a = b-a;
    }
    return a;
}

public int fibonacci(int n) {
    int F = 0;
    int prev = 1;
    int next;
    for (int i = 0; i < n ; ++i) {
        next = F + prev;
        prev = F;
        F = next;
    }
    return F;
}

Gyors hatványozással

Nagy $n$-re ${\mathcal {O}}(\log n)$ szorzással megkaphatjuk, ha az alábbi képletből számoljuk gyors hatványozással:

${\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}={\begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}}$

C++ nyelven történő implementációja:

//
// 2x2-es mátrix megvalósítása
// [a b]
// [c d]
// alakban.
//
struct Matrix {
    int a,b,c,d;
    Matrix operator* (const Matrix& m) const {
        return {(a*m.a+b*m.c), (a*m.b+b*m.d), (c*m.a+d*m.c), (c*m.b+d*m.d)};
    }
};

//
// Gyorshatványozás
//
Matrix fastpow(Matrix alap, int kitevo)
{
  if(kitevo==0) return {1,0,0,1};
  if(kitevo==1) return alap;
  
  Matrix fele=fastpow(alap,kitevo/2);
  Matrix hatvany=fele*fele;
  
  if(kitevo%2) hatvany=hatvany*alap;
  
  return hatvany;
}

//
// F(n) megadása, O(log n) művelettel
//
int fibonacci(int n)
{
	return fastpow({1,1,1,0}, n).b;
}

Binet-formulával

A Binet-formula használata konstans futásidejű megoldást eredményez, de mégsem célszerű, mert a lebegőpontos számábrázolás általában nem elég pontos hozzá, és a felgyülemlő kerekítési hibák miatt téves eredmény adódhat.

Diofantikus reprezentációval

Megmutatható, hogy a Fibonacci-számok halmaza megegyezik az alábbi kétváltozós ötödfokú polinom pozitív értékeivel:

$p(a,b)=2a^{4}b+a^{3}b^{2}-2a^{2}b^{3}-a^{5}-ab^{4}+2a$

ahol a és b természetes számok.

Ennek a ténynek a gyakorlati jelentősége csekély, hiszen már kis Fibonacci-számok előállításához is nagyon nagy számokkal kell számolni.

Alkalmazások

A Fibonacci-számoknak nagy jelentőségük van az euklideszi algoritmus futásidejének elemzésében: az algoritmus akkor a leglassabb, ha két szomszédos Fibonacci-szám legnagyobb közös osztóját kell kiszámolni.

Matyijaszevics kimutatta, hogy a Fibonacci-számok diofantoszi halmazt alkotnak, és ebből kiindulva válaszolta meg Hilbert tizedik problémáját.

A Pascal-háromszögben bizonyos átlók mentén összegezve a számokat Fibonacci-számokat kapunk.

Egy n hosszú szakaszt $F_{n+1}$-féleképpen lehet kirakni 1 és 2 hosszú szakaszokból.

Egy 2×n-es sakktáblát 2×1-es dominókkal $F_{n+1}$-féleképpen lehet lefedni (Dickau).

Az 1, 2, … n számokból $F_{n+2}$-féleképp lehet kiválasztani egy részhalmazt úgy, hogy ne kerüljenek bele szomszédos számok (1-et és n-t nem szomszédosnak tekintve).

Azoknak a bitsorozatoknak a száma, amikben nincs két egymást követő 0, $F_{n+2}$; annak az esélye, hogy n egymást követő pénzfeldobás során nem kapunk kétszer egymás után fejet, $F_{n+2}/2^{n}$.

A zenében néha hangolásra használják, máskor időtartamok arányainak meghatározására. Egy példa erre Bartók Béla Zene húros hangszerekre, ütőkre és cselesztára című műve.

Minden pozitív egész szám felírható különböző Fibonacci-számok összegeként; ha a Fibonacci-számok között nem lehet két egymást követő, akkor a felírás egyértelmű. Ez a Zeckendorf-tétel, maga a felírás pedig Zeckendorf-reprezentáció vagy Fibonacci-számrendszer néven ismeretes.

A mérföld és a kilométer közötti váltószám (1,609) közel van az aranymetszéshez, ezért a kettő közötti átváltás közelíthető egy bitenkénti eltolás művelettel a Fibonacci-számrendszerben.

A Fibonacci-spirál

Fibonacci-spirálok

A Fibonacci-spirál egy olyan logaritmikus spirál, ami egy negyedfordulat alatt nő a $\phi \,$-szeresére (azaz egy $c\,\phi ^{2/\pi }\,$ egyenletű spirál). Jól közelíthető az arany téglalap segítségével.

A Fibonacci-spirálon egyenlő távolságra pontokat elhelyezve azok „spirálkarokká” állnak össze, és ezen karok száma Fibonacci-szám lesz.

A Fibonacci-spirál mentén elhelyezett gömbök optimális elrendezést adnak abban az értelemben, hogy nagyon sok gömböt elhelyezve is azok egyenletesen oszlanak el.

Fibonacci-spirálok a napraforgó virágjában

Fibonacci-számok a természetben

A virágszirmok száma gyakran Fibonacci-szám: például a liliomnak, a nősziromnak és a hármassziromnak három; a haranglábnak, a boglárkának, a larkspurnak és a vadrózsának öt; a szarkalábnak, a vérpipacsnak és a pillangóvirágnak nyolc; a jakabnapi aggófűnek, a hamvaskának és a körömvirágnak 13; az őszirózsának, a borzas kúpvirágnak és a cikóriának 21; a fodroslevelű margitvirágnak, az útilapunak és egyes százszorszépeknek 34; más százszorszép-fajoknak pedig 55 vagy 89 szirma van.

Fibonacci-spirálba rendeződnek például a fenyőtoboz és az ananász pikkelyei, a napraforgó magjai, a málna szemei, a karfiol rózsái és egyes kaktuszok tüskéi. A nautiluszok háza is hasonlít a Fibonacci-spirálhoz, de nem egy negyed, hanem egy teljes kör alatt nő meg a sugár $\phi \,$-szeresére.

Nautilusz

A növények szárán az egymást követő levelek elfordulása (a phyllotaxis) többnyire (egyes becslések szerint 90%-ban) $F_{n}/F_{n+2}$ teljeskör (például szilfa és hárs esetén 1/2, bükknél, mogyorónál és szedernél 1/3, tölgynél, almánál, cseresznyénél és meggynél 2/5, nyárnál, rózsánál és baracknál 3/8, fűznél és mandulánál 5/13). Ezek az arányok éppen a $\phi ^{-2}\,$ lánctörtbe fejtésekor kapott közelítő törtek ($\phi \,$ az aranymetszés).

Przemyslaw Prusinkiewicz szerint ezen jelenségek egy része megmagyarázható szabad csoportok bizonyos algebrai megkötéseinek kifejeződéseként, konkrétabban bizonyos Lindenmayer-nyelvtanokként. A fraktálgeometriában a Fuchs-csoportok és a Klein-csoportok tanulmányozása közben találkozhatunk Fibonacci-számokkal.

Egy méh n-generációs őseinek a száma az n-edik Fibonacci-szám.

Fibonacci-számok az irodalomban

A Fibonacci-sorozatnak fontos szerepe van Dan Brown bestsellerében, A da Vinci-kódban és Darren Aronofsky filmjében, a π-ben. Esterházy Péter: Harminchárom változat Haydn-koponyára. (Színdarab, 2009.)

Fibonacci-számok szerepe Bartók zenéjében

Lendvai Ernő magyar zenetörténész Bartók Béla muzsikáját elemző könyvében mutatja be azt, hogyan tagolta zeneműveiben az egyes zenei gondolatok ütemsorrendjét a Fibonacci-szám hosszúságú szakaszok fölhasználásával Bartók. A Lendvai Ernő által felfedezett Fibonacci szerkezetelméleti összefüggéseket Bartók ösztönösen alkalmazta zenéjének formai arányrendszerében.

Kapcsolódó szócikkek

• aranymetszés
• levélállás
• Zene húros hangszerekre, ütőkre és cselesztára
• Fibonacci-kupac
• Saxon-Szász János polidimenzionális mezői
• OEIS
• Zeckendorf-tétel

Források

• D. E. Knuth: A számítógép-programozás művészete I.
• Gerőcs László: A Fibonacci-sorozat és általánosításai, Tankönyvkiadó, Budapest, 1988
• Török Judit: A Fibonacci-sorozat, Tankönyvkiadó, Budapest, 1984
• Bérczi Szaniszló: Sejtautomaták: Fibonacci növényeken át. Iskolakultúra. IV. No. 7. 16-32. o.,1994 (HU ISSN 1215-5233)
• Lendvai Ernő: Bartók dramaturgiája. Zeneműkiadó, Budapest, 1964
• Lovász – Pelikán – Vesztergombi: Diszkrét matematika. 74-84. old. Typotex Kiadó, 2006 ISBN 963-9664-02-2
• Hrant Arakelian: Mathematics and History of the Golden Section, Logos 2014, 404 p. ISBN 978-5-98704-663-0 (oroszul)

További információk

• Fibonacci numbers az On-Line Encyclopedia of Integer Sequences (OEIS) oldalán (angolul)
• Pravin Chandra and Eric W. Weisstein Fibonacci Number. From MathWorld (angolul)
• Fibonacci Numbers and the Golden Section
• The Fibonacci Quarterly – egy tudományos folyóirat, ami a Fibonacci-számokkal foglalkozik
• GoldenNumber.net
• Museum of Harmony and Golden Section
• Fibonacci Flim-Flam – Fibonacci-számok és áltudomány
• Fibonacci Spirals – Fibonacci-spirálokon alapuló képek
• The Golden Mean and the Physics of Aesthetics
• Hemachandra's application to Sanskrit poetry (pdf)
• Kovács Ádám–Vámos Attila: Aranyháromszög. Aranymetszés, Fibonacci-sorozat, szabályos ötszög; Műszaki, Budapest, 2007
• Böröcz Nándor: A kozmikus szoftver; Toro, Zalaegerszeg, 2009
• Burján-Gál Emil: Leonardo Pisano számai; Mark House, Gyergyószentmiklós, 2017