www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 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
Dt. Schulen im Ausland: Mathe-Seiten:

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 ^
www.vorhilfe.de