Induktion: Eine Folge natürlicher Zahlen sei wie folgt definiert:

Question

Text erkannt:

6. Aufgabe: (6 Punkte) [Induktion]

Eine Folge \( a_{0}, a_{1}, a_{2} \ldots \) natürlicher Zahlen sei wie folgt definiert:
\( \begin{array}{l} a_{0}=2 \\ a_{1}=1 \\ a_{n}=a_{n-1}+a_{n-2} \text { für } n \geq 2 \end{array} \)

Zeigen Sie induktiv:
\( \forall n \in \mathbb{N}_{0}: \quad a_{n} \leq 2^{n}+1 \)

Kann mir jemand erklären wie man diese Induktion durchführt?

Answer 1

Hallo,

Willkommen in der Mathelounge!

Kann mir jemand erklären wie man diese Induktion durchführt?

Beginne mit der Voraussetzung - hier z.B. mit \(n=0\)$$a_0 = 2 \le 2^0 + 1 = 2\space \checkmark$$das ist also erfüllt. Und da wir hier zwei Vorgänger benötigen prüfen wir dasselbe für \(a_1\)$$a_1 = 1 \le 2^1 + 1 = 3\space \checkmark$$Dann macht man den Schritt nach \(n+1\). Also schaut man sich \(a_{n+1}\) an$$a_{n+1} = a_n + a_{n-1}$$ nach der Vorausetzung (s.o.) kann man davon ausgehen, dass$$\begin{aligned}a_{n+1} &= a_n + a_{n-1}\\ &\le 2^n + 1 + 2^{n-1} + 1 \\ &= 2^n +  2^{n-1} + 2 \\&\le 2^n +  2^{n-1} + 2^{n-1} &&|\,\text{für}\space n\ge2\\&= 2^{n+1} \\&\le 2^{n+1} +1 \\ &\text{q.e.d} \end{aligned}$$Gruß Werner

Comments

Vielen Dank erstmal! Ich bin da aktuell noch ein wenig verwirrt im Bezug auf das Lösungsschema meines Professors für solche Induktionsaufgaben. Dabei wird angenommen, dass p(m) für m<n gilt, also kein Beweis für p(n+1) durchgeführt wird. Kann ich dann also genauso gut die Induktion nach dem gewöhnlichen Schema ( p(0) ∧ ∀n ∈ N0 p(n) → p(n + 1) ) durchführen?