Rekursion und vollständige Induktion

29.08.2011, 13:02	Evelyn89	Auf diesen Beitrag antworten »
Rekursion und vollständige Induktion Hallo, Aufgabe: Sei $\begin{eqnarray} a_0=2, a_1=5 \end{eqnarray}$ und für $\begin{eqnarray} n \ge 2 \end{eqnarray}$ gelte die Rekursionsgleichung: $\begin{eqnarray} a_n = 5a_{n-1} - 6a_{n-2} \end{eqnarray}$ Beweisen Sie : $\begin{eqnarray} a_n=2^n + 3^n \end{eqnarray}$ Mein Ansatz: Da schon eine geschlossene Formel für die Rekursion gegeben ist, muss ich diese ja nicht mehr explizit bestimmmen. Also zeige ich lediglich, dass sie für alle $\begin{eqnarray} n \ge 2 \end{eqnarray}$ richtig ist und ich denke das macht man am besten mit der vollständigen Induktion. Induktionsanfang: n=2 $\begin{eqnarray} a_2=5a_1-6a_0=5 \cdot 5 - 6\cdot 12 = 13 = 2^2+3^2 \end{eqnarray}$ Induktionsvoraussetzung (I.V.) : Die Formel $\begin{eqnarray} a_n=2^n+3^n \end{eqnarray}$ erfülle die Rekursionsgleichung für ein $\begin{eqnarray} n \in \mathbb N \end{eqnarray}$ . Induktionsschritt : $\begin{eqnarray} n \to n+1 \end{eqnarray}$ $\begin{eqnarray} a_{n+1} = 5a_n - 6a_{n-1} \stackrel{I.V.}{=} 5(2^n+3^n)-6(2^{n-1}+3^{n-1})=2^{n+1}+3^{n+1} \end{eqnarray}$ Damit wäre alles gezeigt. Meine Frage ist nun, ob ich die Induktionsvoraussetzung richtig angewandt habe? Ist das so erlaubt? Denn ich habe sie auch für das $\begin{eqnarray} a_{n-1} \end{eqnarray}$ eingesetzt. Darf man das? Danke im voraus für eure Hilfe!
29.08.2011, 13:08	tigerbine	Auf diesen Beitrag antworten »
Sehr gut aufgepasst. Schau mal hier rein http://de.wikipedia.org/wiki/Vollst%C3%A...Vorg.C3.A4ngern Nun kannst du die Lücke schließen.
29.08.2011, 19:14	Evelyn89	Auf diesen Beitrag antworten »
Alles klar! Dankeschön tigerbine. Wenn ich also auch noch den Induktionsanfang für n=3 zeige, wäre die Lösung so vollständig? Ich ergänze dann beim Induktionsanfang dann noch: I.A.: n=3 $\begin{eqnarray} a_3=5a_2- 6a_1= 5 \cdot 13 - 6 \cdot 5= 35 = 2^3 + 3^3 \end{eqnarray}$ Wäre das so in Ordnung?
29.08.2011, 19:17	tigerbine	Auf diesen Beitrag antworten »
Genau.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »