www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 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

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-Analysis-Induktion" - Rekursionsgleichung auflösen
Rekursionsgleichung auflösen < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Analysis-Induktion"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Rekursionsgleichung auflösen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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


        
Bezug
Rekursionsgleichung auflösen: Antwort
Status: (Antwort) fertig Status 
Datum: 09:48 Do 18.10.2018
Autor: HJKweseleit

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 )


Bezug
                
Bezug
Rekursionsgleichung auflösen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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


Bezug
                        
Bezug
Rekursionsgleichung auflösen: Antwort
Status: (Antwort) fertig Status 
Datum: 16:05 Do 18.10.2018
Autor: HJKweseleit


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



Bezug
                                
Bezug
Rekursionsgleichung auflösen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

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


Alle Foren
Status vor 5m 10. fred97
DiffGlGew/Globaler Existenzsatz
Status vor 1h 15m 3. meili
UNum/Skizzieren einer Menge
Status vor 1h 34m 5. Chris84
DiffGlGew/Loesung DGL
Status vor 2h 17m 2. leduart
ZahlTheo/Kleinstes gem. Vielfachaches
Status vor 3h 19m 3. Hela123
UAlgoDatstrukt/Eigenschaften Binärbäume
^ Seitenanfang ^
www.vorhilfe.de