Lösung von Rekursionsgleichung bestimmen

29.05.2013, 22:36

sartari

Auf diesen Beitrag antworten »

Lösung von Rekursionsgleichung bestimmen

Hallo,

sitze gerade an einer Aufgabe und komme nicht so recht weiter. Ich soll die Lösung der Rekursionsgleichung

$\begin{eqnarray*} x_n=_{def} n+1-2x_{n-1}-x_{n-2} \quad n\geq 2 \end{eqnarray*}$

mit $\begin{eqnarray*} x_0=_{def} 1, x_1=_{def} 4 \end{eqnarray*}$ bestimmen.

Also angefangen mit der erzeugenden Funktion, da sieht mein Fortschritt wie folgt aus:

$\begin{eqnarray*} <br /> x_n =_{def} n+1-2A_{n-1}-A_{n-2} \\\\<br /> A(x) = 1+4+ \sum_{n=2}^{\infty} (n+1-2A_{n-1}-A_{n-2})*x^n \\<br /> = 5+ \sum_{n=2}^{\infty}nx^n + \sum_{n=2}^{\infty}x^n - \sum_{n=2}^{\infty} 2A_{n-1}x^n - \sum_{n=2}^{\infty} A_{n-2} x^n\\<br /> =5+\sum_{n=0}^{\infty}nx^n-x+x^2\sum_{n=0}^{\infty}x^n - 2x\sum_{n=1}^{\infty} A_{n}x^{n} - \sum_{n=0}^{\infty}A_{n}x^{n+2}\\<br /> =5-\frac{(x-2)x^2}{(x-1)^2}+\frac{x^2}{1-x}- 2x(A(x)-1) - x^2 A(x) \\<br /> =5-\frac{(x-2)x^2}{(x-1)^2}+\frac{x^2}{1-x}-2xA(x)+2x-x^2A(x)\\<br /> A(x)+2xA(x)+x^2A(x)=5-\frac{(x-2)x^2}{(x-1)^2}+\frac{x^2}{1-x}+2x\\<br /> A(x)*(1+2x+x^2)=5-\frac{(x-2)x^2}{(x-1)^2}+\frac{x^2}{1-x}+2x \\<br /> A(x)*(x+1)^2=5-\frac{(x-2)x^2}{(x-1)^2}+\frac{x^2}{1-x}+2x \\<br /> A(x)=\frac{5-\frac{(x-2)x^2}{(x-1)^2}+\frac{x^2}{1-x}+2x}{(x+1)^2}\\<br /> A(x)=\frac{4x^2-8x+5}{(x^2-1)^2}<br /> \end{eqnarray*}$

Dazu erstmal, stimmt das soweit? Bin mir in dem Thema ziemlich unsicher.

Und jetzt, wie gehts weiter; Wir hatten da zwei Möglichkeiten - Taylorreihenentwicklung oder das Zerlegen in bereits bekannte Potenzreihen und irgendwie will mir beides nicht so recht gelingen Augenzwinkern

Augenzwinkern

29.05.2013, 22:42

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von sartari (korrigiert)
$\begin{eqnarray*} A(x) = 1+4{\color{red}x}+ \sum_{n=2}^{\infty} (n+1-2A_{n-1}-A_{n-2})*x^n \end{eqnarray*}$

29.05.2013, 23:07

sartari

Auf diesen Beitrag antworten »

Ah, ein Fehler in Zeile 2, da kommt Freude auf Augenzwinkern

Augenzwinkern

