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

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.