Rij van Fibonacci

De rij van Fibonacci is genoemd naar Leonardo van Pisa, bijgenaamd Fibonacci, zoon van Bonaccio, van Guglielmo dei Bonaccio. Hij noemt de rij in zijn boek Liber abaci, Boek over rekenen, uit 1202. De rij blijkt interessante eigenschappen te bezitten en verbanden te hebben met onder andere de gulden snede. De rij begint met 0 en 1, men kiest ook wel 1 en 1, en vervolgens is elk volgende element van de rij steeds de som van de twee voorgaande elementen. De eerste elementen van de rij^[1] 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, ...

Hierin heeft de 0 de index 0, de eerste 1 de index 1, enzovoort.

Ieder positief geheel getal kan volgens de stelling van Zeckendorf op een unieke wijze worden geschreven als de som van een of meer elkaar niet opvolgende getallen uit de rij van Fibonacci. Overeenkomende rijen zijn de rij van Lucas en de rij van Padovan.

Het is niet duidelijk wie als eerste de rij heeft uitgedacht. De rij van Fibonacci wordt al genoemd in de Chhandah-shāstra, Kunst van het metrum, van de Sanskriet schrijver Pingala, omstreeks 450 v. Chr. of volgens andere datering omstreeks 200 v. Chr.,^[2] 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.

Toen Fibonacci 20 jaar was, ging hij naar Algerije waar hij Indiase en Arabische wiskunde bestudeerde en wellicht leerde hij daar de rij kennen. Hij was in het westen de eerste die de rij in zijn Liber abaci, Boek van de rekenkunst, noemde, bij het 'konijnenprobleem'.^[3]

In zijn boek Liber Abaci berekent Fibonacci de groei van konijnenpopulaties. Vandaar soms de bijnaam konijnenrij. Fibonacci gebruikte hiervoor de volgende regels:

• in de eerste maand is er maar één jong paar konijnen
• 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, 89 ....

Een nieuwe historische analyse van Fibonacci en zijn werk wijst niet op konijnen maar op bijen. Gedurende zijn verblijf in Algerije bracht Fibonacci tijd door in of bij de stad Béjaïa, in die tijd een belangrijke exporteur van bijenwas. Anders dan bij het konijnenprobleem, waar een aantal niet in alle gevallen even realistische regels gebruikt worden, blijkt de ontwikkeling van een bijenpopulatie ook in werkelijkheid volgens de rij van Fibonacci te verlopen. Er wordt gesuggereerd dat feitelijk de bijenhouders van Béjaïa en kennis van de bijenstambomen de inspiratie voor de rij van Fibonacci vormden.^[4]

De manier waarop de rij van Fibonacci gedefinieerd is, is een voorbeeld van wat in de wiskunde een recursieve definitie wordt genoemd. Dit betekent dat de elementen op basis van een of meer voorgaande elementen worden vastgelegd, dus in de vorm van een differentievergelijking. Het ${\displaystyle n}$-de getal van Fibonacci wordt gegeven door:

${\displaystyle f_{0}=0}$

${\displaystyle f_{1}=1}$

${\displaystyle f_{n}=f_{n-1}+f_{n-2},\ {\text{voor }}n>1}$

De eerste twee elementen zijn per definitie 0 en 1, sommigen hanteren 1 en 1. Ieder volgend element is de som van de twee voorafgaande waarden. Andere waarden voor de eerste twee elementen zijn ook mogelijk, maar leveren een andere rij, bijvoorbeeld de rij van Lucas. Veel differentievergelijkingen hebben geen gesloten uitdrukking of expliciet voorschrift, waarmee het ${\displaystyle n}$-de element aan de hand van alleen het getal ${\displaystyle n}$ kan worden bepaald. Voor de rij van Fibonacci bestaat een dergelijke uitdrukking wel, namelijk:

${\displaystyle f_{n}={\frac {(1+{\sqrt {5}})^{n}-(1-{\sqrt {5}})^{n}}{2^{n}{\sqrt {5}}}}}$

Bovenstaande formule, voor het eerst gepubliceerd in 1730 door Abraham de Moivre, is op het eerste gezicht opvallend omdat ${\displaystyle f_{n}}$ een geheel getal is, terwijl de formule wortels bevat. Dat de termen waarin een wortel overblijft, wegvallen, is direct te begrijpen uit de binomiums voor de beide machten in de teller. Het bewijs van deze formule berust op het oplossen van een vierkantsvergelijking.

