Rekursion < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Zeigen Sie, dass eine spezielle Lösung von [mm] a_n [/mm] = [mm] c_1 a_{n-1} [/mm] + [mm] c_2 a_{n-2} [/mm] + [mm] g_n [/mm] gegeben ist durch [mm] i_n [/mm] = [mm] \summe_{k=1}^{n} s_{n-k} g_{k+1}, [/mm] n [mm] \ge [/mm] 1, wobei [mm] s_n [/mm] die Lösung der homogenen Rekursion mit den Anfangsbedingungen [mm] s_0 [/mm] = 0 und [mm] s_1 [/mm] = 1 ist. |
Hallo
ich weiß leider nicht so recht, wie ich da jetzt rangehe...
lg
Martin
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:58 Mi 28.02.2018 | | Autor: | fred97 |
> Zeigen Sie, dass eine spezielle Lösung von [mm]a_n[/mm] = [mm]c_1 a_{n-1}[/mm]
> + [mm]c_2 a_{n-2}[/mm] + [mm]g_n[/mm] gegeben ist durch [mm]i_n[/mm] =
> [mm]\summe_{k=1}^{n} s_{n-k} g_{k+1},[/mm] n [mm]\ge[/mm] 1, wobei [mm]s_n[/mm] die
> Lösung der homogenen Rekursion mit den Anfangsbedingungen
> [mm]s_0[/mm] = 0 und [mm]s_1[/mm] = 1 ist.
> Hallo
> ich weiß leider nicht so recht, wie ich da jetzt
> rangehe...
>
> lg
> Martin
Du musst nachrechnen, dass gilt:
$ [mm] i_n [/mm] = [mm] c_1 i_{n-1} [/mm] + [mm] c_2 i_{n-2} +g_n [/mm] $ für alle $n [mm] \in \IN_0$.
[/mm]
Dabei musst Du benutzen:
$ [mm] s_n [/mm] = [mm] c_1 s_{n-1} [/mm] + [mm] c_2 s_{n-2} [/mm] $ für alle $n [mm] \in \IN_0$
[/mm]
und $ [mm] s_0 [/mm] = 0$ und $ [mm] s_1 [/mm] = 1 $.
|
|
|
| |
|
Kannst du das mal bitte vorrechnen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 05:09 Sa 03.03.2018 | | Autor: | fred97 |
> Kannst du das mal bitte vorrechnen?
Ist das nicht Deine Aufgabe ?
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 07:14 Sa 03.03.2018 | | Autor: | sancho1980 |
Ich komme auf keinen grünen Zweig; meinst du einen induktiven Beweis?
M.E. lässt sich der, zumindest so wie von dir beschrieben, nicht durchführen. Du schreibst, ich soll "nachrechnen", dass gilt:
[mm] i_n [/mm] = [mm] c_1 i_{n-1} [/mm] + [mm] c_2 i_{n-2} [/mm] + [mm] g_n [/mm] für alle n [mm] \IN_0
[/mm]
Es handelt sich um eine Rekursion zweiter Ordnung, also sind [mm] i_0 [/mm] und [mm] i_1 [/mm] Anfangsbedingungen, also sind [mm] g_0 [/mm] und [mm] g_1 [/mm] m.E. nicht definiert.
Daher fragte ich mich, ob du dir die Aufgabenstellung richtig durchgelesen hast und wollte, dass du mal vorrechnest, was du beschrieben hast.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:17 Sa 03.03.2018 | | Autor: | chrisno |
Hallo,
Fang mal langsam an. Erkläre, was mit der Aussage
wobei $ [mm] s_n [/mm] $ die Lösung der homogenen Rekursion mit den Anfangsbedingungen $ [mm] s_0 [/mm] $ = 0 und $ [mm] s_1 [/mm] $ = 1 ist
gemeint ist.
|
|
|
| |
|
Na dass ich statt [mm] s_n [/mm] auch schreiben kann:
[mm] s_n [/mm] = [mm] c_1 s_{n-1} [/mm] + [mm] c_2 s_{n-2}
[/mm]
Somit gilt:
[mm] i_n [/mm] = [mm] (c_1 s_{n-2} [/mm] + [mm] c_2 s_{n-3}) g_2 [/mm] + ... + [mm] (c_1 s_1 [/mm] + [mm] c_2 s_0) g_{n-1} [/mm] + [mm] g_n
[/mm]
= [mm] (c_1 s_{n-2} [/mm] + [mm] c_2 s_{n-3}) g_2 [/mm] + ... + [mm] (c_1 s_2 [/mm] + [mm] c_2 s_1) g_{n-2} [/mm] + [mm] c_1 g_{n-1} [/mm] + [mm] g_n
[/mm]
= [mm] (c_1 s_{n-2} [/mm] + [mm] c_2 s_{n-3}) g_2 [/mm] + ... + [mm] (c_1 s_3 [/mm] + [mm] c_2 s_2) g_{n-3} [/mm] + [mm] (c_1 s_2 [/mm] + [mm] c_2) g_{n-2} [/mm] + [mm] c_1 g_{n-1} [/mm] + [mm] g_n
[/mm]
Und jetzt, wie weiter? Ich blick's nicht!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:23 So 04.03.2018 | | Autor: | chrisno |
damit habe ich Deinen Blick nicht in die richtige Richtung gelenkt. Mir wird ein Lösungsversuch mit Ausschreiben der Summen zu unübersichtlich.
Für wichtig halte ich im Moment, dass, wären da keine [mm] $g_n$, [/mm] es nichts zu tun gäbe. Also sind die [mm] $g_n$ [/mm] der Unterschied zur homogenen Rekursion, die Inhomogenitäten. Darum kann ich
"also sind $ [mm] g_0 [/mm] $ und $ [mm] g_1 [/mm] $ m.E. nicht definiert."
nicht nachvollziehen. Alle [mm] $g_n$ [/mm] sind als gegeben anzusetzen. Du musst zeigen, dass
$ [mm] \summe_{k=1}^{n} s_{n-k} g_{k+1} [/mm] = [mm] c_1\summe_{k=1}^{n-1} s_{n-k} g_{k+1} [/mm] + [mm] c_2 \summe_{k=1}^{n-2} s_{n-k} g_{k+1} [/mm] + [mm] g_n$
[/mm]
gilt. Wie das am geschicktesten geht, habe ich mir noch nicht überlegt. Eine Möglichkeit wäre, die Summenglieder mit gleichen [mm] $g_i$ [/mm] zu betrachten.
|
|
|
| |
|
> Du musst zeigen, dass
>
> [mm]\summe_{k=1}^{n} s_{n-k} g_{k+1} = c_1\summe_{k=1}^{n-1} s_{n-k} g_{k+1} + c_2 \summe_{k=1}^{n-2} s_{n-k} g_{k+1} + g_n[/mm]
>
> gilt.
Laut Aufgabenstellung gilt die Summenformel ja für n [mm] \ge [/mm] 1.
Wenn ich in deiner Gleichung jetzt n := 1 setze, dann bleibt da stehen:
0 = [mm] c_1 \summe_{k=1}^{0} s_{1-k} g_{k+1} [/mm] + [mm] c_2 \summe_{k=1}^{-1} s_{1-k} g_{k+1} [/mm] + [mm] g_1
[/mm]
Was will mir das sagen? Wenn ich
[mm] \summe_{k=1}^{0} s_{1-k} g_{k+1}
[/mm]
und
[mm] \summe_{k=1}^{-1} s_{1-k} g_{k+1}
[/mm]
wie eine for-Schleife interpretiere, die genau 0-mal durchlaufen wird, dann bleibt da stehen
0 = [mm] g_0.
[/mm]
Allerdings frage ich mich auch, ob die von dir genannte Formel so stimmt. Müsste sie richtigerweise nicht eher lauten:
[mm] \summe_{k=1}^{n} s_{n-k} g_{k+1} [/mm] = [mm] c_1\summe_{k=1}^{n-1} s_{(n-1)-k} g_{k+1} [/mm] + [mm] c_2 \summe_{k=1}^{n-2} s_{(n-2)-k} g_{k+1} [/mm] + [mm] g_n
[/mm]
??
Überlege, ob ich jetzt langsam mal die Autoren der Aufgabenstellung auf diesen Thread hier aufmerksam mache. Scheint ja, als wäre ich nicht der Einzige, der sich an der Aufgabe die Zähne ausbeißt ...
Edit:
Ich hab's raus: Es ist tatsächlich wie gesagt, die zu beweisende Gleichung lautet wohlkorrekterweise:
[mm] \summe_{k=1}^{n} s_{n-k} g_{k+1} [/mm] = [mm] c_1\summe_{k=1}^{n-1} s_{(n-1)-k} g_{k+1} [/mm] + [mm] c_2 \summe_{k=1}^{n-2} s_{(n-2)-k} g_{k+1} [/mm] + [mm] g_n
[/mm]
Trotzdem hat mich der Tipp mit der Gleichung weitergebracht. Im Prinzip ist das ja gleichbedeutend mit:
[mm] s_{n-1}g_2 [/mm] + ... + [mm] s_0g_{n+1} [/mm] = [mm] c_1(s_{n-2}g_2 [/mm] + ... + [mm] s_0g_n) [/mm] + [mm] c_2(s_{n-3}g_2 [/mm] + ... + [mm] s_0g_{n-1} [/mm] + [mm] g_n
[/mm]
Die linke Seite kann ich unter Berücksichtigung, dass [mm] s_0 [/mm] = 0 und [mm] s_1 [/mm] = 1 umformen:
= [mm] (c_1 s_{n-2} [/mm] + [mm] c_2 s_{n-3}g_2 [/mm] + ... + [mm] (c_1 s_{1} [/mm] + [mm] c_2 s_{0}g_{n-1} [/mm] + [mm] g_n
[/mm]
= [mm] (c_1 s_{n-2} g_2 [/mm] + [mm] c_2 s_{n-3} g_2 [/mm] + ... + [mm] (c_1 s_1 g_{n-1} [/mm] + [mm] c_2 s_0 g_{n-1}) [/mm] + [mm] g_n
[/mm]
= [mm] c_1(s_{n-2} g_2 [/mm] + ... + [mm] s_1 g_{n-1}) [/mm] + [mm] c_2(s_{n-3} g_2 [/mm] + ... + [mm] s_0 g_{n-1}) +g_n
[/mm]
Wieder unter Berücksichtigung, dass [mm] s_0 [/mm] = 0 erkennt man, dass das genau die rechte Seite der zu beweisenden Gleichung ist.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:32 So 04.03.2018 | | Autor: | chrisno |
> Allerdings frage ich mich auch, ob die von dir genannte
> Formel so stimmt. Müsste sie richtigerweise nicht eher
> lauten:
>
> [mm]\summe_{k=1}^{n} s_{n-k} g_{k+1}[/mm] = [mm]c_1\summe_{k=1}^{n-1} s_{(n-1)-k} g_{k+1}[/mm] + [mm]c_2 \summe_{k=1}^{n-2} s_{(n-2)-k} g_{k+1}[/mm] + [mm]g_n[/mm]
>
Da hast Du Recht.
[mm]\summe_{k=1}^{n} s_{n-k} g_{k+1}[/mm] =
da [mm] $s_0 [/mm] = 0$ ist dies gleich mit
[mm]\summe_{k=1}^{n-1} s_{n-k} g_{k+1}[/mm] =
da [mm] $s_1 [/mm] = 1$ ist dies gleich mit
[mm]\summe_{k=1}^{n-2} s_{n-k} g_{k+1} + g_n[/mm] =
da $ [mm] s_n [/mm] $ = $ [mm] c_1 s_{n-1} [/mm] $ + $ [mm] c_2 s_{n-2} [/mm] $ ist dies gleich mit
[mm]\summe_{k=1}^{n-2} \left( c_1 s_{n-k-1} + c_2 s_{n-k-2} \right) g_{k+1} + g_n[/mm] =
[mm]c_1\summe_{k=1}^{n-2} s_{(n-1)-k} g_{k+1}[/mm] + [mm]c_2 \summe_{k=1}^{n-2} s_{(n-2)-k} g_{k+1} + g_n[/mm] =
da [mm] $s_0 [/mm] = 0$ ist dies gleich mit
[mm]c_1\summe_{k=1}^{n-1} s_{(n-1)-k} g_{k+1}[/mm] + [mm]c_2 \summe_{k=1}^{n-2} s_{(n-2)-k} g_{k+1}[/mm] + [mm]g_n[/mm]
|
|
|
| |
|
Hier noch ein Tipp, der hoffentlich nicht kontraproduktiv ist.
Mir fiel auf, dass im Term
[mm] i_n=\summe_{k=1}^{n} s_{n-k} g_{k+1}
[/mm]
bereits für [mm] i_n [/mm] der Wert von [mm] g_{n+1} [/mm] vorkommt, wenn k=n ist, was doch sehr merkwürdig wäre. Tatsächlich ist dann aber [mm] s_{n-k} [/mm] = [mm] s_{0}=0, [/mm] d.h., der Summand mit k=n ist immer 0 und kann daher wegfallen.
Somit könnte man nun [mm] i_n=\summe_{k=1}^{n-1} s_{n-k} g_{k+1} [/mm] schreiben.
Hier mal ein Beispiel, wie das Ganze gemeint ist.
[mm] a_0=0
[/mm]
[mm] a_1=0
[/mm]
[mm] a_n=a_{n-1}+a_{n-2}+n
[/mm]
Damit erhält man nun
0
0
2
5
11
21
...
Nun bilden wir zunächst die ersten 5 Folgeglieder der homogenen Gleichung
[mm] s_n=s_{n-1}+s_{n-2}
[/mm]
mit
[mm] s_0=0
[/mm]
[mm] s_1=1
[/mm]
Daraus folgen
[mm] s_2=1
[/mm]
[mm] s_3=2
[/mm]
[mm] s_4=3
[/mm]
[mm] s_5=5
[/mm]
Damit erhalten wir für [mm] i_n [/mm] der Reihe nach
[mm] i_1=s_0g_2=0 [/mm] (hätte nach meiner obigen Bemerkung auch wegfallen können)
[mm] i_2=s_1g_2 (+s_0g_3)=2
[/mm]
[mm] i_3=s_2g_2+s_1g_3 (+s_0g_4)=2+3=5
[/mm]
[mm] i_4=s_3g_2+s_2g3+s_1g_4 (+s_0g_5)=4+3+4=11
[/mm]
[mm] i_5=s_4g_2+s_3g_3+s_2g4+s_1g_5 (+s_0g_6)=6+6+4+5=21
[/mm]
Das entspricht genau der obigen Folge der [mm] a_n [/mm] ab n=1.
ABER:
Wir bilden die selbe Rekursion mit anderen Startwerten:
[mm] a_0=0
[/mm]
[mm] a_1=1
[/mm]
[mm] a_n=a_{n-1}+a_{n-2}+n
[/mm]
Damit erhält man jetzt
0
1
3
7
13
25
...
also eine andere Folge. Die angegebene Folge mit den [mm] i_n [/mm] beschreibt also nur die Möglichkeit für eine bestimmte Startwertkonfiguration.
|
|
|
| |
|
Hallo Martin,
nachdem ich dir meinen Tipp geschickt habe, konnte ich den Beweis konstruieren, da er genau diese Ideen enthält.
Behauptung:
Für
[mm] i_0=0
[/mm]
[mm] i_1=0
[/mm]
[mm] i_n=A*i_{n-1}+B*i_{n-2}+g_i
[/mm]
(gleich benötigt: [mm] i_2=g_2 [/mm] und [mm] i_3=Ag_2+g_3)
[/mm]
sowie
[mm] s_0=0
[/mm]
[mm] s_1=1
[/mm]
[mm] s_n=A*s_{n-1}+B*s_{n-2}
[/mm]
(gleich benötigt: [mm] s_2=A)
[/mm]
gilt: [mm] i_n=\summe_{k=1}^{n}s_{n-k}g_{k+1} [/mm] für [mm] i\ge [/mm] 1.
Zunächst zeige ich, dass dies für n=1,2 und 3 gilt, um keine Probleme mit der Indizierung zu bekommen.
Nach der Summenformel wären nun
[mm] i_1=\summe_{k=1}^{1}s_{1-k}g_{k+1}=s_0g_2=0*g_2=0 [/mm] (stimmt),
[mm] i_2=\summe_{k=1}^{2}s_{2-k}g_{k+1}=s_1g_2+s_0g_3=1*g_2+0*g_3=g_2 [/mm] (stimmt),
[mm] i_3=\summe_{k=1}^{3}s_{3-k}g_{k+1}=s_2g_2+s_1g_3+s_0*g_4=A*g_2+1*g_3+0*g_4=A*g_2+g_3 [/mm] (stimmt).
Jetzt der entscheidende Schritt für [mm] n\ge [/mm] 4:
[mm] i_n=A*i_{n-1}+B*i_{n-2}+g_i
[/mm]
= [mm] A*\summe_{k=1}^{n-1}s_{n-1-k}g_{k+1}+B*\summe_{k=1}^{n-2}s_{n-2-k}g_{k+1}+ g_n [/mm] (in der ersten Summe können wir den letzten Summanden weglassen, da er [mm] s_{n-2-(n-2)}g_{(n-2)+1}=s_{0}g_{n-1}=0 [/mm] ist)
= [mm] A*\summe_{k=1}^{n-2}s_{n-1-k}g_{k+1}+B*\summe_{k=1}^{n-2}s_{n-2-k}g_{k+1}+ g_n
[/mm]
= [mm] \summe_{k=1}^{n-2}(A*s_{n-1-k}+B*s_{n-2-k})g_{k+1}+ g_n [/mm] (und nach Definition von [mm] s_n)
[/mm]
= [mm] \summe_{k=1}^{n-2}s_{n-k}g_{k+1}+ g_n [/mm] (da [mm] s_1 [/mm] nach Definition =1 ist, ergibt sich)
= [mm] \summe_{k=1}^{n-2}s_{n-k}g_{k+1}+ s_{n-(n-1)}g_n
[/mm]
= [mm] \summe_{k=1}^{n-1}s_{n-k}g_{k+1} [/mm] (und nun noch, da [mm] s_0=0 [/mm] ist)
= [mm] \summe_{k=1}^{n}s_{n-k}g_{k+1}
[/mm]
|
|
|
|
