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


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