matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
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 Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

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:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenUni-Analysis-InduktionRekursionsgleichung auflösen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
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 1h 32m 1. meister_quitte
Ind/Vollständige Induktion
Status vor 2h 29m 7. Chris84
DiffGlGew/Loesung DGL
Status vor 8h 08m 3. fred97
UAnaR1/Beweis reelle Zahlen
Status vor 13h 0m 12. fred97
DiffGlGew/Globaler Existenzsatz
Status vor 1d 2h 52m 1. homerq
SVektoren/Raumwinkel errechnen
^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]