TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 13

Aus VoWi
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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\over4})] < ({7 \over 4})^{n}*({7 \over 4})^2
dividieren durch ({7 \over 4})^{n}
[1+({7\over4})] < ({7 \over 4})^2
({44\over16}) < ({49 \over 16})

q.e.d.