-A +A

Rij van Fibonacci

Printervriendelijke versiePrintervriendelijke versieVerstuur naar een vriendVerstuur naar een vriend

Rij van Fibonacci

 

De rij van Fibonacci is genoemd naar Leonardo van Pisa, bijgenaamd Fibonacci, die de rij noemt in zijn boek Liber abaci. In woorden is elk element van de rij steeds de som van de twee voorgaande elementen, beginnend met 0 en 1. De rij blijkt interessante eigenschappen en verbanden te bezitten met onder andere de gulden snede. De eerste elementen van de rij (rij A000045 in OEIS) zijn dan als volgt:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, ...

Het is evenwel niet duidelijk wie als eerste de rij heeft uitgedacht. Toen Fibonacci 20 jaar was, ging hij naar Algerije waar hij Indiaase en Arabische wiskunde bestudeerde. Wellicht leerde hij daar de rij kennen.

 

De manier waarop de rij van Fibonacci gedefinieerd is, is een voorbeeld van wat in de wiskunde een recursieve definitie genoemd wordt. Dit betekent dat de elementen vastgelegd worden op basis van een of meer voorgaande elementen; dit leidt tot een differentievergelijking. Het ne getal van Fibonacci wordt zo gegeven door:

f_0 = 0\,
f_1 = 1\,
f_n = f_{n-1} +f_{n-2}\, , voor n > 1

De eerste twee elementen zijn per definitie 0 en 1. Ook andere waarden voor de eerste twee elementen zijn mogelijk, maar leveren een andere rij.

Veel differentievergelijkingen hebben geen gesloten uitdrukking of expliciet voorschrift, waarmee het ne element enkel aan de hand van het getal n bepaald kan worden. Voor de rij van Fibonacci bestaat een dergelijke uitdrukking wel, namelijk:

f_n = \frac{(1+\sqrt 5)^n - (1-\sqrt 5)^n}{2^n \sqrt 5}

Bovenstaande formule, voor het het eerst gepubliceerd in 1730 door Abraham de Moivre, is op het eerste zicht opvallend omdat fn een geheel getal is, terwijl de formule wortels bevat. Zie differentievergelijking voor een bewijs van deze formule.

Uit de recursievergelijking kan worden afgeleid dat de voortbrengende functie voor de rij van Fibonacci gelijk is aan:

\sum_{n=0}^\infty f_n x^n = \frac{x}{1-x-x^2}.

Dit kan op volgende manier:

 S = \sum_{n=0}^\infty f_n x^n = f_0 x^0 + f_1 x^1 + \sum_{n=2}^\infty f_n x^n.
   =  0 + 1 x + \sum_{n=2}^\infty (f_{n-2} + f_{n-1})x^n.
   =  x + x^2 \sum_{n=2}^\infty f_{n-2} x^{n-2} + x \sum_{n=2}^\infty f_{n-1} x^{n-1}.
   =  x + x^2 \sum_{n=0}^\infty f_n x^n + x \sum_{n=1}^\infty f_n x^n.
   =  x + x^2 \sum_{n=0}^\infty f_n x^n + x (-f_0 x^0 + (f_0 x^0 + \sum_{n=1}^\infty f_n x^n)).
   =  x + x^2 S + x ( \sum_{n=0}^\infty f_n x^n).
   =  x + x^2 S + x \ S.
 S = \frac{x}{1 - x - x^2}.

Geschiedenis

De rij van Fibonacci wordt al genoemd in de Chhandah-shāstra („kunst van de versmaat“) van de Sanskriet schrijver Pingala (ca. 450 v. Chr. of volgens andere datering ca. 200 v. Chr.)[1]. onder de naam maatraameru („berg van de cadens“). Uitvoeriger behandelden in de 6e eeuw Virahanka en later Acharya Hemachandra (1089–1172) de rij, om rekentechnisch het metrum te beschrijven door de regelmatige verdeling in korte en lange lettergrepen.

In het westen was het de Italiaanse wiskundige Fibonacci die als eerste de rij noemt in zijn Liber abbaci (boek van de rekenkunst) bij het 'konijnenprobleem'.[2]:

Het konijnenprobleem

Fibonacci's berekening van een konijnenpopulatie in zijn Liber abbaci

De rij van Fibonacci blijkt ook op te duiken bij de studie van een konijnenpopulatie, vandaar soms de bijnaam konijnenrij. Leonardo Fibonacci gebruikte hiervoor de volgende regels:

  • we starten zonder konijnenparen en in de eerste maand hebben we één jong paar
  • een paar is volwassen vanaf de tweede maand
  • een volwassen paar krijgt elke maand één nieuw paar nakomelingen
  • de konijnen sterven niet

Het aantal aanwezige konijnenparen in een maand groeit dan precies volgens: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ....

Gulden snede en de natuur

Fibonaccispiraal

Men kan de formule voor de n-de term uit de reeks ook uitdrukken in de gulden snede:

f_n = {{\varphi^n-(1-\varphi)^n} \over {\sqrt 5}}

Hierin is:

\varphi  = \frac{{1 + \sqrt 5 }}{2}

de gulden snede.

Wanneer men de verhouding van twee opeenvolgende getallen van Fibonacci neemt, blijkt deze de gulden snede te benaderen. In de limiet is deze verhouding er zelfs aan gelijk, dit kan men wiskundig noteren als:

\lim_{n\to\infty}\frac{{f_{n + 1} }}{{f_n }} = \varphi

 

Fibonacci en matrixrekening

Een tegelwand van vierkanten met afmetingen uit de rij van Fibonacci

De differentievergelijking kan in matrixvorm geschreven worden als:

