Rekursiongleichung

Aufrufe: 966     Aktiv: 28.06.2019 um 18:37

0

Hi, es geht um folgende Aufgabe.

 

Soweit ich weiß ist das eine Lineare, inhomogene Rekursion 2. Ordnung.

Eine allgemeine Lösung wäre: an = hn +in

wobei hn = c1*hn-1 + c2*hn-2

und in = spezielle Lösung der inhomogenen Rekursion.

 

Ich verstehe nicht, wie man "in" berechnet, beziehungsweise wie man mit 2^n-2 umgehen soll.

Diese Frage melden
gefragt

Student, Punkte: 10

 
Kommentar schreiben
3 Antworten
0

Hallo,

entschuldige nochmals, dass ich die falsche Folge genommen habe. Bei dir müsste die explizite Form

$$t_n=2^n-(n+1)$$

sein, was du durch Vergleich von \(2^n\) mit deiner Folge ziemlich leicht sehen kannst.

Der Beweis durch Einsetzen:

$$2t_{n-1}-t_{n-2}+2^{n-2}=2\Bigl(2^{n-1}-n\Bigr)-\Bigl(2^{n-2}-(n-1)\Bigr)+2^{n-2}$$

$$=2^{n}-2n-2^{n-2}+(n-1)+2^{n-2}$$

$$=2^{n}-2n+n-1=2^{n}-n-1=2^{n}-(n+1)=t_n$$

Ich hoffe, ich habe dich mit meiner anderen Antwort nicht zu sehr erschreckt! :D

Diese Antwort melden
geantwortet

Student, Punkte: 2.6K

 

Kommentar schreiben

0

Hallo,

ich habe gerade germerkt, dass ich ein kompletter Trottel bin und statt dem "-" ein "+" genommen habe. Ich hoffe die Ideen helfen dir trotzdem auch für deine Folge! :P

 

Du hast für \(n\geq2\) (wenn du falsch liest) die Gleichung:

$$t_n=2t_{n-1}+t_{n-2}+2^{n-2}$$

Du kannst dir ja mal ein paar Folgenglieder von \(t_n\) anschauen:

$$t_0=0\quad t_1=0\quad t_2=1\quad t_3=4\quad t_4=13\quad t_5=38\quad t_6=105\quad t_7=280\quad t_8=729$$

Wenn du zwei aufeinanderfolgende Folgenglieder durcheinander teilst siehst du, dass der Wert immer kleiner wird, aber immer mindestens \(2\) beträgt. Somit kommst du leider mit \(2^n\) nicht weiter (das hab ich verzweifelt probiert). Schau dir mal die Pell-Folge an. Die hat die Werte:

$$P_0=0\quad P_1=1\quad P_2=2\quad P_3=5\quad P_4=12\quad P_5=29\quad P_6=70\quad P_7=169\quad P_8=408$$

Sie hat fast das gleiche Verhalten wie deine Folge und die explizite Form:

$$\frac{(1+\sqrt{2})^n-(1-\sqrt{2})^n}{2\sqrt{2}}$$

Vielleicht merkt man erstmal nicht, dass sie fast das gleiche Verhalten hat, aber wenn wir sie um eins nach rechts verschieben, wird es vielleicht noch deutlicher. Wir betrachten also:

$$Q_n=\frac{(1+\sqrt{2})^{n+1}-(1-\sqrt{2})^{n+1}}{2\sqrt{2}}$$

Die Folgenwerte sind jetzt:

$$Q_0=1\quad Q_1=2\quad Q_2=5\quad Q_3=12\quad Q_4=29\quad Q_5=70\quad Q_6=169\quad Q_7=408$$

Die Differenz \(D\) zu deiner Folge sieht sehr vertraut aus:

$$D_0=1\quad D_1=2\quad D_2=4\quad D_3=8\quad D_4=16\quad D_5=32$$

Also gilt \(D_n=2^{n}\). Wenn wir also die Folge \(t_n=Q_n-D_n\) betrachten, hat sie die Werte:

$$t_0=0\quad t_1=0\quad t_2=1\quad t_3=4\quad t_4=13\quad t_5=38\quad t_6=105\quad t_7=280\quad t_8=729$$

Somit ist die explizite Form wohl:

$$t_n=\frac{(1+\sqrt{2})^{n+1}-(1-\sqrt{2})^{n+1}}{2\sqrt{2}}-2^n$$

Das muss jetzt noch bewiesen werden. Wir setzen die Folge in die Rekursionsgleichung ein und erhalten:

$$2t_{n-1}+t_{n-2}+2^{n-2}$$

$$=2\cdot\Bigl(\frac{(1+\sqrt{2})^{n}-(1-\sqrt{2})^{n}}{2\sqrt{2}}-2^{n-1}\Bigr)+\Bigl(\frac{(1+\sqrt{2})^{n-1}-(1-\sqrt{2})^{n-1}}{2\sqrt{2}}-2^{n-2}\Bigr)+2^{n-2}$$

$$=\frac{2(1+\sqrt{2})^{n}-2(1-\sqrt{2})^{n}}{2\sqrt{2}}-2^{n}+\frac{(1+\sqrt{2})^{n-1}-(1-\sqrt{2})^{n-1}}{2\sqrt{2}}$$

$$=\frac{2(1+\sqrt{2})^{n}+(1+\sqrt{2})^{n-1}}{2\sqrt{2}}-\frac{2(1-\sqrt{2})^{n}+(1-\sqrt{2})^{n-1}}{2\sqrt{2}}-2^{n}$$

$$=\frac{(2+2\sqrt{2})(1+\sqrt{2})^{n-1}+(1+\sqrt{2})^{n-1}}{2\sqrt{2}}-\frac{(2-2\sqrt{2})(1-\sqrt{2})^{n-1}+(1-\sqrt{2})^{n-1}}{2\sqrt{2}}-2^{n}$$

$$=\frac{(1+2\sqrt{2}+2)(1+\sqrt{2})^{n-1}}{2\sqrt{2}}-\frac{(1-2\sqrt{2}+2)(1-\sqrt{2})^{n-1}}{2\sqrt{2}}-2^{n}$$

$$=\frac{(1+\sqrt{2})^2(1+\sqrt{2})^{n-1}}{2\sqrt{2}}-\frac{(1-\sqrt{2})^2(1-\sqrt{2})^{n-1}}{2\sqrt{2}}-2^{n}$$

$$=\frac{(1+\sqrt{2})^{n+1}}{2\sqrt{2}}-\frac{(1-\sqrt{2})^{n+1}}{2\sqrt{2}}-2^{n}$$

$$=\frac{(1+\sqrt{2})^{n+1}-(1-\sqrt{2})^{n+1}}{2\sqrt{2}}-2^n=t_n$$

 

Somit haben wir eine explizite Form gefunden! :)

Diese Antwort melden
geantwortet

Student, Punkte: 2.6K

 

Kommentar schreiben

0

Vielen Dank für deine Mühe! 

Das vertauschte + und - ist kein Problem, du hast mir mit deiner Antwort sehr weitergeholfen!

 

Diese Antwort melden
geantwortet

Student, Punkte: 10

 

Kommentar schreiben