Erzeugende Funktion einer Rekursionsgleichung berechnen

17.02.2015, 16:09

Voldi

Erzeugende Funktion einer Rekursionsgleichung berechnen

Heyho, ich kämpf gerade mit diesem Thema und wollte mal wissen, ob ich mich (bis jetzt) irgendwo verrechnet habe.

Die Rekursionsgleichung hat die Form $\begin{eqnarray*} 2a_{n} = 5a_{n-1} - 3a_{n-2} - a_{n-3} + a_{n-4} \end{eqnarray*}$ mit $\begin{eqnarray*} a_{0} = 8, a_{1} = -2, a_{2} = 8, a_{3} = 11 \end{eqnarray*}$ .
Ich möchte nun zuerst die dazugehörige erzeugende Funktion $\begin{eqnarray*} A(x) \end{eqnarray*}$ berechnen.

Ich stelle also auf:
$\begin{eqnarray*} A(x) = \sum\limits_{n\geq 0} a_{n}x^n \end{eqnarray*}$
Und forme die rechte Seite nun so um, dass ich die Rekursionsbedingungen und die Anfangswerte einsetzen kann:
$\begin{eqnarray*} A(x) = 8-2+8+11+ \sum\limits_{n\geq 4} (\frac{5}{2} a_{n-1} - \frac{3}{2} a_{n-2} - \frac{1}{2} a_{n-3} + \frac{1}{2} a_{n-4} )x^n \end{eqnarray*}$
Als nächstes teile ich die Summe rechts etwas auf und verschiebe die Summengrenze immer, um überall $\begin{eqnarray*} a_{n}x^n \end{eqnarray*}$ zu erhalten:
$\begin{eqnarray*} A(x) = 25 + \frac{5}{2}x \sum\limits_{n\geq 3} a_{n}x^n - \frac{3}{2}x^2 \sum\limits_{n\geq 2} a_{n}x^n - \frac{1}{2}x^3 \sum\limits_{n\geq 1} a_{n}x^n + \frac{1}{2}x \sum\limits_{n\geq 0} a_{n}x^n \end{eqnarray*}$
Jetzt subtrahiere ich für jede Summe die fehlenden Folgenglieder, um die Summengrenze auf $\begin{eqnarray*} n\geq 0 \end{eqnarray*}$ zu bekommen:
$\begin{eqnarray*} A(x) = 25 + \frac{5}{2}x(\sum\limits_{n\geq 0} a_{n}x^n - 14) - \frac{3}{2}x^2(\sum\limits_{n\geq 0} a_{n}x^n - 6) - \frac{1}{2}x^3(\sum\limits_{n\geq 0} a_{n}x^n - 8) + \frac{1}{2}x^4\sum\limits_{n\geq 0} a_{n}x^n \end{eqnarray*}$

Nun kann ich sämtliche Vorkommen von Summen durch $\begin{eqnarray*} A(x) \end{eqnarray*}$ ersetzen und dies dann ausklammern:
$\begin{eqnarray*} A(x) = 25 - 35x + 9x^2 + 4x^3 + A(x)(\frac{5}{2}x - \frac{3}{2}x^2 - \frac{1}{2}x^3 + \frac{1}{2}x^4) \end{eqnarray*}$

Durch Umformen komme ich dann auf $\begin{eqnarray*} A(x) = \frac{4x^3 + 9x^2 - 35x + 25}{-\frac{1}{2}x^4 +\frac{1}{2}x^3 +\frac{3}{2}x^2 -\frac{5}{2}x + 1} \end{eqnarray*}$

Wäre über eine Korrektur o.ä. sehr dankbar smile

Dies ist "erst" der erste Aufgabenteil, aber solange ich mir mit der Lösung hiervon noch nicht sicher bin, lohnt es nicht mit den anderen anzufangen.
Danke schon mal!

17.02.2015, 17:39

Matt Eagle

Auf diesen Beitrag antworten »

RE: Erzeugende Funktion einer Rekursionsgleichung berechnen

Zitat:

Original von Voldi
...
Und forme die rechte Seite nun so um, dass ich die Rekursionsbedingungen und die Anfangswerte einsetzen kann:
$\begin{eqnarray*} A(x) = 8-2+8+11+ \sum\limits_{n\geq 4} (\frac{5}{2} a_{n-1} - \frac{3}{2} a_{n-2} - \frac{1}{2} a_{n-3} + \frac{1}{2} a_{n-4} )x^n \end{eqnarray*}$

Der Ansatz sollte dann eher so aussehen:

$\begin{eqnarray*} A(x) = 8-2x+8x^2+11x^3+ \sum\limits_{n\geq 4} (\frac 52 a_{n-1} - \frac 32 a_{n-2} - \frac 12 a_{n-3} + \frac 12 a_{n-4} )x^n \end{eqnarray*}$

17.02.2015, 18:11

Voldi

Auf diesen Beitrag antworten »

Aah, na klar. Dann macht die Teilaufgabe b) auch plötzlich vieeeel mehr Sinn. Danke sehr!

Korrigiert sähe das dann so aus?

$\begin{eqnarray*} A(x) = 8 - 37x + 17x^2 + 15x^3 + A(x)(\frac{5}{2}x - \frac{3}{2}x^2 - \frac{1}{2}x^3 + \frac{1}{2}x^4) \end{eqnarray*}$

$\begin{eqnarray*} A(x) = \frac{15x^3 + 17x^2 - 37x + 8}{-\frac{1}{2}x^4 +\frac{1}{2}x^3 +\frac{3}{2}x^2 -\frac{5}{2}x + 1} \end{eqnarray*}$

17.02.2015, 18:30

HAL 9000

Auf diesen Beitrag antworten »

Mit Ausnahme der 8 sind die anderen Summanden im Zähler falsch. Allem Anschein nach hast du bei der Berechnung irgendwas systematisch falsch gemacht.

17.02.2015, 18:36

Voldi

Auf diesen Beitrag antworten »

Ah - ich denke ich weiß wo. Habe ja einige Summen abgeändert um auf $\begin{eqnarray*} n \geq 0 \end{eqnarray*}$ zu kommen und die übrigen Folgeglieder subtrahiert. Aber auch da habe ich ja das x, x^2 usw vergessen. Wird wohl daran liegen.

17.02.2015, 18:50

Voldi

Auf diesen Beitrag antworten »

Meine korrigierte, endgültige Antwort (der Einfachheit halber mit -2 erweitert) wäre dann:

$\begin{eqnarray*} A(x) = \frac{16x^3 - 50x^2 + 44x - 16}{x^4 - x^3 - 3x^2 + 5x - 2} \end{eqnarray*}$

Wenn ich nun die Rekursionsgleichung lösen wollen würde, müsste ich eine Partialbruchzerlegung durchführen und daraus dann formale Potenzreihen ableiten, um dann die Koeffizienten zu vergleichen.

17.02.2015, 19:02

HAL 9000

Auf diesen Beitrag antworten »

Jetzt ist es richtig.

Und ja, jetzt ist die PBZ fällig: Freundlicherweise (wie so oft bei "Schulaufgaben") sind alle Nennernullstellen ganzzahlig. Big Laugh

Neue Frage »

Antworten »

Erzeugende Funktion einer Rekursionsgleichung berechnen

Verwandte Themen