Uit de gegeven vergelijkingen kan worden afgeleid dat de voortbrengende functie voor de rij van Fibonacci gelijk is aan

${\displaystyle \sum _{n=0}^{\infty }f_{n}x^{n}={\frac {x}{1-x-x^{2}}}}$

Dit kan op de volgende manier:

${\displaystyle 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}=}$

${\displaystyle =0+1x+\sum _{n=2}^{\infty }(f_{n-2}+f_{n-1})x^{n}=}$

${\displaystyle =x+x^{2}\sum _{n=2}^{\infty }f_{n-2}x^{n-2}+x\sum _{n=2}^{\infty }f_{n-1}x^{n-1}}$

${\displaystyle =x+x^{2}\sum _{n=0}^{\infty }f_{n}x^{n}+x\sum _{n=1}^{\infty }f_{n}x^{n}}$

${\displaystyle =x+x^{2}\sum _{n=0}^{\infty }f_{n}x^{n}+x\left(-f_{0}x^{0}+\left(f_{0}x^{0}+\sum _{n=1}^{\infty }f_{n}x^{n}\right)\right)}$

${\displaystyle =x+x^{2}S+x\left(\sum _{n=0}^{\infty }f_{n}x^{n}\right)}$

${\displaystyle =x+x^{2}S+xS}$

Daaruit volgt dan:

${\displaystyle S={\frac {x}{1-x-x^{2}}}}$

Men kan de formule voor de ${\displaystyle n}$-de term uit de reeks ook uitdrukken in de gulden snede:

${\displaystyle f_{n}={{\varphi ^{n}-(1-\varphi )^{n}} \over {\sqrt {5}}}}$

Hierin is:

${\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1{,}618}$

het gulden getal.^[5]

De verhouding van twee opeenvolgende getallen van Fibonacci blijkt de gulden snede te benaderen. In de limiet geldt:

${\displaystyle \lim _{n\to \infty }{\frac {f_{n+1}}{f_{n}}}=\varphi }$

Overigens geldt dit voor alle paren getallen waarmee je een alternatieve reeks van fibonacci kunt starten. Bijvoorbeeld 1,3,4,7,etc. levert in de limiet ook de gulden snede op.

Behalve dat de getallen van Fibonacci met de gulden snede in verband staan, blijken zij ook in de natuur voor te komen. Bekijk bijvoorbeeld de structuur van een zonnebloem en tel het aantal spiralen waarin de zonnebloempitten gerangschikt zijn. De rij van Fibonacci komt ook terug in de verdeling van takken aan bomen, de ordening van bladeren aan takken, de vruchten van een ananas, de bloemen van een artisjok, zich ontvouwende varens, de ordening van de schubben van een dennenappel en de reeds genoemde honingbijenpopulaties. Dergelijke rangschikkingen met betrekking tot opeenvolgende Fibonacci-getallen komen voor in een grote variëteit aan planten. Het vermeerderen van bloembollen, zoals die van sneeuwklokjes en krokussen, gaat even snel, net zoals in de rij van Fibonacci ieder jaar 1,618 keer meer bollen, oftewel een groei van ruim 60%.

De differentievergelijking kan in matrixvorm geschreven worden als:

${\displaystyle {\begin{bmatrix}f_{n}\\f_{n-1}\\\end{bmatrix}}={\begin{bmatrix}1&1\\1&0\\\end{bmatrix}}{\begin{bmatrix}f_{n-1}\\f_{n-2}\\\end{bmatrix}}}$

Dit betekent immers:

${\displaystyle f_{n}=f_{n-1}+f_{n-2}}$

en

${\displaystyle f_{n-1}=f_{n-1}}$

Herhaald toepassen levert:

${\displaystyle {\begin{bmatrix}f_{n}\\f_{n-1}\\\end{bmatrix}}={\begin{bmatrix}1&1\\1&0\\\end{bmatrix}}^{2}{\begin{bmatrix}f_{n-2}\\f_{n-3}\\\end{bmatrix}}=\ldots ={\begin{bmatrix}1&1\\1&0\\\end{bmatrix}}^{n-1}{\begin{bmatrix}f_{1}\\f_{0}\\\end{bmatrix}}={\begin{bmatrix}1&1\\1&0\\\end{bmatrix}}^{n-1}{\begin{bmatrix}1\\0\\\end{bmatrix}}}$

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

${\displaystyle {\begin{bmatrix}1&1\\1&0\\\end{bmatrix}}}$

