www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Uni-Sonstiges" - Rekursion
Rekursion < Sonstiges < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Rekursion: spezielle Lösung
Status: (Frage) beantwortet Status 
Datum: 10:32 Mi 28.02.2018
Autor: sancho1980

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

        
Bezug
Rekursion: Antwort
Status: (Antwort) fertig Status 
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 $.



Bezug
        
Bezug
Rekursion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 00:48 Sa 03.03.2018
Autor: sancho1980

Kannst du das mal bitte vorrechnen?

Bezug
                
Bezug
Rekursion: Antwort
Status: (Antwort) fertig Status 
Datum: 05:09 Sa 03.03.2018
Autor: fred97


> Kannst du das mal bitte vorrechnen?


Ist das nicht  Deine Aufgabe  ?

Bezug
                        
Bezug
Rekursion: Frage (reagiert)
Status: (Frage) reagiert/warte auf Reaktion Status 
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.

Bezug
                                
Bezug
Rekursion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
                                        
Bezug
Rekursion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:11 Sa 03.03.2018
Autor: sancho1980

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!

Bezug
                                                
Bezug
Rekursion: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
                                                        
Bezug
Rekursion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:41 So 04.03.2018
Autor: sancho1980


> 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.

Bezug
                                                                
Bezug
Rekursion: Antwort
Status: (Antwort) fertig Status 
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]

Bezug
                                                        
Bezug
Rekursion: Tipp
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:54 So 04.03.2018
Autor: HJKweseleit

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.

Bezug
        
Bezug
Rekursion: Antwort
Status: (Antwort) fertig Status 
Datum: 16:00 So 04.03.2018
Autor: HJKweseleit

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]


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]