Rekursion auflösen mit erzeugender Funktion

Question

Aufgabe:

Die Rekursion $a_n = a_{n-1} \cdot \dfrac{2n-1}{2(n+1)}$ mit $a_0= \dfrac{1 }{2}$ soll mit Hilfe der erzeugenden Funktion $f=\sum\limits_{k=0}^{\infty} a_n \cdot x^{n }$ in eine explizite Form für $a_n$ gebracht werden.

Problem/Ansatz:

Ich setze zunächst die Rekursion in die formale Potenzreihe ein:

$f=\sum\limits_{k=0}^{\infty} a_n \cdot x^{n } = \sum\limits_{k=1}^{\infty} a_{n-1} \cdot \dfrac{2n-1}{2(n+1)} \cdot x^{n }$

Dann führe ich eine Indexverschiebung durch:

$f=\sum\limits_{k=0}^{\infty} a_{n} \cdot \dfrac{2(n+1)-1}{2(n+1+1)} \cdot x^{n+1 }=\sum\limits_{k=0}^{\infty} a_{n} \cdot \dfrac{2n+1}{(n+2)} \cdot x^{n+1 }$

Durch Ausklammern von x erhält man:

$f= x \cdot \sum\limits_{k=0}^{\infty} a_{n} \cdot \dfrac{2n+1}{(n+2)} \cdot x^{n }$

Den Term kann man noch in zwei Summanden aufteilen:

$f= x \cdot \sum\limits_{k=0}^{\infty} a_{n} \cdot \dfrac{2n}{(n+2)} \cdot x^{n } + x \cdot \sum\limits_{k=0}^{\infty} a_{n} \cdot \dfrac{1}{(n+2)} \cdot x^{n }$

Wie mache ich jetzt weiter? Was ist mit dem Anfangswert $a_0= \dfrac{1 }{2}$ ?

Normalerweise ergibt sich bei den "klassischen" Fällen meist irgendwo eine eine Beziehung z.B. von der Art:

$x \cdot \sum\limits_{k=0}^{\infty} (n+1) \cdot x^{n } = \dfrac{x}{(1-x^{2})}$

Damit kann man dann gezielt weiter rechnen und die Funktion f ermitteln.

Gibt es hier vielleicht eine ähnliche Möglichkeit?

Comments

Sorry!!

Schreibfehler: k= muss natürlich n= heißen !!

---

Überprüfe bitte die Aufgabenstellung, denn so wie ich die Methode "erzeugende Funktion" kenne liefert sie keine gescheite Lösung.

Zunächst die Berechnung einiger Folgenglieder :

a₀ = 1/2 , a₁ = 1/2*1/4 = 1/8 , a₂ = 1/8*3/6 = 1/16 , a₃ = 1/16*5/8 = 5/128 , a₄ = 5/128*7/10 = 7/256

Dann eine Umformung der Rekursion :

a_n = (2n-1)/(2*(n+1))*a_n-1 ⇔  (n+1)*a_n = ((2n-2)*a_n-1 + a_n-1)/2 

⇔  n*a_n + a_n = (n-1)*a_n-1 + 1/2*a_n-1  (Zur Überprüfung mit n=4 : 4*7/256 + 7/256  =  3*5/128 + 1/2*5/128  ist wegen (28+7)/256 = (30+5)/256 wahr)

Leider versehentlich zu früh abgeschickt, Rest folgt gleich.

---

Überprüfe bitte die Aufgabenstellung, denn so wie ich die Methode "erzeugende Funktion" kenne liefert sie keine gescheite Lösung.

Zunächst die Berechnung einiger Folgenglieder :

a₀ = 1/2 , a₁ = 1/2*1/4 = 1/8 , a₂ = 1/8*3/6 = 1/16 , a₃ = 1/16*5/8 = 5/128 , a₄ = 5/128*7/10 = 7/256

Dann eine Umformung der Rekursion :

a_n = (2n-1)/(2*(n+1))*a_n-1 ⇔  (n+1)*a_n = ((2n-2)*a_n-1 + a_n-1)/2
⇔  n*a_n + a_n = (n-1)*a_n-1 + 1/2*a_n-1 
(Zur Überprüfung mit n=4 : 4*7/256 + 7/256  =  3*5/128 + 1/2*5/128  ist wegen (28+7)/256 = (30+5)/256 wahr)

Dann etwas zur erzeugenden Funktion : (zur Schreibvereinfachung schreibe ich nur den unteren Summationsanfang)

f(x) = ∑₀ a_nxⁿ ⇒ f '(x) = ∑₀ n*a_nx^n-1 ⇒  x*f '(x) = ∑₀ n*a_nxⁿ   

Aus der umgeformten Rekursion folgt durch Multiplikation mit xⁿ und Summation von n=1 bis unendlich :

∑₁ n*a_nxⁿ + ∑₁ a_nxⁿ =  ∑₁ (n-1)*a_n-1xⁿ + 1/2*∑₁ a_n-1xⁿ

⇔  ∑₀ n*a_nxⁿ + ∑₀ a_nxⁿ - a₀x⁰  =  x*∑₀ n*a_nxⁿ + 1/2*x*∑₀ a_nxⁿ

⇔  x*f '(x) + f(x) - a0  =  x²*f '(x) + 1/2*x*f(x)


Üblicherweise wird jetzt diese Differentialgleichung gelöst, die ermittelte Funktion f in eine Taylorreihe umgewandelt und die dabei entstehenden Koeffizienten a_n sind die gesuchte explizite Darstellung der Folge.

Mit WolframAlpha ergibt sich im vorliegenden Fall Folgendes :
https://www.wolframalpha.com/input?i=x*y%27%2By-1%2F2+%3D+x%5E2*y%27…

Der Summand 1/x in der Lösung y(x) = c_1 e^(1/2 (log(1 - x) - 2 log(x))) + 1/x lässt stutzen, denn er ist für x=0 nicht definiert.

Nach der Taylor-Entwicklung gefragt bekommt man diese Antwort :
https://www.wolframalpha.com/input?i=taylor+series+of+%28c_1+e%5E%28…

Dabei erkenne ich in (c_1 + 1)/x - c_1/2 - (c_1 x)/8 - (c_1 x²)/16 - (5 c_1 x³)/128 - (7 c_1 x⁴)/256 + O(x⁵) (Laurent series) durchaus einen Zusammenhang mit den händisch berechneten Folgegliedern, allerdings ohne eine geschlossene Darstellung der Koeffizienten keine Lösung der Aufgabe.

---

Vielen Dank für die ausführliche Antwort.

Meine Fragestellung war das Ergebnis einiger Studien zu Differenzengleichungen und damit im Zusammenhang stehender erzeugender Funktionen.

Leider wird in der "normalen" Literatur als Paradebeispiel immer nur die Fibonacci Folge ausführlich erklärt.

Für geometrische Reihen fand ich zufällig hier einen kurze Beschreibung zur Lösung:

Wie gesagt, man muss immer zufäliig eine bestimmte Form von Gleichung finden oder entsprechend konstruieren, um geschickt ausklammern zu können. Diem Klassiker sind hier die Partialsummen von Folgen der natürlichen Zahlen, Quadratzahlen, Kubikzahlen. Leider scheint das in meinem Beispiel aber nicht zu funktionieren.

Trotzdem vielen Dank! Ich werde mir auf jeden Fall noch die Lösung der Differentialgleichung genauer anschauen.