6 Geschlossene Form

Wie in 1.1 bereits erwähnt, bilden Fibonacci-Folgen gewissermaßen einen Gegenpol zu den Zweierpotenzen.

Die Zweierpotenzen lassen sich durch b₀ : = 1; b_n : = b_n-1 + b_n-1 = 2b_n-1 definieren und bilden als geschlossene Form den Term b_n = 2ⁿ. Ist es auf ähnliche Weise möglich, die Fibonacci-Folge in eine geschlossene Form zu pressen? - Nun ja, manche Erkenntnis fällt vom Himmel, und manchmal muß man dazu etwas nachhelfen. Schießen wir also etwas Silberjodid in die Wolken und warten ab, was herunterkommt...

Der Ansatz lautet, f_n = xⁿ zu setzen, und wir erhalten damit aus der Rekursionsgleichung f_n = f_n-1 + f_n-2 die Gleichung xⁿ = x^n-1 + x^n-2, die (für x $\neq$ 0) zu x² = x + 1 äquivalent ist. Diese wiederum entspricht x² - x - 1 = 0, dem sogenannten »charakteristischen Polynom« der zugehörigen Rekursion. Wir ermitteln nun dessen Nullstellen, in dem wir eine quadratische Ergänzung auf beiden Seiten addieren:

(Die quadratische Ergänzung wird bestimmt durch den Ansatz (x + y)² = x² +2xy + y², wobei hier 2xy = - x gewünscht wird. Also y = - ${\frac{{1}}{{2}}}$.)

x² - x - 1 + (- $${\frac{{1}}{{2}}}$$)² = (- $${\frac{{1}}{{2}}}$$)²

$\Leftrightarrow$

(x - $${\frac{{1}}{{2}}}$$)² -1 = $${\frac{{1}}{{4}}}$$

// $\sqrt{{()}}$

$\Leftrightarrow$

x - $${\frac{{1}}{{2}}}$$ = ±$$\sqrt{{\frac{5}{4}}}$$

$\Leftrightarrow$

x = $${\frac{{1}}{{2}}}$$±$${\frac{{\sqrt{5}}}{{2}}}$$

$\Leftrightarrow$

x = $${\frac{{1\pm\sqrt{5}}}{{2}}}$$

Wie man es bei quadratischen Gleichungen nicht anders erwarten kann, erhalten wir zwei Lösungen. Nun ja, wir haben ja auch zwei Startwerte f₀ und f₁, die wir bisher noch nicht ins Spiel gebracht haben. Versuchen wir eine Linearkombination der beiden Lösungen, um eine von den Startwerten abhängige geschlossene Form zu erhalten⁶:

f_n = a ^. ($${\frac{{1+\sqrt{5}}}{{2}}}$$)ⁿ + b ^. ($${\frac{{1-\sqrt{5}}}{{2}}}$$)ⁿ

Für f₀, also n = 0 erhalten wir daraus f₀ = a ^. (${\frac{{1+\sqrt{5}}}{{2}}}$)⁰ + b ^. (${\frac{{1-\sqrt{5}}}{{2}}}$)⁰ = a + b. Für f₁ ergibt sich f₁ = a ^. (${\frac{{1+\sqrt{5}}}{{2}}}$) + b ^. (${\frac{{1-\sqrt{5}}}{{2}}}$). Das ist ein lineares Gleichungssystem mit zwei Gleichungen und zwei Unbekannten und sollte sich daher lösen lassen:

Mit b = f₀ - a (aus der ersten Gleichung) ergibt sich eingesetzt in die zweite

f₁ = a$${\frac{{1+\sqrt{5}}}{{2}}}$$ + (f₀ - a)$${\frac{{1-\sqrt{5}}}{{2}}}$$

$\Leftrightarrow$

f₁ = a$${\frac{{1+\sqrt{5}}}{{2}}}$$ + f₀$${\frac{{1-\sqrt{5}}}{{2}}}$$ - a$${\frac{{1-\sqrt{5}}}{{2}}}$$

$\Leftrightarrow$

f₁ = a$${\frac{{(1+\sqrt{5})-(1-\sqrt{5)}}}{{2}}}$$ + f₀$${\frac{{1-\sqrt{5}}}{{2}}}$$

$\Leftrightarrow$

f₁ = a$$\sqrt{{5}}$$ + f₀$${\frac{{1-\sqrt{5}}}{{2}}}$$

$\Leftrightarrow$

a$$\sqrt{{5}}$$ = f₁ - f₀$${\frac{{1-\sqrt{5}}}{{2}}}$$

$\Leftrightarrow$

a = $${\frac{{f_{1}-f_{0}\frac{1-\sqrt{5}}{2}}}{{\sqrt{5}}}}$$

.

Für die Fibonacci-Folge F_n mit F₀ = 0 und F₁ = 1 ergibt dies a = ${\frac{{1}}{{\sqrt{5}}}}$ und b = 0 - a = - ${\frac{{1}}{{\sqrt{5}}}}$, also F_n = ${\frac{{1}}{{\sqrt{5}}}}$(${\frac{{1+\sqrt{5}}}{{2}}}$)ⁿ - ${\frac{{1}}{{\sqrt{5}}}}$(${\frac{{1-\sqrt{5}}}{{2}}}$)ⁿ = ${\frac{{(1+\sqrt{5})^{n}}}{{\sqrt{5}\cdot2^{n}}}}$ - ${\frac{{(1-\sqrt{5})^{n}}}{{\sqrt{5}\cdot2^{n}}}}$ = ${\frac{{(1+\sqrt{5})^{n}-(1-\sqrt{5})^{n}}}{{\sqrt{5}\cdot2^{n}}}}$.

Unter Berücksichtigung der Tatsache, daß (1 + $\sqrt{{5}}$) - (1 - $\sqrt{{5}}$) = 2 ^. $\sqrt{{5}}$ ist, ergibt sich F_n = ${\frac{{(1+\sqrt{5})^{n}-(1-\sqrt{5})^{n}}}{{(1+\sqrt{5})-(1-\sqrt{5})}}}$ ^. (${\frac{{1}}{{2}}}$)^n-1 = ${\frac{{(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n}}}{{\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}}}}$ die sogenannte »binetsche Darstellung« der Fibonacci-Folge, die, wenn wir $\lambda$ : = ${\frac{{1+\sqrt{5}}}{{2}}}$ und $\mu$ : = ${\frac{{1-\sqrt{5}}}{{2}}}$ setzen, in der Form F_n = ${\frac{{\lambda^{n}-\mu^{n}}}{{\lambda-\mu}}}$ besonders einprägsam ist.

Unter Anwendung von 4.1.2 erhalten wir beinahe unmittelbar auch deren allgemeine geschlossene Darstellung geschenkt:

f_n = F_nf₁ + F_n-1f₀ = f₁$${\frac{{\lambda^{n}-\mu^{n}}}{{\lambda-\mu}}}$$ + f₀$${\frac{{\lambda^{n-1}-\mu^{n-1}}}{{\lambda-\mu}}}$$ = $${\frac{{f_{1}\lambda^{n}-f_{1}\mu^{n}+f_{0}\lambda^{n-1}-f_{0}\mu^{n-1}}}{{\lambda-\mu}}}$$

= $${\frac{{(f_{1}\lambda^{n}+f_{0}\lambda^{n-1})-(f_{1}\mu^{n}+f_{0}\mu^{n-1})}}{{\lambda-\mu}}}$$ = $${\frac{{(f_{1}+\frac{f_{0}}{\lambda})\lambda^{n}-(f_{1}+\frac{f_{0}}{\mu})\mu^{n}}}{{\lambda-\mu}}}$$