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

$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 $\varphi$ gilt:

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

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

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

und

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

$={\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

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

so dass schließlich die Formel von Moivre-Binet

$\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 $n$-te Fibonacci-Zahl lautet für ganze Zahlen (siehe oben):

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

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

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

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

Ist $n$ eine ganze Zahl, dann gilt jedoch:

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

Deshalb ist die stetige und analytische Funktion

$\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 $(g_{n})_{n\in \mathbb {N} _{0}}$ eine Folge in $\mathbb {C}$, die für $n\geq 0$ durch das rekursive Bildungsgesetz

$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 $g_{0}=0$ und $g_{1}=1$ setzt. Für das $n$-te Folgenglied dieser Folge gibt es einen geschlossenen Ausdruck:

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

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

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

und Induktionsschritt

$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 $V$ ein Vektorraum und sind $g_{0},g_{1}\in V$, kann man eine Folge $(g_{n})_{n\in \mathbb {N} _{0}}$ von Vektoren $g_{n}\in V$ rekursiv definieren durch

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

Wie oben gilt dann die Formel

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

Vektorraum der Fibonacci-Folgen

Wegen der Gleichung

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

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