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

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}<({7 \over 4})^{n}.$

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}<({7 \over 4})^{n}$ für alle $n\in \mathbb {N}$
Induktionsbehauptung $F_{n+2}<({7 \over 4})^{n+2}.$
Induktionsanfang
$F_{0}:0<1$
$F_{1}:1<{7 \over 4}$

Induktionsschritt
(I) $F_{n+2}=F_{n+2}=F_{n}+F_{n+1}<({7 \over 4})^{n}+({7 \over 4})^{n+1}$
(II) $F_{n+2}<({7 \over 4})^{n+2}$

In (II) wird nun statt $F_{n+2}$ (I) eingesetzt.
$({7 \over 4})^{n}+({7 \over 4})^{n+1}<({7 \over 4})^{n+2}$
herausheben von $({7 \over 4})^{n}$
$({7 \over 4})^{n}*[1+({7 \over 4})]<({7 \over 4})^{n}*({7 \over 4})^{2}$
dividieren durch $({7 \over 4})^{n}$
$[1+({7 \over 4})]<({7 \over 4})^{2}$
$({44 \over 16})<({49 \over 16})$

q.e.d.