Erzeugende Funktion < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Lösen Sie die Rekursion [mm] a_0 [/mm] = 1, [mm] a_n [/mm] = 2a_(n-1) +3 mit Hilfe der Methode der erzeugenden Funktionen. |
Ich habe versucht die erzeugende Funktion zunächst zu bilden. Hierbei komme ich auf das folgende Ergebnis:
A(z) = [mm] \frac{1+2z}{1-2z}
[/mm]
Das scheint offensichtlich falsch zu sein. Kann mir jemand einen Tipp geben?
|
|
| |
|
Hallo,
> Lösen Sie die Rekursion [mm]a_0[/mm] = 1, [mm]a_n[/mm] = 2a_(n-1) +3 mit
> Hilfe der Methode der erzeugenden Funktionen.
>
>
> Ich habe versucht die erzeugende Funktion zunächst zu
> bilden. Hierbei komme ich auf das folgende Ergebnis:
>
> A(z) = [mm]\frac{1+2z}{1-2z}[/mm]
>
> Das scheint offensichtlich falsch zu sein. Kann mir jemand
> einen Tipp geben?
Es wäre leichter, dir zu helfen, wenn du deine bisherige Rechnung für A(z) hingeschrieben hättest  . So wissen wir jetzt nicht, wo der Fehler passiert ist und was du schon weißt.
Die Erzeugende Funktion ist
$A(z) = [mm] \sum_{n=0}^{\infty}a_n z^n$.
[/mm]
Damit folgt (nutze Rekursionsgleichung + Indexverschiebung):
$A(z) = [mm] a_0 [/mm] + [mm] \sum_{n=1}^{\infty}a_{n}z^{n} [/mm] = 1 + [mm] 2z\sum_{n=1}^{\infty}a_{n-1}z^{n-1} [/mm] + [mm] 3\sum_{n=1}^{\infty}z^n [/mm] = 1 + 2z A(z) + 3 [mm] \sum_{n=1}^{\infty}z^n$.
[/mm]
Hast du das auch? Kannst du nun weiterrechnen?
Als nächstes muss die Summe hinten mittels geometrischer Reihe vereinfacht und nach $A(z)$ umgestellt werden.
Viele Grüße,
Stefan
|
|
|
| |
|
| Aufgabe | [mm] a_0 [/mm] = 1
[mm] a_n [/mm] = 2 * [mm] a_{n-1} [/mm] + 3 |
Ich nutze die Methode von Aigner:
1. Schreiben in einer Formel:
[mm] a_n [/mm] = 2 * [mm] a_{n-1} [/mm] + 3 + [n=0](-2)
2. Bilden der erzeugenden Funktion:
A(z) = [mm] \summe_{n>=0}a_n z^n
[/mm]
A(z) = 2 [mm] \summe_{n>=0} a_{n-1} z^n [/mm] + 3 [mm] \summe_{n>=0} z^n [/mm] - 2 * [mm] z^0
[/mm]
A(z) = 2 z A(z) + 3 * [mm] \frac{1}{1-z} [/mm] - 2
A(z) = [mm] \frac{1+2z}{1-2z}
[/mm]
Und nun versuchen etwas umzuformen für die Partialbruchzerlegung:
= [mm] \frac{(1+2z)(1-2z)}{(1-2z)(1-2z)}
[/mm]
= [mm] \frac{1+4z^2}{(1-2z)(1-2z)}
[/mm]
Ist das korrekt?
|
|
|
| |
|
Hallo,
> [mm]a_0[/mm] = 1
> [mm]a_n[/mm] = 2 * [mm]a_{n-1}[/mm] + 3
> Ich nutze die Methode von Aigner:
>
> 1. Schreiben in einer Formel:
>
> [mm]a_n[/mm] = 2 * [mm]a_{n-1}[/mm] + 3 + [n=0](-2)
>
> 2. Bilden der erzeugenden Funktion:
>
> A(z) = [mm]\summe_{n>=0}a_n z^n[/mm]
> A(z) = 2 [mm]\summe_{n>=0} a_{n-1} z^n[/mm]
> + 3 [mm]\summe_{n>=0} z^n[/mm] - 2 * [mm]z^0[/mm]
> A(z) = 2 z A(z) + 3 * [mm]\frac{1}{1-z}[/mm] - 2
Bis hierhin stimmt alles ![[ok]](/images/smileys/ok.gif "[ok]") .
> A(z) = [mm]\frac{1+2z}{1-2z}[/mm]
Hier scheinst du dich dann verrechnet zu haben.
Nach deiner letzten Gleichung ist
$(1- 2*z) *A(z) = [mm] \frac{3}{1-z} [/mm] - 2 = [mm] \frac{3 - 2(1-z)}{1-z} [/mm] = [mm] \frac{1+2z}{1-z}$.
[/mm]
Du hast also das $(1-z)$ im Nenner vergessen, wenn du nun im Folgenden durch $(1-2*z)$ teilst.
Viele Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:48 Mi 11.03.2015 | | Autor: | Rainingman |
Das darf nicht wahr sein!!!! Danke für den Hinweis. Jetzt komme ich auch zum Ziel!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:56 Mi 11.03.2015 | | Autor: | Rainingman |
Mein Ergebnis ist nun:
[mm] a_n [/mm] = -3 + 4 * [mm] 2^n
[/mm]
|
|
|
| |
|
Hallo,
> Mein Ergebnis ist nun:
>
> [mm]a_n[/mm] = -3 + 4 * [mm]2^n[/mm]
Das sieht gut aus !
Stefan
|
|
|
|
