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

From VoWi
< TU Wien:Algebra und Diskrete Mathematik UE (diverse)‎ | Übungen SS19
Revision as of 17:46, 7 March 2019 by Gittenborg (talk | contribs) (Gittenborg verschob die Seite TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen WS18/Beispiel 13 nach TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 13 und überschrieb dabei eine Weiterleitung: verschie…)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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

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.