MathePrisma Logo

Rekursive Folgen

Rekursive Folgen

vollständige Induktion

Wir beweisen die Formel für die Fibonacci-Zahlen ebenfalls per Induktion.

Der Beweis sieht auf den ersten Blick vielleicht etwas gefährlich aus. Aber wenn man die einzelnen Schritte nachrechnet, dann merkt man, dass es sich nur um einfache Umformungen von großen Termen handelt.

Die Fibonacci-Zahlen




Achtung! Hier gibt es zwei Startwerte.

Vor.:   F(1)=1, F(2)=1 und F(n+2)=F(n+1)+F(n) für alle n>2
\(\tau_1 = \frac{1 + \sqrt{5}}{2} \qquad \tau_1 = \frac{1 - \sqrt{5}}{2}\)
\(\tau_1 + \tau_2 = 1, \qquad \tau_1 - \tau_2 = \sqrt{5}, \qquad \tau_1 \cdot \tau_2 = -1\)
Beh.:   F(n) = \(\frac{\tau_1^n - \tau_2^n}{\sqrt{5}}\)
Beweis:
Ind.-Anf.:
F(1) = \(\frac{\tau_1 - \tau_2}{\sqrt{5}} = \frac{\sqrt{5}}{\sqrt{5}}=1\) ist wahr.
F(2) = \(\frac{\tau_1^2 - \tau_2^2}{\sqrt{5}}=\frac{(\tau_1 + \tau_2)(\tau_1 - \tau_2)}{\sqrt{5}}=\frac{1 \cdot \sqrt{5}}{\sqrt{5}}=1\) ist wahr.
Ind.-Vor.:
F(k-1) = \(\frac{\tau_1^{k-1} - \tau_2^{k-1}}{\sqrt{5}}\)
F(k) = \(\frac{\tau_1^k - \tau_2^k}{\sqrt{5}}\)
Ind.-Schluss:
Von k-1 und k nach k+1 schließen.
Ind,-Bew.:
F(k+1)
= F(k)+F(k-1) (nach Voraussetzung)
\(= \frac{\tau_1^k - \tau_2^k}{\sqrt{5}} + \frac{\tau_1^{k-1} - \tau_2^{k-1}}{\sqrt{5}}\)
\(= \frac{1}{\sqrt{5}}(\tau_1^k + \tau_1^{k-1} - \tau_2^k - \tau_2^{k-1})\)
\(= \frac{1}{\sqrt{5}}(\tau_1^k(1 + \frac{1}{\tau_1}) - \tau_2^k ( 1+ \frac{1}{\tau_2}))\)
\(= \frac{1}{\sqrt{5}}(\tau_1^k(1 - \tau_2) - \tau_2^k ( 1 - \tau_1))\)
\(= \frac{1}{\sqrt{5}}(\tau_1^k \cdot \tau_1 - \tau_2^k \cdot \tau_2)\)
\(= \frac{\tau_1^{k+1} - \tau_2^{k+1}}{\sqrt{5}}\)

Damit gilt F(n) = \(\frac{\tau_1^n - \tau_2^n}{\sqrt{5}}\) für alle n.