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!

Puzzels door de eeuwen heen

Geplaatst op door

Puzzels, raadsels, denkspelen hebben de mensheid altijd al gefascineerd Archeologische opgravingen hebben hun aanwezigheid kunnen vaststellen bij vrijwel alle beschavingen. Uit de verre oudheid  kennen we onder andere het koningsspel van Ur en het Senet bordspel uit Egypte:

 

 

 

 

 

 

Oorspronkelijk was de functie van die denkspelen eerder mythisch-religieus. Bordspelen konden aanwijzingen geven over het verloop van een oorlog. Via tekens kon de Godheid communiceren met de mensheid. Vooral de getallen hadden dan een magische betekenis. Denk maar aan het magische vierkant van Lo Shu. Voor de Chinezen waren de oneven getallen mannelijk en was het kruis het symbool van mannelijkheid en goddelijkheid.

In de loop  van de geschiedenis is de klemtoon evenwel verschoven en is men het spel meer gaan bekijken als een aangenaam tijdverdrijf. De spelletjes waren fascinerend omwille van de uitdaging die er in school. Ook beroemde wiskundigen hebben zich ermee bezig gehouden: Alcuïnus met het probleem van de wolf, de geit en de kool; Fibonacci met het konijnenprobleem, Gauss met de verplaatsing van de dames op een schaakbord,…

Nog later werden vele intellectuele spelletjes uit de recreatieve sfeer gehaald  en werden onderworpen aan een grondige wiskundige analyse. Neem het voorbeeld van de 7 bruggen van Königsberg met de grafentheorie of het vierkleurenprobleem. De banden tussen recreatieve en ernstige wiskunde werden aangehaald en ingewikkelde wiskundige technieken werden gebruikt bij de analyse van schijnbaar eenvoudige problemen.