Lösen von Rekurrenzen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:54 Mo 23.06.2008 | | Autor: | stevies |
| Aufgabe | Lösen Sie die Rekurrenz:
a0 = 1
a1 = 3
an = 4an−1 − 4an−2 n ≥ 2 |
Hallo an alle,
ich habe ein Problem. Ich verstehe nicht wie man Rekurrenzen löst oder überhaupt an die obige Aufgabe dran geht... Mein bester Freund Wikipedia und das begleitende Buch zur Vorlesung hat mir in dem Kapitel auch nicht geholfen. Für sowas wie einen "Wie gehe ich an sowas ran Plan" wäre schön...
Gruß Stevie
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> Lösen Sie die Rekurrenz:
>
> a0 = 1
> a1 = 3
> an = 4an−1 − 4an−2 n ≥ 2
> Hallo an alle,
>
> ich habe ein Problem. Ich verstehe nicht wie man
> Rekurrenzen löst oder überhaupt an die obige Aufgabe dran
> geht... Mein bester Freund Wikipedia und das begleitende
> Buch zur Vorlesung hat mir in dem Kapitel auch nicht
> geholfen. Für sowas wie einen "Wie gehe ich an sowas ran
> Plan" wäre schön...
Ich bin nicht ganz sicher mit Deiner Schreibweise, aber ich vermute, es handelt sich um die ![[]](/images/popup.gif) homogen-lineare Differenzengleichung
[mm]a_n=4a_{n-1}-4a_{n-2}[/mm]
mit der Anfangsbedingung [mm] $a_0=1$ [/mm] und [mm] $a_1=3$. [/mm] In einem solchen Falle bilden die Lösungen der Differenzengleichung (ohne Anfangsbedingung) einen Vektorraum. Man versucht zuerst eine Basis dieses Vektorraumes zu bestimmen, indem man für [mm] $a_n$ [/mm] den Exponentialansatz [mm] $a_n [/mm] := [mm] z^n$ [/mm] macht, in die Differenzengleichung einsetzt und die Lösungen bestimmt. Hier haben wir Pech, dass die resultierende Gleichung 2. Grades [mm] $z^2=4z-4$ [/mm] für $z$ eine doppelte Lösung $z=2$ hat. In diesem Falle ist die Ableitung von [mm] $z^n$ [/mm] nach $z$ ebenfalls eine Basislösung der homogen-linearen Differenzengleichung (allgemein: bei einer $k$-fachen Lösung $z$ sind neben [mm] $z^n$ [/mm] die ersten $k-1$ Ableitungen von [mm] $z^n$ [/mm] ebenfalls Basislösungen). Wir haben also die Basislösungen [mm] $2^n$ [/mm] und [mm] $n\cdot 2^{n-1}$. [/mm] Nun müssen wir diese beiden Basislösungen so miteinander linear-kombinieren, dass neben der homogen-linearen Differenzengleichung zusätzlich auch noch die beiden Anfangsbedingungen [mm] $a_0=1$ [/mm] und [mm] $a_1=3$ [/mm] erfüllt sind. Sei also [mm] $a_n [/mm] := [mm] \alpha 2^n+\beta \cdot n\cdot 2^{n-1}$. [/mm] Wegen der Anfangsbedingungen erhalten wir folgendes Gleichungssystem für [mm] $\alpha$ [/mm] und [mm] $\beta$:
[/mm]
[mm]\begin{array}{clclcl|}
\text{(1)} & 1 &=& \alpha\cdot 2^0 &+& \beta\cdot 0\cdot 2^{0-1}\\
\text{(2)} & 3 &=& \alpha\cdot 2^1 &+& \beta\cdot 1\cdot 2^{1-1}\\\cline{2-6}
\end{array}[/mm]
mit der Lösung [mm] $\alpha=1$ [/mm] und [mm] $\beta=1$. [/mm] Also müsste [mm] $a_n [/mm] := [mm] 2^n+n\cdot 2^{n-1}$ [/mm] die gesuchte Lösung der homogen-linearen Differenzengleichung inklusive Anfangsbedingung sein.
Nachtrag (1. Revision): Zum allgemeinen Problem des Lösens von "Rekurrenzgleichungen" gibt es aber kein Rezept. Die Situation ist ähnlich wie bei den Differentialgleichungen: Lösungsrezepte gibt es nur für einige Spezialfälle. Eben zum Beispiel für die linearen Differentialgleichungen (bzw. hier: die linearen Differenzengleichungen). Wir hatten sogar noch zusätzlich das Glück, dass es sich um eine homogen-lineare Differenzengleichung handelte. Im inhomogen-linearen Fall müsste man noch eine "spezielle Lösung" finden, und dann zu dieser speziellen Lösung eine Linearkombination der zugehörigen homogen-linearen Differenzengleichung so addieren, dass auch die Anfangsbedingungen erfüllt sind.
|
|
|
|