$\begin{eqnarray*} <br /> A(x) = 1+4x+ \sum_{n=2}^{\infty} (n+1-2A_{n-1}-A_{n-2})*x^n \\<br /> = 1+4x \sum_{n=2}^{\infty}nx^n + \sum_{n=2}^{\infty}x^n - \sum_{n=2}^{\infty} 2A_{n-1}x^n - \sum_{n=2}^{\infty} A_{n-2} x^n\\<br /> =1+4x+\sum_{n=0}^{\infty}nx^n-x+x^2\sum_{n=0}^{\infty}x^n - 2x\sum_{n=1}^{\infty} A_{n}x^{n} - \sum_{n=0}^{\infty}A_{n}x^{n+2}\\<br /> =1+4x-\frac{(x-2)x^2}{(x-1)^2}+\frac{x^2}{1-x}- 2x(A(x)-1) - x^2 A(x) \\<br /> =1+4x-\frac{(x-2)x^2}{(x-1)^2}+\frac{x^2}{1-x}-2xA(x)+2x-x^2A(x)\\<br /> A(x)+2xA(x)+x^2A(x)=1+4x-\frac{(x-2)x^2}{(x-1)^2}+\frac{x^2}{1-x}+2x\\<br /> A(x)*(1+2x+x^2)=1+4x-\frac{(x-2)x^2}{(x-1)^2}+\frac{x^2}{1-x}+2x \\<br /> A(x)*(x+1)^2=1+4x-\frac{(x-2)x^2}{(x-1)^2}+\frac{x^2}{1-x}+2x \\<br /> A(x)=\frac{1+4x-\frac{(x-2)x^2}{(x-1)^2}+\frac{x^2}{1-x}+2x}{(x+1)^2}\\<br /> A(x)=\frac{(1+4x-8x^2+4 x^3)}{(1-2x^2+x^4)} \end{eqnarray*}$

Wie siehts jetzt aus? Augenzwinkern

Augenzwinkern

29.05.2013, 23:13

HAL 9000

Auf diesen Beitrag antworten »

Ja, sieht gut aus, ich war durch eigene Rechnung auf

$\begin{eqnarray*} A(x) = \frac{4x}{(1+x)^2} + \frac{1}{(1-x^2)^2} \end{eqnarray*}$

gekommen, was wohl dasselbe ist.

30.05.2013, 11:08

sartari

Auf diesen Beitrag antworten »

Yay und deine Lösung schreit ja schon fast nach einer Umformung in bereits bekannte Potenzreihen, oder?

30.05.2013, 11:42

HAL 9000

Auf diesen Beitrag antworten »

Ja, könnte man schon machen. Alternativ bleibt auch der "Standardweg", jetzt erstmal eine vollständige PBZ zu machen, und auf deren Basis dann die explizite Koeffizientenformel für $\begin{eqnarray*} A_n \end{eqnarray*}$ aufzustellen. Wie man es nun letztendlich macht, ist Geschmackssache.

Anzeige

30.05.2013, 13:16

sartari

Auf diesen Beitrag antworten »

Ok, jetzt sieht es so aus:

Wir zerlegen $\begin{eqnarray*} A(x)=\frac{4x}{(1+x)^2}+\frac{1}{(1-x^2)^2} \end{eqnarray*}$ in bereits bekannte Potenzreihen:
$\begin{eqnarray*} <br /> A(x)=&\frac{4x}{(1+x)^2}+\frac{1}{(1-x^2)}*\frac{1}{(1-x^2)}\\<br /> A(x)=&\frac{4x}{(1+x)^2}+(\sum_{k=0}^\infty x^k)^2*\frac{1}{(1+x)^2}\\<br /> \end{eqnarray*}$

Jetzt müsste ich mich ja eigtl nur noch um $\begin{eqnarray*} \frac{1}{(x+1)^2} \end{eqnarray*}$ und um $\begin{eqnarray*} \frac{x}{(x+1)^2} \end{eqnarray*}$ kümmern, oder? Aber da will mir iwie nichts zu einfallen..

Zu $\begin{eqnarray*} \frac{1}{(x+1)^2} \end{eqnarray*}$ : So ein Ansatz?

$\begin{eqnarray*} \frac{1}{x^2+2x+1}=\frac{A}{1-ax}+\frac{B}{1-bx} \end{eqnarray*}$ und dann mit geometrischer Reihe weitermachen?

30.05.2013, 13:26

