Rekursionsgleichung in expliziete Darstellung umwandeln

Question

Aufgabenstellung:

Geben Sie eine explizite, reelle Darstellung für die allgemeine Lösung $x_{n}$ der Rekursionsgleichung
$$\begin{aligned} x_{n+2}-16 x_{n+1}+289 x_{n} &=0 \\ x_{0}=1, & x_{1}=0 \end{aligned}$$
Hinweis: Eine expliziten, reellen Darstellung darf keine komplexen Terme enthalten.

Problem:

Ich sehe keine Abbruchbedingung innerhalb der Formel.

Wenn man zum Beispiel die Formel zum berechnen der Fibonnacizahl nimmt wird n im ersten Schrit mit 1 subtrahiert und im zweiten Schritt mit 2 subtrahiert, wodurch man schließlich irgendwann an die Abbruchbedingung 0 = 1 und 1 = 1 gelangt:

0: return 1;
1: return 1;
default: return fib(n-1) + fib(n-2);

Ich sehe jedoch keine Abbruchbedinung in meiner Aufgabe da n bei jedem Aufruf um 1 erhöh wird.

Kann mir jemand weiterhelfen?

Comments

Ich sehe keine Abbruchbedingung innerhalb der Formel.

Was soll da abbrechen? Das ist eine Rekursionsformel, daher berechnet man aus bekannten Folgengliedern die nächsten. Überlege dir doch erstmal, wie man x_2 berechnet. 

0: return 1;
1: return 1;
default: return fib(n-1) + fib(n-2);

Das ist eine analytische Aufgabe, ein Rechner wird nicht benötigt.

---

@Gast jc2144

ja aber irgendwann muss die rekursion doch enden oder nicht? und ich sehe nicht wann die rekursion endet wenn n mit eins und zwei addiert wird. bei dem beispiel mit der fibonnaci sequenz wird n um eins und zwei reduziert, weshalb dann irgendwann der grenzwert 0 oder 1 erreicht wird und dann "abbricht".

---

wenn n mit eins und zwei addiert wird.

Vielleicht hilft dir folgendes:

man kann die Rekursionsformel auch wie folgt schreiben, indem man n+2 := m setzt:

$$x_{m}-16 x_{m-1}+289 x_{m-2} =0$$

m ∈ [2,∞)

---

Hallo,

wie schon in dem Kommentar erwähnt, scheinst Du das Prinzip der Rekursionsformel noch nicht ganz erfasst zu haben. Jedenfalls bricht auch die Fibonacci-Folge nicht ab - oder was meinst Du damit.

Du solltest mal einige Folgenglieder berechnen, um ein Gefühl für die Sache zu bekommen.

Es gibt 3 Möglichkeiten, diese Rekursionsformel zu lösen:

1. Empirisch raten, wie die allgemeine Form aussieht und durch Induktion verifizieren.

2. Potenzeihen-Methode

3. Ansatz $x_n=a^n$ und charakteristische Gleichung.

Vielleicht schaust Du mal in Dein Skript, was erwartet wird.

Gruß

---

Aloha :)

Ich habe die Aufgabe gerade überflogen und eine Lösungsidee.

Allerdings würde das vermutlich zu einer komplex-wertigen Lösung führen.

Könntest du mal bitte die Vorzeichen in der Rekursionsgleichung prüfen.

---

Hallo Tschaka,

die charackteristische Gleichung hat zwei komplexe Nullstellen, aber man kann ähnlich wie bei linearen DGLs die Lösung mit Sinus und Cosinustermen reell machen.

Zumindest hat mir das Wolfram alpha verraten ;).

PS: ich habe gerade

http://statistik.wu-wien.ac.at/~leydold/MOK/HTML/node195.html

gefunden, da wird es auch für komplexe Werte vorgemacht.

---

Hallo jc2144 ;)

So ähnlich habe ich das nämlich befürchtet. Ich wollte über lineare Algebra rangehen:$$\binom{x_{n+2}}{x_{n+1}}=\left(\begin{array}{c}16 & -289\\1 & 0\end{array}\right)^{n+1}\binom{0}{1}\quad;\quad n\ge0$$Aber Eigenwerte und Eigenvektoren sind komplex... Viel Fummelei :(