Fibonaccis talfølge
Vi definere Fibonaccis talfølge som følgen
$$\{1,1,2,3,5,8,13,\ldots\}$$
Lader vi \(F_n\) betegne det \(n\)'te tal følgen, kan følgen også beskrives med rekursionsligningen
$$F_n=F_{n-1}-F_{n-2}$$
med begyndelsesbetingelserne \(F_1=F_2=1\).
Det gyldne snit
Der gælder at forholdet mellem tallene i følgen nærmer sig det gyldne snit. Med andre ord vil
$$\lim_{n\rightarrow\infty}\frac{F_{n+1}}{F_n}=\frac{1+\sqrt{5}}{2}$$
Bevis
Definér en ny følge \(x_n=\frac{F_{n+1}}{F_n}\). Da gælder der at
\begin{align*}
F_n=F_{n-1}-F_{n-2} &\Rightarrow \frac{F_n}{F_{n-1}}=1+\frac{F_{n-2}}{F_{n-1}} \\
&\Rightarrow x_{n-1} = 1 + \frac{1}{x_{n-2}}
\end{align*}
Bemærk at for alle \(n\geq 0\) vil \(1\leq x_n\leq 2\). Der må derfor gælde at
$$\lim_{n\rightarrow\infty}x_{n-1}=\lim_{n\rightarrow\infty}x_{n-2}$$
Grænseværdien kan altså findes ved at løse
$$x=1+\frac{1}{x} \Rightarrow x^2=x+1$$
En løsningen til denne andengradsligning, som opfylder at \(1\leq x\leq 2\), er netop \(\frac{1+\sqrt{5}}{2}\).
Det \(n\)'te Fibonacci-tal
Man kan benytte flg. formel til at approksimere det \(n\)'te tal i Fibonaccis talfølge
$$F_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)$$
Bevis
Vi viser først flg.
Hvis \(x\) er en løsning til lignignen \(x^2=x+1\), så gælder der at \(x^n=F_n\cdot x+F_{n-1}\)
Vi viser dette ved induktion over \(n\).
Pr. antagelsen har vi netop at
$$x^2=x+1 \Rightarrow x^2=F_2\cdot x +F_1$$
altså er dette sandt for \(n=2\).
Antag nu, at det gælder for \(n=k\), dvs. at
$$x^k=F_k\cdot x+F_{k-1}$$
Ved at gange igennem med \(x\), og bruge hvad vi viste foroven, får vi at
\begin{align*}
x^{k+1}&=F_k\cdot x^2+F_{k-1}\cdot x \\
&= F_k\cdot (x+1)+F_{k-1}\cdot x \\
&= F_k\cdot x+F_k+F_{k-1}\cdot x \\
&= (F_k+F_{k-1})\cdot x+F_k \\
&= F_{k+1}\cdot x+F_k
\end{align*}
Altså er det sandt for \(n=k+1\). Vi har dermed bevist påstanden foroven.
Bemærk at de to løsninger til \(x^2=x+1\), er
$$\Phi_+=\frac{1+\sqrt{5}}{2},\ \ \ \ \Phi_-=\frac{1-\sqrt{5}}{2}$$
Vi ved derfor at
$$(\Phi_+)^n=F_n\cdot (\Phi_+)+F_{n-1}$$
og
$$(\Phi_-)^n=F_n\cdot (\Phi_-)+F_{n-1}$$
Så
\begin{align*}
(\Phi_+)^n-(\Phi_-)^n &= F_n\cdot \left((\Phi_+)-(\Phi_-)\right) \\
&= F_n\cdot \left(\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}\right) \\
&= F_n\cdot \sqrt{5}
\end{align*}
hvoraf
$$F_n=\frac{1}{\sqrt{5}}\left((\Phi_+)^n-(\Phi_-)^n\right)$$
Generalisering af Fibonacci-tallene
Man kan generalisere Fibonacci-tallene og definere talfølgen for negative \(n\). Her vil der gælde at
$$F_{-n}=(-1)^{n+1}\cdot F_n$$
for alle \(n> 0\). Der gælder at \(F_0=0\). Man opnår dermed talfølgen
$$\{\ldots,13,-8,5,-3,2,-1,1,0,1,1,2,3,5,8,13,\ldots\}$$