Alle machten van deze matrix kunnen direct worden berekend, dus zonder dat alle tussenliggende matrices moeten worden berekend, omdat er voor de getallen van Fibonacci een functievoorschrift is.

Er bestaan varianten op de rij van Fibonacci waarbij de elementen niet ontstaan uit de som van twee, maar uit de som van 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 Tetra(bo)nacci indien we de som van de vier voorgaande getallen nemen. Men kan dit verder veralgemenen naar de som van de ${\displaystyle n}$ voorgaande elementen. Hoewel Fibonacci (van filius Bonacci, zoon van Bonacci) een naam is, zijn tribonacci en tetra(bo)nacci dit natuurlijk niet.

• Tribonacci:^[6] 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, ...
• Tetranacci:^[7] 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.

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

${\displaystyle r_{0}=f_{N}}$

${\displaystyle r_{1}=f_{N-1}}$

${\displaystyle r_{n}=r_{n-2}-r_{n-1}}$, voor ${\displaystyle n>1}$

Deze definitie stelt ons bovendien in staat om ${\displaystyle f_{n}}$, voor ${\displaystyle n<0}$ te vinden. De eerste paar termen van deze negatieve rij van Fibonacci zien er als volgt uit voor ${\displaystyle r_{0}=f_{1}=1}$ en ${\displaystyle 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, ...

Als een polynoom een reële oplossing heeft kan men een oplossing bepalen met behulp van een variant van de Fibonacci-rij die gebruikmaakt van meer voorgaande termen en verschillende coëfficiënten. Deze variant is:

${\displaystyle f_{n}=x_{i-1}f_{n-1}+x_{i-2}f_{n-2}+\ldots +x_{0}f_{n-i}}$,

waarin ${\displaystyle i}$ de graad van de polynoom is en ${\displaystyle \sum _{k=0}^{i-1}x_{k}\in \mathbb {R} }$.

Definieer ${\displaystyle \phi ={\frac {f_{n-j}}{f_{n-1-j}}}}$, waarbij ${\displaystyle n}$ naar oneindig gaat en ${\displaystyle j\in \mathbb {N} }$. Als men de vergelijking deelt door ${\displaystyle f_{n-1}}$, wordt de vergelijking

${\displaystyle \phi =x_{i-1}+{\frac {x_{i-2}}{\phi }}+{\frac {x_{i-3}}{\phi ^{2}}}+\ldots +{\frac {x_{0}}{\phi ^{i-1}}}}$,

vermenigvuldigen met ${\displaystyle \phi ^{i-1}}$ levert:

${\displaystyle \phi ^{i}=x_{0}+x_{1}\phi ^{1}+x_{2}\phi ^{2}+\ldots +x_{i-1}\phi ^{i-1}}$

Termen overbrengen:

${\displaystyle \phi ^{i}-x_{i-1}\phi ^{i-1}-x_{i-2}\phi ^{i-2}-\ldots -x_{1}\phi ^{1}-x_{0}=0}$

De verhouding van de laatste en de voorlaatste term van deze rij is dus bijgevolg een nulpunt van deze polynoom.

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 ${\displaystyle n}$ komt voor in de rij van Fibonacci dan en slechts dan als ${\displaystyle 5n^{2}+4}$ of ${\displaystyle 5n^{2}-4}$ een kwadraat is.

Het negatieve gehele getal ${\displaystyle n}$ komt dan en slechts dan voor in de rij van Fibonacci als ${\displaystyle 5n^{2}+4}$ een kwadraat is.

Er bestaan rationale getallen die in hun decimale ontwikkeling de rij van Fibonacci vertonen.

In groepen van twee decimalen bijvoorbeeld:

${\displaystyle 1/(1-0{,}0101)=1{,}010203.050813.213455.904636.832003.232549\ldots }$

De plaats van de term 89 wordt verstoord door de driecijferige term 144, en die weer door de volgende.

In groepen van drie decimalen:

${\displaystyle 1/(1-0{,}001001)=1{,}001002.003005.008013.021034.055089.144233.377610\ldots }$

Verderop zal het laatste driecijferige getal verstoord worden door zijn viercijferige volger.

• Fibonacciwoorden ontstaan op dezelfde manier als de getallen in de rij van Fibonacci, maar door opeenvolgende elementen als tekenreeksen te behandelen en ze te concateneren in plaats van ze op te tellen.
• Een Fibonaccigedicht is een gedicht waarin het aantal lettergrepen in iedere volgende regel het volgende getal van fibonacci is.

• Geprogrammeerde Rij van Fibonacci met unittest