TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 43

Aufgabe

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}.$

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.