TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 11

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=\frac{1}{\sqrt{5}}\left[\right(\frac{1+\sqrt{5}}{2}{)}^n-\left(\frac{1-\sqrt{5}}{2}{)}^n\right]$

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

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

$F_{n+2}=\frac{1}{\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=\frac{1}{\sqrt{5}}(a^0-b^0)=\frac{1}{\sqrt{5}}(1-1)=0$
$F_1=\frac{1}{\sqrt{5}}(a^1-b^1)=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2}{)}^1-(\frac{1-\sqrt{5}}{2}{)}^1]=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}-1+\sqrt{5}}{2})]=1$

Induktionsschritt $F_n\wedge F_{n+1}⟹F_{n+2}$

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

$\frac{1}{\sqrt{5}}[a^{n+1}-b^{n+1}]+\frac{1}{\sqrt{5}}[a^n-b^n]=\frac{1}{\sqrt{5}}[a^{n+2}-b^{n+2}]$
kürzen von $\frac{1}{\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+(\frac{1+\sqrt{5}}{2})-(\frac{1+\sqrt{5}}{2}{)}^2]=\frac{4+2+2\sqrt{5}-6-2\sqrt{5}}{4}=0$

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

$a^n\ast 0=b^n\ast 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})\stackrel{!}{=}\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}\stackrel{!}{=}{a}^{n+1}-b^{n+1}+a^n-b^n$

Auf gleiche Seite bringen

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

Herausheben

$a^n(a^2-1-a^1)\stackrel{!}{=}{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})\stackrel{!}{=}(\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})\stackrel{!}{=}(\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})\stackrel{!}{=}(\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})\stackrel{!}{=}(\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})\stackrel{!}{=}(\frac{2-2\sqrt{5}}{4}{)}^n(\frac{0}{4})$

$0=0$

Links

Ähnliches Beispiel:

• TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 42 neue Nummerierung 18

• [1] - Beispiel 2)b)