\begin{bmatrix}<br />
    f_n  \\<br />
    f_{n-1}  \\<br />
    \end{bmatrix}=\begin{bmatrix}<br />
    1&1  \\<br />
    1&0  \\<br />
    \end{bmatrix} \begin{bmatrix}<br />
    f_{n-1}  \\<br />
    f_{n-2}  \\<br />
    \end{bmatrix}.

Dit betekent immers:

f_n = f_{n-1} +f_{n-2}\,

en

f_{n-1} = f_{n-1}\,.

Door herhaald toepassen krijgen we:

<br />
    \begin{bmatrix}<br />
    f_n  \\<br />
    f_{n-1}  \\<br />
    \end{bmatrix}=<br />
    \begin{bmatrix}<br />
    1&1  \\<br />
    1&0  \\<br />
    \end{bmatrix}^2<br />
    \begin{bmatrix}<br />
    f_{n-2} \\<br />
    f_{n-3}  \\<br />
    \end{bmatrix}=\ldots =<br />
    \begin{bmatrix}<br />
    1&1  \\<br />
    1&0  \\<br />
    \end{bmatrix}^{n-1}<br />
    \begin{bmatrix}<br />
    f_1  \\<br />
    f_0  \\<br />
    \end{bmatrix}=<br />
    \begin{bmatrix}<br />
    1&1  \\<br />
    1&0  \\<br />
    \end{bmatrix}^{n-1}<br />
    \begin{bmatrix}<br />
    1  \\<br />
    0  \\<br />
    \end{bmatrix}<br />
    .

De enig nodige berekening is het bepalen van de macht van de volgende matrix:

\begin{bmatrix}<br />
    1&1  \\<br />
    1&0  \\<br />
    \end{bmatrix}.

Deze kan gevonden worden zonder dat men de voorgaande waarden moet berekenen.
Voor deze macht bestaat immers ook een gesloten vorm, zie
macht van een matrix voor de uitwerking.

Veralgemeningen

Er bestaan varianten op de rij van Fibonacci waarbij de elementen niet ontstaan uit de som van twee, maar drie of meer voorgaande elementen. Indien we de drie eerste elementen vastleggen en vanaf het vierde de som van de drie voorgaande nemen, dan verkrijgen we een rij die wel de rij van Tribonacci wordt genoemd. Op analoge wijze spreekt men van de rij van Tetranacci indien we de som van de vier voorgaande getallen nemen. Men kan dit verder veralgemenen naar de som van de n voorgaande elementen. (Hoewel Fibonacci (van filius Bonacci, zoon van Bonacci) een naam is, zijn tribonacci en tetrabonacci dit natuurlijk niet.)

  • Tribonacci (rij A000073 in OEIS): 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, ...
  • Tetranacci (rij A000078 in OEIS): 0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, ...

Deze getalrijen bevatten echter niet de karakteristieke eigenschappen die aan de Fibonacci-getallen toegeschreven worden; er is geen relatie met de gulden snede, en deze rijen kunnen dus ook niet fungeren als hulpmiddel bij het creëren van wat men als 'esthetisch ideaal' betitelt.

Fibonacci omgekeerd

Wanneer er twee opeenvolgende termen uit de rij van Fibonacci bekend zijn, bijvoorbeeld f_{N-1}\, en f_N\,, kan men het deel van de rij dat hieraan voorafging reconstrueren aan de hand van de volgende recursieve formule:

r_0 = f_N\,
r_1 = f_{N-1}\,
r_n = r_{n-2} - r_{n-1}\, , voor n > 1

Deze definitie stelt ons bovendien in staat om fn, voor n < 0 te vinden. De eerste paar termen van deze negatieve rij van Fibonacci zien er als volgt uit voor r_0 = f_1 = 1\, en r_1 = f_0 = 0\,:

1, 0, 1, -1, 2, -3, 5, -8, 13, -21, 34, -55, 89, -144, 233, -377, 610, -987, 1597, -2584, 4181, -6765, 10946, ...

Test

Door een test, geformuleerd door Ira Gessel in 1972, is eenvoudig te controleren of een getal in de rij van Fibonacci voorkomt:

Het positieve gehele getal n komt voor in de rij van Fibonacci dan en slechts dan als 5n2 + 4 of 5n2 − 4 een kwadraat is.

Het negatieve gehele getal n komt voor in de rij van Fibonacci dan en slechts dan als 5n2 + 4 een kwadraat is.

Zie ook

Externe links

Bronnen, noten en/of referenties: bron: Wikipedia, de vrije encyclopedie

  1. Parmanand Singh: Acharya Hemachandra and the (so called) Fibonacci Numbers. In: Mathematics Education 20,1 (Siwan, 1986), S. 28–30, ISSN 0047-6269]
  2. Baldassare Boncompagni (Hrsg.): Scritti di Leonardo Pisano matematico del secolo decimoterzo, Bd. I, Tipografia delle scienze matematiche e fisiche, Rom, 1857, S. 283–284 (Kap. XII, 7: „Quot paria coniculorum in uno anno ex uno pario germinentur“)

 

Gerelateerd
Downloads: 
0
Uw beoordeling Geen
Aangemaakt op: vr, 16/04/2010 - 05:51
Laatst aangepast op: di, 26/08/2014 - 22:14

Hebt u nog een vraag?

Hebt u nog een vraag in dit verband, klik dan hier om uw vraag aan ons te stellen, of meteen een afspraak te maken voor een consultatie.

Aanvulling

Heeft u een suggestie, aanvulling of voorstel tot correctie met betrekking tot deze pagina? Gebruik dit adres om het te melden.