HAL 9000

Auf diesen Beitrag antworten »

Wende doch einfach $\begin{eqnarray*} \frac{1}{(1-q)^2} = \sum_{k=0}^{\infty} (k+1)q^k \end{eqnarray*}$ einmal für $\begin{eqnarray*} q=-x \end{eqnarray*}$ (links) und dann für $\begin{eqnarray*} q=x^2 \end{eqnarray*}$ (rechts) an.

30.05.2013, 13:57

sartari

Auf diesen Beitrag antworten »

Also für $\begin{eqnarray*} \frac{1}{(x+1)^2} \end{eqnarray*}$ einfach: $\begin{eqnarray*} \sum_{k=0}^{\infty}(k+1)*(-x^k) \end{eqnarray*}$ ?

Edit: Hm, ich glaube du meintest was anderes Augenzwinkern

Augenzwinkern

Und wiese für das rechte $\begin{eqnarray*} q=x^2 \end{eqnarray*}$ ?

30.05.2013, 14:10

HAL 9000

Auf diesen Beitrag antworten »

Na richtig Klammern setze sollte man schon. unglücklich

unglücklich

Eingesetzt ergibt sich

$\begin{eqnarray*} \frac{1}{(1+x)^2} = \sum_{k=0}^{\infty} (k+1)(-x)^k = \sum_{k=0}^{\infty} (k+1)(-1)^k x^k \end{eqnarray*}$

sowie

$\begin{eqnarray*} \frac{1}{(1-x^2)^2} = \sum_{k=0}^{\infty} (k+1)(x^2)^k = \sum_{k=0}^{\infty} (k+1)x^{2k} \end{eqnarray*}$ ,

womit sich dein unverständliches "wieso" erübrigen sollte: Weil das genau die Reihen sind, die man hier braucht.

30.05.2013, 14:36

sartari

Auf diesen Beitrag antworten »

Edit: Ahhh, du beziehst dich auf den Anfangsterm smile

smile

Alles klar, dankeschön! smile

smile

(Oh, ja das sollte man eigtl können.. unglücklich

unglücklich

Dennoch ist mir dann das rechte immer noch nicht klar; Vielleicht reden wir auch aneinander vorbei, aber ich ging davon aus, dass du damit $\begin{eqnarray*} \frac{x}{(1-x)^2} \end{eqnarray*}$ meintest, aber warum hilft mir da $\begin{eqnarray*} x^2 \end{eqnarray*}$ .

Was ich doch machen könnte, wäre : $\begin{eqnarray*} \frac{x}{(1-x)^2}=\frac{1}{x+1}-\frac{1}{x+1}^2 \end{eqnarray*}$ und die dann beide einzeln machen und da sind mir die Reihen ja bereits bekannt)

30.05.2013, 14:39

Mystic

Auf diesen Beitrag antworten »

Kleiner Einwurf zwischendurch: Ich bin zwar, wie manche hier wissen, durchaus ein Fan von erzeugenden Funktionen, aber käme hier auch nicht im Traum auf die Idee sie überhaupt in Betracht zu ziehen... Immerhin hat die homogene Differenzengleichung

$\begin{eqnarray*} x_n+2x_{n-1}+x_{n-2}=0 \end{eqnarray*}$

ja die offensichtliche Lösung $\begin{eqnarray*} (An+B)(-1)^n \end{eqnarray*}$ und eine partikuläre Lösung ist durch einen Ansatz als lineare Funktion in n auch sofort gefunden... Augenzwinkern

Augenzwinkern

30.05.2013, 15:15

HAL 9000

Auf diesen Beitrag antworten »

Hehehe, vertauschte Rollen... Big Laugh

Big Laugh

Ich hätte es auch so gemacht, aber sartari war so vertieft in seinen Weg, da wollte ich ihn auch nicht von abbringen. Außerdem sieht das ganze oben nur so lang aus durch einige etwas ungeschickte Umformungen. Beispielsweise hätte man sofort

