Fibonaccitalen

Den här posten är, hur ska jag säga, överkurs låter bara svårt, men optional. Den är tänkt att ge ytterligare ett perspektiv, men inget man behöver sitta och plugga inför tentan.

Fibonaccitalen definieras av de två startvärdena $F_0=0$ och $F_1=1$, och den rekursiva ekvationen
$$F_{n+2} = F_n+F_{n+1}.$$
Med andra ord, varje tal i följden är summan av de två föregående, så det börjar
$$0,1,1,2,3,5,8,13,21,34,55,89,144,\dots.$$ Fibonaccitalen dyker upp lite här och där i matematiken, men jag ska inte prata här om historien och varför de är viktiga, det är bara att googla!

Det finns en märklig "exakt formel" för Fibonaccitalen,
$$F_n = \frac1{\sqrt{5}}\left(\frac{1+\sqrt{5}}2\right)^n - \frac1{\sqrt{5}}\left(\frac{1-\sqrt{5}}2\right)^n.$$
Det här ser konstigt ut första gången man stöter på det. Det är en massa roten ur 5 överallt, så det är inte självklart att det ens blir heltal, men testar man att sätta in några värden på $n$ verkar det stämma. Och hur kommer man på en sådan formel?

Jag vet inte hur den först upptäcktes, men vi kan härleda den med lite modernt linjär algebra-tänk.

Först struntar vi i startvärdena, och definierar rummet av alla talföljder $(a_0, a_1, a_2,\dots)$ som uppfyller ekvationen $a_{n+2} = a_n+a_{n+1}$ för alla $n$. Det här är ett linjärt rum (under termvis addition och multiplikation). Vi kan kalla det $V$, och Fibonacciföljden är en punkt i $V$!

Några andra punkter i $V$ är nollan: $$(0,0,0,0,0,0\dots),$$ minus Fibonacci: $$(0,-1,-1,-2,-3,-5\dots),$$ Fibonacci förskjutet ett steg: $$(1,1,2,3,5,8\dots),$$ och Lucastalen: $$(2,1,3,4,7,11\dots).$$
Rummet $V$ har två dimensioner, vilket man informellt inser genom att det finns två frihetsgrader. Vi kan välja $a_0$ och $a_1$ hur vi vill, men de bestämmer sedan hela resten av följden. Vi skulle kunna "koda" punkterna i $V$ genom att bara ange de två första talen i varje följd. Fibonaccitalen blir då $(0,1)$, och den andra vektorn i standardbasen, $(1,0)$, representerar en förskjuten Fibonacci: $$(1,0,1,1,2,3,5,\dots).$$
En följd i $V$ som börjar med $a_0=x$ och $a_1=y$ kan skrivas med "koordinaterna" $x$ och $y$, som $$x\cdot (1,0,1,1,2,3,5,\dots) + y\cdot (0,1,1,2,3,5,8,\dots).$$
Men det finns ett par ännu mer speciella punkter i $V$, nämligen de som är geometriska följder, och mer exakt, som har formen:
$$(1, x, x^2, x^3, x^4, x^5,\dots).$$
Det fiffiga är att eftersom en geometrisk följd växer (krymper) med samma faktor hela tiden, behöver vi bara kolla för vilka $x$ det stämmer att tredje talet i följden är summan av de två första, dvs för vilka $x$ som $$x^2 = 1+x.$$
Om den ekvationen gäller, så följer att $x^{n+2} = x^n+x^{n+1}$ för alla $n$.
Löser vi ekvationen, får vi rötterna $$\alpha = \frac{1+\sqrt{5}}2$$ och $$\beta = \frac{1-\sqrt{5}}2.$$
Rummet $V$ innehåller alltså punkterna $$(1,\alpha, \alpha^2,\alpha^3,\dots)$$ och $$(1,\beta, \beta^2,\beta^3,\dots).$$
Eftersom de här två vektorerna inte är parallella, och inte är noll, spänner de upp hela $V$ ($V$ har ju bara två dimensioner). Fibonaccitalen kan därför skrivas som en linjärkombination av $(1,\alpha, \alpha^2,\alpha^3,\dots)$ och $(1,\beta, \beta^2,\beta^3,\dots)$. Då återstår bara att beräkna koordinaterna. Vi söker alltså $A$ och $B$ så att $$(0,1,1,2,3,5,\dots) = A\cdot (1,\alpha, \alpha^2,\alpha^3,\dots) + B \cdot (1,\beta, \beta^2,\beta^3,\dots).$$
Tittar vi på första talen i respektive följd, får vi att $0 = A + B$, så $B=-A$. Det andra talet i respektive följd ger att $$1 = A\cdot \alpha + B\cdot \beta =  A\cdot \alpha + (-A)\cdot \beta = A\cdot (\alpha-\beta) = A \cdot \sqrt{5},$$ så $A=1/\sqrt{5}$ och $B = -1/\sqrt{5}$, och då har vi faktiskt härlett den exakta formeln. Vi har $$(0,1,1,2,3,5,\dots) = \frac1{\sqrt{5}}\cdot (1,\alpha, \alpha^2,\alpha^3,\dots) - \frac1{\sqrt{5}}\cdot (1,\beta, \beta^2,\beta^3,\dots),$$ eller om man tittar på det $n$:te talet i följden och sätter in de kända värdena på $\alpha$ och $\beta$: $$F_n = \frac1{\sqrt{5}}\left(\frac{1+\sqrt{5}}2\right)^n - \frac1{\sqrt{5}}\left(\frac{1-\sqrt{5}}2\right)^n.$$ Lägg märke till att den andra termen går mot noll, så skulle man använda det här numeriskt, behöver man bara räkna ut första termen och avrunda till närmaste heltal.