Fibonacci sommen - Wiskunst

Inhoud

Inleiding
Fibonacci
Vragen
Gulden-snede

Inleiding

Al lezend in het boek MindF*ck van Victor Mids en Oscar Verpoort werd ik geïnspireerd tot het schrijven van dit stukje.

In het boek komt (in mijn eigen bewoordingen) de volgende truc voor:

“Vraag iemand twee willekeurige getallen onder elkaar te schrijven (niet al te groot, want de persoon moet ermee gaan rekenen). Laat de persoon nu deze twee getallen optellen en de som onder het tweede getal zetten. Vraag nu aan deze persoon om het tweede en derde getal bij elkaar op te tellen en deze som daar weer onder te zetten. Laat hem/haar dit herhalen totdat er 10 getallen onder elkaar staan.

Nu zeg je dat je in een oogwenk deze 10 getallen bij elkaar zult optellen. De persoon laat het blaadje met de 10 getallen aan je zien en je zet er een streep onder met daaronder de som van de getallen.

Laat de persoon deze getallen ook bij elkaar optellen (rekenmachine toegestaan) en hij/zij zal verbaasd zijn over de uitkomst. Jij had het namelijk goed!

De truc is als volgt: Kijk naar het zevende getal en vermenigvuldig dit met 11 (x10 + 1) en zet dit getal onder de streep. Onafhankelijk van de gekozen getallen werkt dit altijd.”

Tot zover het boek. Maar hoe zit dit nu? Daar geeft het boek geen antwoord op. Dus gaan we zelf maar aan de slag.

Fibonacci

De meeste mensen hebben wel gehoord over de rij van Fibonacci. Deze rij bestaat uit de volgende getallen:

1, 1, 2, 3, 5, 8, 13, 21, 34, …

en is opgebouwd volgens een vast patroon: De eerste twee termen zijn 1 en de daarop volgende termen zijn de som van de voorgaande twee termen.

In formulevorm:

\left\{\begin{matrix}F_{1}=F_{2}=1\\F_{n}=F_{n-1}+F_{n-2},\forall n>2\end{matrix}\right.

We definiëren nu de Fibonacci-som als volgt:

s_{n}=\sum_{i=1}^{n}F_{i}

S_n is dus de cumulatieve som van alle Fibonacci-getallen t/m de n^e.

Kijk even naar de volgende tabel:

n	1	2	3	4	5	6	7	8	9	10
Fib_n	1	1	2	3	5	8	13	21	34	55
S_n	1	2	4	7	12	20	33	54	88	143

In bovenstaande tabel zijn S₆ en S₁₀ rood en F₅ en F₇ groen gemarkeerd. Ik kan namelijk S₆ uitdrukken in F₅ en evenzo S₁₀ in S₇ en wel als volgt:

S₆ = 4 x F₅ en S₁₀ = 11 x F₇.

Nu kan ik natuurlijk iedere S_n in een F_m uitdrukken (bijvoorbeeld S₅ = 6 x F₃), maar met deze twee is toch iets bijzonders aan de hand.

We maken even een nieuwe tabel:

n	1	2	3	4	5	6	7	8	9	10
Fib_n	4	7	11	18	29	47	76	123	199	322
S_n	4	11	22	40	69	116	192	315	514	836

En nog steeds geldt: S₆ = 4 x F₅ en S₁₀ = 11 x F₇ (merk op dat S₅ = 6 3/11 x F₃).

Dit verdient nader onderzoek.

In Excel even een grotere tabel gemaakt:

Wanneer je in deze tabel verschillende waarden voor F₁ en F₂ invult dan blijkt dat de gele cellen onveranderlijk blijven

Uit de tabel haal ik de volgende onveranderlijke S_n’s:

S₆ = 4 x F₅S₁₀ = 11 x F₇S₁₄ = 29 x F₉S₁₈ = 76 x F₁₁…

Vragen

De volgende vragen dringen zich nu op:

Kunnen we een formule bedenken voor iedere “bijzondere” S_n uitgedrukt als een getal (de vermenigvuldiger) keer een F_m?
Kunnen we de vermenigvuldiger uit de formule van vraag 1 bepalen?
Kunnen we aantonen dat voor de bijzondere S_n’s de vermenigvuldiger invariant is?

Uit de voorbeelden en uit de grote tabel blijkt dat:

S_4n+2 = V_n x F_2n+3.

Dit is dus het antwoord op vraag 1.

We weten uit de voorbeelden dat:

V₁ = 4,
V₂ = 11,
V₃ = 29,
V₄ = 76…

Deze rij getallen biedt niet meteen houvast om een gemakkelijke regel voor V₅, V₆…V_n te bepalen. Hiervoor moeten we wat verder onderzoek doen.

Laten we eens kijken naar S₁₀ met als startgetallen F₁=A=4 en F₂=B=7:

n	F_n	A		B
1	4	1A
2	7			1B
3	11	1A	+	1B
4	18	1A	+	2B
5	29	2A	+	3B
6	47	3A	+	5B
7	76	5A	+	8B
8	123	8A	+	13B
9	199	13A	+	21B
10	322	21A	+	34B
	—+	—+		—+
	836	55A		88B

S₁₀ = 836 = 55A + 88B = 11(5A+8B). Maar nu is 5A+8B gelijk aan F₇ (kijk maar in de tabel hierboven). Dus is S₁₀ = 11 x F₇. A en B zijn hier willekeurig en zowel S₁₀ als F₇ zijn in dezelfde A en B uitgedrukt (nl. 5A+8B) waarmee de vermenigvuldiger (11) dus invariant is.

Hiermee is dus (min of meer) vraag 3 beantwoord.

Kijk nog eens goed naar de factoren van A en B in de bovenstaande tabel. De factoren bij A en bij B volgen weer keurig de (standaard) rij van Fibonacci!

En dit geeft ons houvast voor een formule voor de vermenigvuldigers V_n.

V₂=11=(F₁₀-F₁₁-1)/(F₅-F₆),
V_n=(F_4n+2+F_4n+3)/(F_2n+1+F_2n+2).

En hiermee is ook vraag 2 opgelost.

We hebben dus voor de mooie S_n’s de volgende formule:

S_{4n+2}=\frac{F_{4n+2}+F_{4n+3}\text{ - }1}{F_{2n+1}+F_{2n+2}}\cdot F_{2n+3}

Tot slot zou het mooi zijn als we in de formule voor S_n alleen maar afhankelijk zouden zijn van gewone getallen al dan niet in combinatie met n, ofwel dat we S_n kunnen uitdrukken in termen van n.

Dit betekent dat we dus een formule voor F_n uitgedrukt in n moeten hebben.

Gulden-snede

Welnu, deze is er:

F_{n}=\frac{\left ( \frac{1+\sqrt{5}}{2} \right )^{n}\text{ - }\left ( \frac{1\text{ - }\sqrt{5}}{2} \right )^{n}}{\sqrt{5}}

Deze formule is (vrij eenvoudig) te bewijzen door middel van volledige inductie, maar dat laat ik graag aan de lezer over.

De getallen (1+√5)/2 en (1-√5)/2 komen niet zo maar uit de lucht vallen.

Wanneer je kijkt naar het quotiënt van twee opeenvolgende Fibonacci getallen, dus F_m/F_m_-1, en je gaat steeds verder in de rij dat blijkt dat het quotiënt naar een bepaalde limiet-waarde toegaat. Deze limiet-waarde blijkt (1+√5)/2 te zijn.

Kijk maar eens:

Stel :

L=\lim_{n \to \infty }\frac{F_{n}}{F_{n\text{ - }1}}=\lim_{n \to \infty }\frac{F_{n+1}}{F_{n}}

De tweede = heeft te maken met de eigenschappen van limieten (n gaat toch naar oneindig).

Denk nog even aan de recurente betrekking van F_n:

F_{n+1}=F_{n}+F_{n\text{ - }1}

dan krijgen we nu:

L=\lim_{n \to \infty}\frac{F_{n+1}}{F_n}=\lim_{n \to \infty}\frac{F_{n}+F_{n\text{ - }1}}{F_n}=\lim_{n \to \infty}\frac{F_{n}}{F_n}+\lim_{n \to \infty}\frac{F_{n\text{ - }1}}{F_n}=1+\frac{1}{L}

Bedenkt bij de laatste limiet dat F_n_-1/F_n = 1 / (F_n/F_n_-1).

We hebben dus L = 1 + 1/L. Dat kunnen we herschrijven als L² = L + 1 ofwel L² – L – 1 = 0.

En met behulp van de abc-formule vinden we voor L de waardes (1+√5)/2 en (1-√5)/2.

Tussen haakjes (het getal (1+√5)/2 staat ook wel bekend als de waarde van de gulden-snede en wordt ook wel φ (phi) genoemd).

Met al deze kennis kunnen we nu een formule voor mooie S_n’s uitgedrukt in n geven:

S_{4n+2}=\frac{\frac{\left ( \frac{1+\sqrt{5}}{2} \right )^{4n+2}\text{ - }\left ( \frac{1\text{ - }\sqrt{5}}{2} \right )^{4n+2}}{\sqrt{5}}+\frac{\left ( \frac{1+\sqrt{5}}{2} \right )^{4n+3}\text{ - }\left ( \frac{1\text{ - }\sqrt{5}}{2} \right )^{4n+3}}{\sqrt{5}}\text{ - }1}{\frac{\left ( \frac{1+\sqrt{5}}{2} \right )^{2n+1}\text{ - }\left ( \frac{1\text{ - }\sqrt{5}}{2} \right )^{2n+1}}{\sqrt{5}}+\frac{\left ( \frac{1+\sqrt{5}}{2} \right )^{2n+2}\text{ - }\left ( \frac{1\text{ - }\sqrt{5}}{2} \right )^{2n+2}}{\sqrt{5}}}\cdot \frac{\left ( \frac{1+\sqrt{5}}{2} \right )^{2n+3}\text{ - }\left ( \frac{1\text{ - }\sqrt{5}}{2} \right )^{2n+3}}{\sqrt{5}}

Wat kan wiskunde toch mooi zijn!

[Oplossing raadsel 3]