$\begin{eqnarray*} \sum_{n=2}^{\infty} (n+1)x^n = \frac{1}{(1-x)^2} -1-2x \end{eqnarray*}$

berechnen können. Augenzwinkern

Augenzwinkern

30.05.2013, 16:39

sartari

Auf diesen Beitrag antworten »

Wir haben in der Vorlesung eben eigentlich nur diese Form gemacht, daher kann ich mit einem alternativen Lösungsweg wahrscheinlich auch nicht viel anfangen Augenzwinkern

Augenzwinkern

Aber zu sartari und seinem Weg, ich hänge nämlich schon wieder fest:

$\begin{eqnarray*} A(x)=&4x*\sum_{k=0}^{\infty}(k+1)*(-1)^k*x^k+\sum_{k=0}^{\infty}(k+1)*x^{2k} \end{eqnarray*}$

Jetzt muss ich ja igendwie entsprechend umformen, damit ich das alles unter eine Summe bringe, aber da komme ich irgendwie nicht weiter unglücklich

unglücklich

30.05.2013, 19:39

HAL 9000

Auf diesen Beitrag antworten »

Das ist in der Tat vielleicht ein wenig knifflig anzuschauen für jemand, der das nicht gewohnt ist. Wenn du bei der folgenden Umformung die Hände über den Kopf zusammenschlägst, dann denk dran, dass ich dir oben auch

Zitat:

Original von HAL 9000
Alternativ bleibt auch der "Standardweg", jetzt erstmal eine vollständige PBZ zu machen, und auf deren Basis dann die explizite Koeffizientenformel für $\begin{eqnarray*} A_n \end{eqnarray*}$ aufzustellen.

vorgeschlagen habe. smile

smile

Nun, bleiben wir erstmal beim eingeschlagenen Weg: Es ist

$\begin{eqnarray*} A(x) &=& \frac{4x}{(1+x)^2} + \frac{1}{(1-x^2)^2} = 4x\sum_{k=0}^{\infty} (k+1)(-1)^k x^k + \sum_{k=0}^{\infty} (k+1)x^{2k} \\ &=& -4\sum_{n=1}^{\infty} n(-1)^n x^n + \sum_{n=0}^{\infty} \frac{1+(-1)^n}{2}\cdot \left(\frac{n}{2}+1\right) x^n \end{eqnarray*}$

mit Indexverschiebung $\begin{eqnarray*} n=k+1 \end{eqnarray*}$ in der ersten sowie "Indexumwandlung" $\begin{eqnarray*} n=2k \end{eqnarray*}$ in der zweiten Summe. Letzteres ist natürlich nur statthaft, wenn man gewährleistet, dass für ungerade $\begin{eqnarray*} n \end{eqnarray*}$ der (vorher in der $\begin{eqnarray*} k \end{eqnarray*}$ -Summe gar nicht existente) Summand zu Null wird, und das erreicht man durch den "Hilfsfaktor"

$\begin{eqnarray*} \frac{1+(-1)^n}{2} = \begin{cases} 1 & \;\mbox{falls $n$ gerade} \\ 0 & \;\mbox{falls $n$ ungerade} \end{cases} \end{eqnarray*}$ .

Es verbleibt nun nur noch das Aufsammeln der einzelnen Bestandteile des Koeffizienten von $\begin{eqnarray*} x^n \end{eqnarray*}$ :

$\begin{eqnarray*} A_n = -4n(-1)^n + \frac{1+(-1)^n}{2}\cdot \left(\frac{n}{2}+1\right) \end{eqnarray*}$

Das lässt sich natürlich noch zusammenfassen und somit "schöner" schreiben. Augenzwinkern

Augenzwinkern

01.06.2013, 12:36

sartari

Auf diesen Beitrag antworten »

Sorry für die späte Antwort; Ja habs verstanden, wär aber nie auf sowas gekommen Augenzwinkern

Augenzwinkern

Wieder was gelernt, dankeschön!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »