Verallgemeinerte Fibonacci-Folge

Eine Verallgemeinerung der Fibonacci-Folge ist entweder eine Erweiterung der Fibonacci-Folge auf größere Definitionsbereiche als die natürlichen Zahlen oder eine Verallgemeinerung des Bildungsgesetzes.

Erweiterung auf größere Definitionsbereiche

Erweiterung auf alle ganzen Zahlen

Wenn man das Bildungsgesetz der Fibonacci-Folgen umkehrt, erhält man

${\displaystyle f_{n-2}=f_{n}-f_{n-1}}$.

Mit dieser Formel kann man rekursiv Fibonacci-Zahlen zu negativen ganzen Zahlen berechnen. Ferner gilt die Formel von Moivre-Binet auch für negative ganze Zahlen: Für den goldenen Schnitt ${\displaystyle \varphi }$ gilt:

${\displaystyle 1+{\frac {1}{\varphi }}=\varphi \Leftrightarrow {\frac {1}{\varphi }}=\varphi -1\Leftrightarrow 1-\varphi -1={\frac {1}{1-\varphi }}}$

Setzt man ${\displaystyle \psi :=1-\varphi }$, so folgt aus

${\displaystyle {\tfrac {\varphi ^{0}-\psi ^{0}}{\sqrt {5}}}=0=f_{0}}$, ${\displaystyle {\tfrac {\varphi ^{1}-\psi ^{1}}{\sqrt {5}}}=1=f_{1}}$

und

${\displaystyle f_{-(n+1)}=f_{-(n-1)-2}=f_{-(n-1)}-f_{-n}}$

${\displaystyle ={\frac {\varphi ^{-n+1}-\psi ^{-n+1}}{\sqrt {5}}}-{\frac {\varphi ^{-n}-\psi ^{-n}}{\sqrt {5}}}={\frac {{\frac {\varphi -1}{\varphi ^{n}}}-{\frac {\psi -1}{\psi ^{n}}}}{\sqrt {5}}}={\frac {\varphi ^{-(n+1)}-\psi ^{-(n+1)}}{\sqrt {5}}}}$.

Der Induktionsschluss ergibt

${\displaystyle \forall n\in \mathbb {N} _{0}:f_{-n}={\frac {\varphi ^{-n}-\psi ^{-n}}{\sqrt {5}}}}$,

so dass schließlich die Formel von Moivre-Binet

${\displaystyle \forall n\in \mathbb {Z} :f_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\sqrt {5}}}}$

für alle ganzen Zahlen gilt.

Erweiterung auf alle komplexen Zahlen

Die geschlossene Form für die ${\displaystyle n}$-te Fibonacci-Zahl lautet für ganze Zahlen (siehe oben):

${\displaystyle f_{n}={\frac {\Phi ^{n}-(1-\Phi )^{n}}{\sqrt {5}}},\qquad n\in \mathbb {Z} }$,

wobei ${\displaystyle \Phi }$ der goldene Schnitt ist. Für den goldenen Schnitt ${\displaystyle \Phi }$ gilt die folgende Gleichung:

${\displaystyle 1+{\frac {1}{\Phi }}=\Phi \Leftrightarrow (-1){\frac {1}{\Phi }}=1-\Phi }$

${\displaystyle \Rightarrow (1-\Phi )^{n}=(-1)^{n}\left({\frac {1}{\Phi }}\right)^{n}=(-1)^{n}\Phi ^{-n}}$

Ist ${\displaystyle n}$ eine ganze Zahl, dann gilt jedoch:

${\displaystyle (-1)^{n}=\cos(n\pi )}$

Deshalb ist die stetige und analytische Funktion

${\displaystyle \operatorname {Fib} (x)={\frac {\Phi ^{x}-\cos(x\pi )\Phi ^{-x}}{\sqrt {5}}}}$

eine Fortsetzung der Fibonacci-Zahlen auf den komplexen Zahlen.

Verallgemeinerung des Bildungsgesetzes

Lucas-Folge

Die Fibonacci-Folge ist ein Spezialfall der Lucas-Folge.

Folgen mit ähnlichem Bildungsgesetz

Folgen in den komplexen Zahlen

Sei ${\displaystyle (g_{n})_{n\in \mathbb {N} _{0}}}$ eine Folge in ${\displaystyle \mathbb {C} }$, die für ${\displaystyle n\geq 0}$ durch das rekursive Bildungsgesetz

${\displaystyle g_{n+2}=g_{n+1}+g_{n}}$

definiert ist, so ist eine solche Folge eine Verallgemeinerung der Fibonacci-Folge, da diese entsteht, wenn man ${\displaystyle g_{0}=0}$ und ${\displaystyle g_{1}=1}$ setzt. Für das ${\displaystyle n}$-te Folgenglied dieser Folge gibt es einen geschlossenen Ausdruck:

${\displaystyle g_{n}=f_{n}\cdot g_{1}+f_{n-1}\cdot g_{0},\quad n\geq 0}$,

wobei ${\displaystyle f_{n}}$ die ${\displaystyle n}$-te Fibonacci-Zahl ist. Dies folgt aus vollständiger Induktion mit Induktionsanfang

${\displaystyle g_{0}=0\cdot g_{1}+1\cdot g_{0}=f_{0}\cdot g_{1}+f_{-1}\cdot g_{0}}$

und Induktionsschritt

${\displaystyle g_{n}=g_{n-1}+g_{n-2}=g_{1}\cdot (f_{n-1}+f_{n-2})+g_{0}\cdot (f_{n-2}+f_{n-3})=g_{1}\cdot f_{n}+g_{0}\cdot f_{n-1}}$

Folgen von Vektoren

Ist ${\displaystyle V}$ ein Vektorraum und sind ${\displaystyle g_{0},g_{1}\in V}$, kann man eine Folge ${\displaystyle (g_{n})_{n\in \mathbb {N} _{0}}}$ von Vektoren ${\displaystyle g_{n}\in V}$ rekursiv definieren durch

${\displaystyle g_{n+2}=g_{n+1}+g_{n},\quad n\geq 0}$.

Wie oben gilt dann die Formel

${\displaystyle g_{n}=f_{n}\cdot g_{1}+f_{n-1}\cdot g_{0},\quad n\geq 0}$.

Vektorraum der Fibonacci-Folgen

Wegen der Gleichung

${\displaystyle g_{n}=f_{n}\cdot g_{1}+f_{n-1}\cdot g_{0},\quad n\geq 0}$

ist die Menge der Folgen ${\displaystyle (g_{n})_{n\in \mathbb {N} _{0}}}$ mit ${\displaystyle g_{n+2}=g_{n+1}+g_{n}}$ ein zweidimensionaler Teilraum des unendlichdimensionalen ${\displaystyle \mathbb {C} }$-Vektorraums aller komplexen Folgen, wobei ${\displaystyle (f_{n})_{n\in \mathbb {N} _{0}}}$ und ${\displaystyle (f_{n-1})_{n\in \mathbb {N} _{0}}}$ (mit ${\displaystyle f_{-1}:=1}$) eine Basis bilden.