TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/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<(\frac{7}{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<(\frac{7}{4}{)}^n$ für alle $n\in \mathbb{N}$
Induktionsbehauptung $F_{n+2}<(\frac{7}{4}{)}^{n+2}.$
Induktionsanfang
$F_0:0<1$
$F_1:1<\frac{7}{4}$

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

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

q.e.d.