Rekursionsgleichung auflösen < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 07:47 Do 18.10.2018 | | Autor: | Hela123 |
| Aufgabe | Betrachten Sie folgende Rekursionsgleichung [mm]T: \IN \rightarrow \IN[/mm] mit:
[mm]T(n)=\left\{\begin{matrix}
1, & \mbox{falls }n=0\mbox \\
T(n-1)+3n+5, & \mbox{falls }n \ge 1
\end{matrix}\right.[/mm]
Stellen Sie eine Vermutung für eine geschlossene Form dieser Rekursionsgleichung auf und beweisen Sie diese per Induktion. |
Hallo Forum,
ich habe Schwierigkeiten mit dem 1. Teil der Aufgabe. Rekursionsgleichung in geschlossener Form heißt quasi, dass wir die Rekursionsgleichung in einer Formel unterbringen. Wir haben das leider nicht gelernt deswegen weiß ich gar nicht, wie man diese Form ermitteln könnte.
Ich habe mir erstmal angeschaut, wie T(n) bei verschiedenen n aussieht:
n=0 T(n)=1
n=1 T(n)=1+3+5=9
n=2 T(n)=9+6+5=20
n=3 T(n)=20+9+5=34
n=4 T(n)=34+12+5=51
Aber irgendwie sehe ich keine Gesetzmäßigkeit drin.
Kann mir vielleicht jemand helfen?
Gibt es vielleicht für dieses Problem (Rekursionsgleichung in geschlossene Form bringen) eine bestimmte Vorgehensweise?
Danke im Voraus!
Hela123
|
|
| |
|
Du bist auf dem richtigen Weg.
> n=0 T(n)=1
> n=1 T(n)=1+3+5=9
> n=2 T(n)=9+6+5=20
> n=3 T(n)=20+9+5=34
> n=4 T(n)=34+12+5=51
Betrachte die Differenzenfolge der Ergebnisse. Diese lauten 8, 11, 14,17,20,23,26,...
Davon die Differenzenfolge lautet immer 3, ist also konstant.
Das wiederum bedeutet, dass die ursprüngliche Folge als Quadratische Funktion geschrieben werden kann. Regel: Ist bei der Folge [mm] a_n [/mm] die k-te Differenzenfolge konstant (also hier die 2.), so lässt sich die Folge als Polynom k-ten Grades darstellen.
Mache also den Ansatz [mm] a_n=an^2+bn+c [/mm] und setze einige Zahlen ein, um a, b und c zu finden.
(Lösung: [mm] a_n=1,5 n^2 [/mm] + 6,5 n +1 )
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:11 Do 18.10.2018 | | Autor: | Hela123 |
Hallo HJKweseleit,
vielen Dank für deine hilfreiche Antwort!
> Betrachte die Differenzenfolge der Ergebnisse. Diese lauten
> 8, 11, 14,17,20,23,26,...
>
> Davon die Differenzenfolge lautet immer 3, ist also
> konstant.
>
> Das wiederum bedeutet, dass die ursprüngliche Folge als
> Quadratische Funktion geschrieben werden kann. Regel: Ist
> bei der Folge [mm]a_n[/mm] die k-te Differenzenfolge konstant (also
> hier die 2.), so lässt sich die Folge als Polynom k-ten
> Grades darstellen.
Super, genau nach solcher Regel habe ich gesucht, danke!
> Mache also den Ansatz [mm]a_n=an^2+bn+c[/mm] und setze einige Zahlen
> ein, um a, b und c zu finden.
>
> (Lösung: [mm]a_n=1,5 n^2[/mm] + 6,5 n +1 )
Das habe ich auch rausbekommen.
Jetzt Beweis mit vollständiger Induktion.
IA: n = 0
[mm]a_n = 1,5 * 0^2 + 6,5* 0 + 1 = 1[/mm]
Also erfüllt.
IV: [mm]a_n = 1,5 n^2 + 6,5 n + 1 [/mm]
IS: n -> n+1
[mm]a_{n+1} = 1,5 (n+1)^2 + 6,5 (n+1) + 1[/mm]
[mm] = 1,5 (n^2+2n+1) + 6,5n + 6,5 + 1[/mm]
[mm] = 1,5n^2 + 3n + 1,5 + 6,5n + 6,5 + 1[/mm]
[mm] = (1,5n^2 + 6,5n + 1) + 3n + 8 [/mm]
[mm] = a_n + 3n + 8 [/mm]
Und ab hier bin ich mir nicht mehr sicher. Wir sollten doch ein Term: [mm] a_n + 3n + 5 [/mm] bekommen, damit Beweis vollständig ist, oder?
Ich sehe aber nicht den Fehler...Was mache ich falsch? Oder vielleicht ist die Schlüssfolgerung falsch?
Noch mal danke und viele Grüße
Hela123
|
|
|
| |
|
> Jetzt Beweis mit vollständiger Induktion.
>
> IA: n = 0
> [mm]a_n = 1,5 * 0^2 + 6,5* 0 + 1 = 1[/mm]
> Also erfüllt.
>
> IV: [mm]a_n = 1,5 n^2 + 6,5 n + 1[/mm]
>
> IS: n -> n+1
> [mm]a_{n+1} = 1,5 (n+1)^2 + 6,5 (n+1) + 1[/mm]
> [mm]= 1,5 (n^2+2n+1) + 6,5n + 6,5 + 1[/mm]
> [mm]= 1,5n^2 + 3n + 1,5 + 6,5n + 6,5 + 1[/mm]
> [mm]= (1,5n^2 + 6,5n + 1) + 3n + 8[/mm]
> [mm]= a_n + 3n + 8[/mm]
>
> Und ab hier bin ich mir nicht mehr sicher. Wir sollten doch
> ein Term: [mm]a_n + 3n + 5[/mm] bekommen, damit Beweis vollständig
> ist, oder?
> Ich sehe aber nicht den Fehler...Was mache ich falsch?
> Oder vielleicht ist die Schlüssfolgerung falsch?
Zunächst: Eigentlich gehst du logisch falsch vor.
Du hast eine Vorgabe, die du als richtig ansehen sollst, und eine neue Behauptung, deren Richtigkeit du nun mit VI zeigen willst. Dann darfst du zwar im Induktionsschritt davon ausgehen, dass die neue Formel für [mm] a_{n-1} [/mm] stimmt, aber nicht auch schon für [mm] a_n.
[/mm]
Induktionsverankerung: n=0 [mm] \Rightarrow a_n=a_0=1,5*0^2+6,5*0+1=1 [/mm] stimmt.
Induktionsschritt:
[mm] a_{n}=a_{n-1}+3n+5
[/mm]
[mm] =1,5(n-1)^2+6,5(n-1)+1+3n+5
[/mm]
[mm] =1,5n^2-3n+1,5+6,5n-6,5+1+3n+5
[/mm]
[mm] =1,5n^2+6,5n+1 [/mm]
Stattdessen kannst du aber auch, wie du es getan hast, von [mm] a_n [/mm] auf [mm] a_{n+1} [/mm] schließen:
Induktionsschritt:
[mm] a_{n+1}=a_n+3(n+1)+5 [/mm] (*)
[mm] =1,5n^2+6,5n+1+3(n+1)+5
[/mm]
[mm] =1,5n^2+6,5n+1+3n+3+5
[/mm]
[mm] =1,5n^2+3n+1,5+6,5n+6,5+1
[/mm]
[mm] =1,5(n+1)^2+6,5(n+1)+1
[/mm]
Bei (*) oder spätestens in der letzten Zeile merkst du aber, wo dein eigentlicher Fehler liegt:
Sobald der Index sich ändert, musst du auch aus n ein n+1 oder n-1 machen, damit noch alles stimmt.
Ich gehe deshalb nochmal deinen Beweis durch. Er besagt: Wenn die Formel [mm] a_n=1,5n^2+6,5n+1 [/mm] gilt, dann ist (mit [mm] T(n)=a_n)
[/mm]
$ [mm] T(n)=\left\{\begin{matrix} 1, & \mbox{falls }n=0\mbox \\ T(n-1)+3n+5, & \mbox{falls }n \ge 1 \end{matrix}\right. [/mm] $
[mm] a_0 [/mm] ist klar.
IV: [mm]a_n = 1,5 n^2 + 6,5 n + 1[/mm]
IS: n -> n+1
[mm]a_{n+1} = 1,5 (n+1)^2 + 6,5 (n+1) + 1[/mm]
[mm]= 1,5 (n^2+2n+1) + 6,5n + 6,5 + 1[/mm]
[mm]= 1,5n^2 + 3n + 1,5 + 6,5n + 6,5 + 1[/mm]
[mm]= (1,5n^2 + 6,5n + 1) + 3n \red{+ 3 + 5}[/mm]
[mm]= a_n + 3\red{(}n \red{+ 1 )}+ 5[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:15 Do 18.10.2018 | | Autor: | Hela123 |
Hallo HJKweseleit,
vielen vielen Dank für deine ausführliche uns sehr hilfreiche Antwort!
Jetzt habe ich verstanden, was mein Fehler war und natürlich auch den Beweis.
Noch mal danke und viele Grüße
Hela123
|
|
|
|
