explizite Formel für rekursive Folge mit Potenzreihen

Question

Aufgabe:

$$Die\;Folge\;(a_n)\;sei\;rekursiv\;definiert\;durch:\\a_0=0,\;a_1=1\;und\;a_n=3a_{n-1}+10a_{n-2},\;n\geq2.\\Bestimmen\;Sie,\;unter\;Verwendung\;der\;Potenzreihe\;\sum_{n=0}^\infty a_nx^n,\;eine\;explizite\;Formel\;für\;a_n,\\wobei\;der\;Rechenweg\;nachvollziehbar\;darzulegen\;ist.$$
Problem/Ansatz:

Ich weiß ungefähr, wie man allgemein vorgehen würde, wenn bei einer rekursiven Definition das a_n nur mit einem vorherigen Folgenglied gebildet wird, z.B. a_n=a_n-1+4. Aber hier wird a_n mit zwei Folgengliedern gebildet. Wie geht man an das Problem heran?

Answer 1

1. Schritt: Die Rekursionsgleichung in eine einzige Gleichung bringen.
\(\begin{aligned} a_{ n}  = 3a_{ n - 1} + 10a_{ n - 2} + [ n = 1] .\end{aligned}\)

2. Schritt: Mit \( z^{ n}\) multiplizieren und über alle \( n\) summieren (damit alles wohldefiniert ist, setzen wir einfach \(a_{ -2} = a_{ -1} =0\)).
\(\begin{aligned}   \sum_{ n = 0}^{\infty} a_{ n} z^{ n} &=   \sum_{ n = 0}^{\infty} 3  a_{ n -1} z^{ n}   + \sum_{ n = 0}^{\infty} 10a_{ n - 2} z^{ n} + z   \\   &= 3z \sum_{ n = 0}^{\infty} a_{ n} z^{ n} + 10z^{ 2} \sum_{ n = 0}^{\infty} a_{ n} z^{ n} + z .\end{aligned}\)

3. Schirtt: Setze \( G( z)  = \sum_{ n = 0}^{\infty} a_{ n} z^{ n}\) um eine Funktionengleichung zu erhalten.
\(\begin{aligned} G( z)  = 4zG( z)  + 10z^{ 2}G( z)  + z .\end{aligned}\)

4. Schritt: Die Gleichung nach \( G( z) \) auflösen.
\(\begin{aligned} G( z)  = \frac{z}{ 1 - 4z + 10z^{ 2}} .\end{aligned}\)

5. Schritt: Partialbruchzerlegung um Terme zu erhalten, deren Potenzreihe wir kennen.

6. Schritt: \(a_{ n}  = [ z^{ n}] G( z) \) (Koeffizient von \( z^{ n}\) in der Potenzreihe \( G( z) \).

Comments

Ich nehme mal an, dass im 3. Schritt die Gleichung $$G(z)=3zG(z)+10z^2G(z)+z$$

entstehen sollte? Oder kommt man tatsächlich auf deine vorgeschlagene Gleichung?

---

Ja genau, das sollte eigentlich eine 3 sein

---

Es ist $$G(z) = \frac z{1-3z-10z} = \frac 17\left(\frac 1{1-5z} - \frac 1{1+2z}\right)$$.

Mit der geometrischen Reihe ergibt sich dann für \(n\geq 0\):$$a_n = \frac 17\left(5^n - (-2)^n\right)$$