Ist $F_{0}=0$ , $F_{1}=1$ und $F_{n+2}=F_{n+1}+F_{n}$ für alle $n\in \mathbb {N}$ , so gilt
$F_{n}={1 \over {\sqrt {5}}}{\Bigg [}{\Bigg (}{1+{\sqrt {5}} \over 2}{\Bigg )}^{n}-{\Bigg (}{1-{\sqrt {5}} \over 2}{\Bigg )}^{n}{\Bigg ]}$

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Lösung[Bearbeiten | Quelltext bearbeiten]

Induktionsvoraussetzung
$F_{n}={1 \over {\sqrt {5}}}[\left({1+{\sqrt {5}} \over 2}\right)^{n}-\left({1-{\sqrt {5}} \over 2}\right)^{n}]$ für $n\in \mathbb {N}$
in weiterer Folge verwende ich:
$a:=({1+{\sqrt {5}} \over 2})$
$b:=({1-{\sqrt {5}} \over 2})$
womit man die I.V. schreiben kann als $F_{n}={1 \over {\sqrt {5}}}[a^{n}-b^{n}]$
Induktionsbehauptung

$F_{n+2}={1 \over {\sqrt {5}}}[a^{n+2}-b^{n+2}]$

Induktionsanfang

Da wir von den vorherigen beiden auf das nächste schließen, müssen wir es für die ersten beiden zeigen.

$F_{0}={1 \over {\sqrt {5}}}(a^{0}-b^{0})={1 \over {\sqrt {5}}}(1-1)=0$
$F_{1}={1 \over {\sqrt {5}}}(a^{1}-b^{1})={1 \over {\sqrt {5}}}[({1+{\sqrt {5}} \over 2})^{1}-({1-{\sqrt {5}} \over 2})^{1}]={1 \over {\sqrt {5}}}[({1+{\sqrt {5}}-1+{\sqrt {5}} \over 2})]=1$

Induktionsschritt $F_{n}\land F_{n+1}\implies F_{n+2}$

(I) $F_{n+2}={1 \over {\sqrt {5}}}[a^{n+2}-b^{n+2}]$
(II) $F_{n+2}=F_{n+1}+F_{n}={1 \over {\sqrt {5}}}[a^{n+1}-b^{n+1}]+{1 \over {\sqrt {5}}}[a^{n}-b^{n}]$

${1 \over {\sqrt {5}}}[a^{n+1}-b^{n+1}]+{1 \over {\sqrt {5}}}[a^{n}-b^{n}]={1 \over {\sqrt {5}}}[a^{n+2}-b^{n+2}]$
kürzen von ${1 \over {\sqrt {5}}}$ .
$a^{n}-b^{n}+a^{n+1}-b^{n+1}=a^{n+2}-b^{n+2}$

umformen

$a^{n}+a^{n+1}-a^{n+2}=b^{n}+b^{n+1}-b^{n+2}$

$a^{n}$ bzw. $b^{n}$ herausheben

$a^{n}(1+a-a^{2})=b^{n}(1+b-b^{2})$

Jetzt muss bewiesen werden, dass die obige Aussage stimmt.
linke Seite: $a^{n}(1+a-a^{2})$
rechte Seite: $b^{n}(1+b-b^{2})$

linke Seite: wir betrachten nur $(1+a-a^{2})$ und setzen ein:
$[1+({1+{\sqrt {5}} \over 2})-({1+{\sqrt {5}} \over 2})^{2}]={4+2+2{\sqrt {5}}-6-2{\sqrt {5}} \over 4}=0$

rechte Seite: wir betrachten nur $(1+b-b^{2})$ und setzen ein:
$[1+({1-{\sqrt {5}} \over 2})-({1-{\sqrt {5}} \over 2})^{2}]={4+2-2{\sqrt {5}}-6+2{\sqrt {5}} \over 4}=0$

$a^{n}*0=b^{n}*0$

$0=0$

q.e.d.

Alternativer Induktionsschritt

$a={\frac {1+{\sqrt {5}}}{2}}$

$b={\frac {1-{\sqrt {5}}}{2}}$

In Rekursion ist die Induktion schon drinnen

$F_{n+2}=F_{n+1}+F_{n}$

I.V. Einsetzen

${\frac {1}{\sqrt {5}}}(a^{n+2}-b^{n+2}){\overset {!}{=}}{\frac {1}{\sqrt {5}}}(a^{n+1}-b^{n+1})+{\frac {1}{\sqrt {5}}}(a^{n}-b^{n})$

Kürzen

$a^{n+2}-b^{n+2}{\overset {!}{=}}a^{n+1}-b^{n+1}+a^{n}-b^{n}$

Auf gleiche Seite bringen

$a^{n+2}-a^{n}-a^{n+1}{\overset {!}{=}}-b^{n+1}-b^{n}+b^{n+2}$

Herausheben

$a^{n}(a^{2}-1-a^{1}){\overset {!}{=}}b^{n}(-b^{1}-1+b^{2})$

Definition von a und b

$({\frac {1+{\sqrt {5}}}{2}})^{n}(({\frac {1+{\sqrt {5}}}{2}})^{2}-1-{\frac {1+{\sqrt {5}}}{2}}){\overset {!}{=}}({\frac {1-{\sqrt {5}}}{2}})^{n}(-{\frac {1-{\sqrt {5}}}{2}}-1+({\frac {1-{\sqrt {5}}}{2}})^{2})$

Nebenrechnung

$({\frac {1+{\sqrt {5}}}{2}})^{2}={\frac {(1+{\sqrt {5}})^{2}}{2^{2}}}={\frac {1+2\,{\sqrt {5}}+5}{4}}={\frac {6+2\,{\sqrt {5}}}{4}}$

$({\frac {1-{\sqrt {5}}}{2}})^{2}={\frac {(1-{\sqrt {5}})^{2}}{2^{2}}}={\frac {1-2\,{\sqrt {5}}+5}{4}}={\frac {6-2\,{\sqrt {5}}}{4}}$

Alles auf /4 Brüche bringen

$({\frac {2+2\,{\sqrt {5}}}{4}})^{n}({\frac {6+2\,{\sqrt {5}}}{4}}-{\frac {4}{4}}-{\frac {2+2\,{\sqrt {5}}}{4}}){\overset {!}{=}}({\frac {2-2\,{\sqrt {5}}}{4}})^{n}(-{\frac {2-2\,{\sqrt {5}}}{4}}-{\frac {4}{4}}+{\frac {6-2\,{\sqrt {5}}}{4}})$

$({\frac {2+2\,{\sqrt {5}}}{4}})^{n}({\frac {6+2\,{\sqrt {5}}-4-2-2\,{\sqrt {5}}}{4}}){\overset {!}{=}}({\frac {2-2\,{\sqrt {5}}}{4}})^{n}({\frac {-2+2\,{\sqrt {5}}-4+6-2\,{\sqrt {5}}}{4}})$

$({\frac {2+2\,{\sqrt {5}}}{4}})^{n}({\frac {0}{4}}){\overset {!}{=}}({\frac {2-2\,{\sqrt {5}}}{4}})^{n}({\frac {-2+2\,{\sqrt {5}}-4+6-2\,{\sqrt {5}}}{4}})$