Geschlossene Formel für Rekursive Folge

28.06.2014, 00:58

greendayasd

Geschlossene Formel für Rekursive Folge

Hi zusammen smile

Ich versuche mich grade an folgender Aufgabe, aber ich komme nicht wirklich weiter:

Gegeben ist eine rekursiv definierte Folge:
$\begin{eqnarray*} a_{n} \end{eqnarray*}$ = 3 $\begin{eqnarray*} a_{n-1} \end{eqnarray*}$ - $\begin{eqnarray*} a_{n-2} \end{eqnarray*}$ für n $\begin{eqnarray*} \leq \end{eqnarray*}$ 2 mit den Anfangswerten $\begin{eqnarray*} a_{1} \end{eqnarray*}$ = $\begin{eqnarray*} a_{0} \end{eqnarray*}$ = 1. Bestimmen Sie eine geschlossebe Formel für $\begin{eqnarray*} a_{n} \end{eqnarray*}$ .

Die zugehörige Lösung kenne ich bereits:

http://i.imgur.com/GpBGLG0.gif

Ich weiß nur leider nicht, wie ich bei der Berechnung vorgehen muss :/ Meine bisherigen Versuche, durch Rumprobieren auf das Ergebnis zu kommen und dieses per Induktion zu beweisen, $\begin{eqnarray*} a_{n-1} \end{eqnarray*}$ in $\begin{eqnarray*} a_{n-2} \end{eqnarray*}$ - $\begin{eqnarray*} a_{n-3} \end{eqnarray*}$ ausfzulösen und damit weiterzurechnen und auch ein paar gegoogelte Anleitungen anzuwenden haben mich leider nur im Kreis geführt, weiß einer Rat?

Gruß
freshgdasd

28.06.2014, 02:38

Guppi12

Auf diesen Beitrag antworten »

Hallo,

ich weiß nicht, ob es noch irgendwie einfacher geht. Wenn jemand was weiß, bitte übernehmen.

Was du machen könntest, wäre folgendes
betrachte die Folge $\begin{eqnarray*} b_n := \log_3(a_n) \end{eqnarray*}$ .

Es folgt dann $\begin{eqnarray*} b_0 = b_1 = 0 \end{eqnarray*}$ und $\begin{eqnarray*} b_n = 1+b_{n-1}+b_{n-2} \end{eqnarray*}$ für $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ .
Wenn du eine explizite Formel für $\begin{eqnarray*} b_n \end{eqnarray*}$ gefunden hast, könntest du dann wieder $\begin{eqnarray*} a_n = 3^{b_n} \end{eqnarray*}$ ausnutzen.

Es folgt für $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$ , dass

$\begin{eqnarray*} \begin{pmatrix}b_n \\ b_{n-1} \\ 1\end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{pmatrix}\begin{pmatrix}b_{n-1} \\ b_{n-2} \\ 1\end{pmatrix} \end{eqnarray*}$ .
Induktiv folgt

$\begin{eqnarray*} \begin{pmatrix}b_n \\ b_{n-1} \\ 1\end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{pmatrix}^{n-1}\begin{pmatrix}b_1 \\ b_0 \\ 1\end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{pmatrix}^{n-1}\begin{pmatrix}0 \\ 0 \\ 1\end{pmatrix} \end{eqnarray*}$ .

Daraus folgt

$\begin{eqnarray*} b_n = \begin{pmatrix}1 & 0 & 0\end{pmatrix}\begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{pmatrix}^{n-1}\begin{pmatrix}0 \\ 0 \\ 1\end{pmatrix} \end{eqnarray*}$ .

Die Matrix, die da steht, kannst du nun diagonalisieren und so zu deiner expliziten Form kommen.
Das habe ich selbst nicht gemacht (hatte nach Bestimmung von Eigenwerten und Eigenvektoren keine Lust mehr), aber theoretisch ist das möglich. Wie gesagt, ich denke, das muss eigentlich auch leichter gehen. Komme aber grad nicht drauf.

Edit: falls du das noch machen willst, hier zum weitermachen: Es ist

$\begin{eqnarray*} \begin{pmatrix}1 \\ 1 \\ -1\end{pmatrix} \end{eqnarray*}$ Eigenvektor zum Eigenwert $\begin{eqnarray*} 1 \end{eqnarray*}$

$\begin{eqnarray*} \begin{pmatrix}2 \\ \sqrt{5}-1 \\ 0\end{pmatrix} \end{eqnarray*}$ Eigenvektor zum Eigenwert $\begin{eqnarray*} \frac 12(1+\sqrt{5}) \end{eqnarray*}$

$\begin{eqnarray*} \begin{pmatrix}2 \\ -\sqrt{5}-1 \\ 0\end{pmatrix} \end{eqnarray*}$ Eigenvektor zum Eigenwert $\begin{eqnarray*} \frac 12(1-\sqrt{5}) \end{eqnarray*}$ .

28.06.2014, 03:21

Tesserakt

Auf diesen Beitrag antworten »

Zitat:

Original von Guppi12
Hallo,

ich weiß nicht, ob es noch irgendwie einfacher geht. Wenn jemand was weiß, bitte übernehmen.

Was du machen könntest, wäre folgendes
betrachte die Folge $\begin{eqnarray*} b_n := \log_3(a_n) \end{eqnarray*}$ .

Es folgt dann $\begin{eqnarray*} b_0 = b_1 = 0 \end{eqnarray*}$ und $\begin{eqnarray*} b_n = 1+b_{n-1}+b_{n-2} \end{eqnarray*}$ für $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ .

Durchaus nicht.

$\begin{eqnarray*} a_n = 3a_{n - 1} - a_{n - 2} \end{eqnarray*}$ mit $\begin{eqnarray*} a_0 = a_1 = 1 \end{eqnarray*}$ .
Dann ist $\begin{eqnarray*} a_2 = 3a_1 - a_0 = 3 - 1 = 2 \end{eqnarray*}$

$\begin{eqnarray*} b_2 = \log_3(a_2) = \log_3(2) \neq 1 + b_1 + b_0 = 1 + 0 + 0 = 1 \end{eqnarray*}$

28.06.2014, 07:16

HAL 9000

Auf diesen Beitrag antworten »

Einerseits könnte man das "normale" Lösungsverfahren für Lineare Differenzengleichungen durchziehen, und kommt so zu einer expliziten Formel.

Was im vorliegenden Fall auffällt, dass jeder zweite Wert der Fibonacci-Folge $\begin{eqnarray*} (F_n) \end{eqnarray*}$ rauskommt. Das kann man natürlich auch begründen: Es ist

$\begin{eqnarray*} F_{n} = F_{n-1} + F_{n-2} \end{eqnarray*}$

Setzt man da rechts $\begin{eqnarray*} F_{n-1} = F_{n-2} + F_{n-3} \end{eqnarray*}$ sowie anschließend $\begin{eqnarray*} F_{n-3} = F_{n-2} - F_{n-4} \end{eqnarray*}$ ein, so gelangt man zu

$\begin{eqnarray*} F_{n} = 3F_{n-2} - F_{n-4} \end{eqnarray*}$ .

In Anbetracht dessen, dass $\begin{eqnarray*} a_0=1=F_{-1} \end{eqnarray*}$ (Fibonacci-Folge "nach links" fortgesetzt) und $\begin{eqnarray*} a_1=1=F_1 \end{eqnarray*}$ ist, folgt daraus unmittelbar

$\begin{eqnarray*} a_n = F_{2n-1} \end{eqnarray*}$ ,

und man könnte direkt auch die Formel von Moivre-Binet zur expliziten Darstellung der Fibonacci-Folge nutzen.

28.06.2014, 10:31

Guppi12

Auf diesen Beitrag antworten »

Zitat:

Original von Tesserakt

Zitat:

Mein Gott, ich war gestern schon zu müde. Hab aus dem Minus in der Bildungsvorschrift ein Mal gemacht.

Will jetzt nicht die Schuld verschieben, aber warum schreibt man auch:

code:
1:	[latex]a_{n}[/latex] = 3[latex]a_{n-1}[/latex] - [latex]a_{n-2}[/latex]

anstatt einfach alles in Latex. Dadurch, dass das Minus auf diese Weise im Kontrast zu den fett geschriebenen Folgengliedern so dünn und schmal aussieht, hatte ich es bei einem flüchtigen Blick für einen \cdot gehalten und danach nicht nochmal drauf geschaut. Tut mir Leid.

Jedenfalls war ich von der Bildungsvorschrift $\begin{eqnarray*} a_{n} = 3a_{n-1}a_{n-2} \end{eqnarray*}$ ausgegangen.

Gruß,
Guppi.

30.06.2014, 17:41

greendayasd

Auf diesen Beitrag antworten »

Vielen Dank für die Hilfestellung, ich bin weitergekommen smile

Neue Frage »

Antworten »

Geschlossene Formel für Rekursive Folge

Verwandte Themen