Tag archieven: Fibonacci

De gulden snede en de rij van Fibonacci

Geplaatst op door

We kennen allemaal de gulden snede. Bij de gulden snede verhoudt het grootste van de twee delen van een lijnstuk zich tot het kleinste, zoals het gehele lijnstuk zich verhoudt tot het grootste. 

Maar er is ook een verband tussen \varphi en de rij van Fibonacci. Noteren we het n-de getal in deze rij door F(n).

  • Als we in bovenstaande uitdrukking \frac{a}{b} vervangen door \varphi, dan vinden we dat \varphi^2=\varphi+1.
  • Maar dat is \varphi^3=\varphi^2+\varphi=2\varphi+1.
  • Dus \varphi^4=2\varphi^2+\varphi=3\varphi+2.
  • Algemeen kan men dan stellen dat :

        \[\varphi^n=F(n)\varphi+F(n-1)\]

Stelling van Zeckendorf

Geplaatst op door

De stelling van Zeckendorf  is vernoemd naar de Belgische dokter, legerofficier en wiskundige Edouard Zeckendorf.

De stelling zegt dat elk positief geheel getal op een unieke manier kan geschreven worden als de som van één of meer verschillende  getallen uit de rij van Fibonacci die elkaar niet opvolgen. Een dergelijke som wordt de Zeckendorfrepresentatie van een getal genoemd. De Zeckendorfrepresentatie van het getal 100 is 89+8+3.

Start met het grootste getal a_1 uit de rij van Fibonacci dat kleiner is of gelijk aan het getal n. Zoek daarna het grootste getal a_2 uit de rij van Fibonacci dat kleiner is of gelijk aan het verschil  n-a_1. Blijf dit proces herhalen totdat het verschil uiteindelijk zelf een getal is uit de rij van Fibonacci. Nu zijn a_1 en a_2 geen opeenvolgende termen van de rij van Fibonacci, want waren ze dat wel dan zou a_1+a_2 een term van de rij van Fibonacci zijn en groter zijn dan n. Dit is onmogelijk want a_1+a_2<n.

We geven ook een Python programma mee om de Zeckendorf representatie te berekenen. In het voorbeeld berekenen we deze van 2021:

Python probleem 2

Geplaatst op door

Bereken de som van alle oneven Fibonacci getallen kleiner dan 4 miljoen.

Antwoord

  • De rij van Fibonacci : 1,1,2,3,5,8,13,21,.. De rij begint met twee enen en daarna is elke term gelijk aan de som van de vorige twee termen.
  • Een eerste idee: bereken elke term , controleer of het even is en tel op bij een gegeven teller. 
  • Omdat de rij gegeven wordt door een recursief voorschrift, is het gebruik van een functie Fibonacci(n) niet zo interessant . Immers worden telkens alle vorige termen opnieuw uitgerekend.
  • We kunnen beter werken met 3 termen van de rij en dan doorschuiven:a=1;b=1en c=a+b.Daarna geven we de waarde van b aan a en de waarde van c aan b en berkenen opnieuw a+b

 

 

Fibonacci en de gulden snede

Geplaatst op door

 

De rij van Fibonacci: 1,1,2,3,5,8,13,21,…  wordt gevormd door met twee enen te beginnen en dan is elke term de som van de vorige twee termen, dus:

    \[a_1=a_2=1 \text{ en } a_{n+2}=a_{n+1}+a_n\]

Vorm nu de rij s_n door twee opeenvolgende termen van de rij van Fibonacci te delen door elkaar:

    \[s_n=\frac{a_{n+1}}{a_n}\]

Een paar termen van die rij zijn : 1,2,\frac{3}{2},\frac{5}{3},\frac{8}{5},.... Wat zou de limiet van deze rij nu zijn?

We vermoeden dat deze limiet bestaat. Noteer de limiet met L.
Nu geldt s_n=\frac{a_{n+1}}{a_n}=\frac{a_n+a_{n-1}}{a_n}=1+\frac{1}{s_{n-1}}. Dus voldoet de limiet L aan de betrekking L=1+\frac{1}{L}. Dit geeft de vergelijking

    \[L^2-L-1=0\]

De positieve oplossing van deze vergelijking is \frac{1+\sqrt{5}}{2}=\varphi=1,6180 3398 8749 8948 482... , de gulden snede!