Formeln aus Rekursionen herleiten

31.12.2018, 23:04

Studentu

Formeln aus Rekursionen herleiten

Liebe Boardmitglieder,

ich hänge zur Zeit bei einem Beispiel, wo es eigentlich nur um geschicktes Umformen geht. Aber ich habe jetzt schon stundenlang rumprobiert und komme leider trotzdem nicht darauf, darum würde ich mich über eure Hilfe sehr freuen.
Sei für $\begin{eqnarray*} A_n \end{eqnarray*}$ (die mittlere interne Pfadlänge von digitalen Suchbäumen mit $\begin{eqnarray*} n \geq 1 \end{eqnarray*}$ Daten) folgende Rekursion bekannt: $\begin{eqnarray*} A_n= n-1 + \sum_{k=0}^{n-1}2^{1-n}\binom{n-1}{k}(A_k+A_{n-1-k}) \end{eqnarray*}$ .
a) Sei $\begin{eqnarray*} A(z) = \sum_{n \geq 0}A_n \frac{z^n}{n!} \end{eqnarray*}$ . Zeige: A'(z) = $\begin{eqnarray*} ze^z+2e^{\frac{z}{2}}A(\frac{z}{2}) \end{eqnarray*}$ .
Ich habe es bislang nur geschafft, das Ganze so darzustellen, dass ich auf den Summanden $\begin{eqnarray*} ze^z \end{eqnarray*}$ komme, aber den Rest kriege ich leider nicht heraus. (Auch bin ich mir nicht sicher, ob ich das richtig gemacht habe, weil ich den auftretenden Bruch mit (0-1)! im Nenner einfach wegfallen habe lassen, weil der ja nicht definiert ist.
b) Sei $\begin{eqnarray*} B(z) = e^{-z}A(z) \end{eqnarray*}$ . Zeige B'(z) + B(z) = $\begin{eqnarray*} z+2B(\frac{z}{2}) \end{eqnarray*}$ .
Das habe ich geschafft.
c) Sei B(z) = $\begin{eqnarray*} \sum_{n \geq 0}B_n \frac{z^n}{n!} \end{eqnarray*}$ .
I) Zeige: $\begin{eqnarray*} B_n = -(1-2^{2-n})B_{n-1}, n\geq 3 \end{eqnarray*}$ ,
bzw. für $\begin{eqnarray*} n \geq 2: \quad B_n = (-1)^nQ_{n-2}, \end{eqnarray*}$ wobei $\begin{eqnarray*} Q_n = \prod_{1 \leq j \leq n}(1-\frac{1}{2^j}) \end{eqnarray*}$ .
Hier komme ich leider absolut nicht voran, bei beiden Unterpunkten nicht.
II) Folgere daraus für $\begin{eqnarray*} n \geq 2: \quad A_n = \sum_{k=2}^n\binom{n}{k}(-1)^kQ_{k-2} \end{eqnarray*}$ .
Das habe ich auch noch nicht geschafft, ich muss mich aber noch genauer damit beschäftigen.

Würde mich über eure Antworten freuen. smile

P.S.: Gutes neues Jahr an alle!

02.01.2019, 10:43

Leopold

Auf diesen Beitrag antworten »

RE: Formeln aus Rekursionen herleiten

Zitat:

Original von Studentu
$\begin{eqnarray*} A_n= n-1 + \sum_{k=0}^{n-1} \color{red} 2^{1-n} \color{black} \binom{n-1}{k}(A_k+A_{n-1-k}) \end{eqnarray*}$

Bei so etwas werde ich immer stutzig. Warum steht der Faktor nicht vor dem Summenzeichen? verwirrt

Wegen $\begin{align*} {{n-1} \choose k} = {{n-1} \choose {n-1-k}} \end{align*}$ wären die Summen $\begin{align*} \sum_{k=0}^{n-1} {{n-1} \choose k} A_k \end{align*}$ und $\begin{align*} \sum_{k=0}^{n-1} {{n-1} \choose k} A_{n-1-k} \end{align*}$ ja auch gleich.

02.01.2019, 14:55

Studentu

Auf diesen Beitrag antworten »

Hallo Leopold,

danke für deine Antwort!
Meinst du mit stutzig, dass das wohl schon ein Hinweis für die Aufspaltungen ist, dass der Faktor drinnen steht? Ich habe da nämlich nur die Angabe abgeschrieben und in meinen Rechnungen habe ich den Faktor dann auch gleich rausgezogen, weil ich mir damit leichter tue.

Guter Hinweis, vielleicht komme ich damit weiter! Ich melde mich dann wieder bzgl. a). Hast du für c) vielleicht auch schon einen Tipp?

02.01.2019, 15:06

Leopold

Auf diesen Beitrag antworten »

Es macht mich insofern stutzig, als ich mir überlege, ob es nicht $\begin{align*} 2^{1-k} \end{align*}$ heißen müßte. Denn warum sollte man den Term umständlich schreiben, wenn es auch einfacher geht? Was ist übrigens der Rekursionsanfangswert?

02.01.2019, 15:33

Helferlein

Auf diesen Beitrag antworten »

@Leopold: Die Angaben sind korrekt. Sie stammen anscheinend aus einer Vorlesung der TU Wien (Aufgabe 61-63) zu Thema Analyse von Algorithmen.

02.01.2019, 16:17

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Studentu
Ich habe es bislang nur geschafft, das Ganze so darzustellen, dass ich auf den Summanden $\begin{eqnarray*} ze^z \end{eqnarray*}$ komme, aber den Rest kriege ich leider nicht heraus.

Der Rest klappt an sich, wenn man Leopolds Bemerkung der Summengleichheit verarbeitet, d.h., mit der Rekursion

$\begin{eqnarray*} A_n= n-1 + 2^{2-n}\sum_{k=0}^{n-1}\binom{n-1}{k} A_k \end{eqnarray*}$

arbeitet. Für den "Rest" kann man die Summationen über $\begin{eqnarray*} n \end{eqnarray*}$ und $\begin{eqnarray*} k \end{eqnarray*}$ vertauschen, da vereinfacht sich so manches.

Zitat:

Original von Studentu
weil ich den auftretenden Bruch mit (0-1)! im Nenner einfach wegfallen habe lassen, weil der ja nicht definiert ist.

Klingt unseriös. Achte auf den Summationsbereich - ist der sorgfältig gewählt, dann treten fragwürdige Terme wie (0-1)! erst gar nicht auf.

02.01.2019, 19:55

Studentu

Auf diesen Beitrag antworten »

Danke euch, Leopold, Helferlein und Hal 9000!

@Helferlein: Die von dir verlinkte Datei ist zwar von 2010, aber die dortigen Bspe. 62-63 entsprechen tatsächlich der von mir zu lösen versuchten Aufgabe.

@Hal 9000 & Leopold: Mit dem Hinweis von Leopold hat nun a) geklappt. Das (n-1)! hatte ich im Nenner, weil ich nicht beachtet habe, dass z^(n=0) abgeleitet ja sowieso wegfällt.

Habt ihr auch noch Tipps für c) I) und II)?

03.01.2019, 09:22

HAL 9000

Auf diesen Beitrag antworten »

Naja, bei a) bist du ausgehend von der Rekursionsgleichung der $\begin{eqnarray*} A_n \end{eqnarray*}$ zu dieser Gleichung für $\begin{eqnarray*} A(z) \end{eqnarray*}$ gelangt. Nun hast du eine ähnliche Gleichung für $\begin{eqnarray*} B(z) \end{eqnarray*}$ und gehst den ganzen Weg rückwärts, d.h., bastelst daraus eine Rekursion für die $\begin{eqnarray*} B_n \end{eqnarray*}$ - das ist doch naheliegend. Also einfach mal in diese Gleichung den Ansatz $\begin{eqnarray*} B(z) = \sum_{n=0}^{\infty} B_n \frac{z^n}{n!} \end{eqnarray*}$ resp. $\begin{eqnarray*} B'(z) = \sum_{n=0}^{\infty} B_{n+1} \frac{z^n}{n!} \end{eqnarray*}$ in $\begin{eqnarray*} z = B'(z) + B(z)-2B\left(\frac{z}{2}\right) \end{eqnarray*}$ einsetzen ergibt

$\begin{eqnarray*} z = \sum_{n=0}^{\infty} \left( B_{n+1} + B_n - \frac{2}{2^n}B_n \right) z^n \end{eqnarray*}$

Für $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ zieht der Koeffizientenvergleich $\begin{eqnarray*} B_{n+1} + B_n - \frac{2}{2^n}B_n=0 \end{eqnarray*}$ nach sich, das ergibt umgestellt $\begin{eqnarray*} B_{n+1} = -\left(1-2^{1-n}\right)B_n \end{eqnarray*}$ . Um Eins indexverschoben ergibt das das gewünschte $\begin{eqnarray*} B_n = -\left(1-2^{2-n}\right)B_{n-1} \end{eqnarray*}$ für alle $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ .

Schauen wir uns noch den "Start" an: Für $\begin{eqnarray*} n=1 \end{eqnarray*}$ ergibt der Koeffizientenvergleich $\begin{eqnarray*} B_{n+1} + B_n - \frac{2}{2^n}B_n=1 \end{eqnarray*}$ , also $\begin{eqnarray*} B_2=1 \end{eqnarray*}$ . Insgesamt haben wir damit für $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ die explizite Darstellung

$\begin{eqnarray*} B_n = B_2 \prod_{k=3}^n \left(-\left(1-2^{2-k}\right)\right) = \prod_{j=1}^{n-2} \left(-\left(1-2^{-j}\right)\right) = (-1)^{n-2} Q_{n-2} = (-1)^n Q_{n-2} \end{eqnarray*}$ .

Zu II) Betrachte $\begin{eqnarray*} A(z) = e^z B(z) = \sum_{k=0}^{\infty} \frac{1}{k!} z^k \cdot \sum_{n=0}^{\infty} \frac{B_n}{n!} z^n \end{eqnarray*}$ unter dem Blickwinkel Cauchy-Produkt.

03.01.2019, 18:13

Studentu

Auf diesen Beitrag antworten »

Hallo Hal, das hat nun geklappt so wie du es geraten hast!
Einziges "Problem" dabei: In der inneren Summe wird zunächst auch über $\begin{eqnarray*} B_0 \end{eqnarray*}$ und $\begin{eqnarray*} B_1 \end{eqnarray*}$ summiert, was nicht wegfallen würde. (Mit dem Koeffizientenvergleich in I) sieht man lediglich $\begin{eqnarray*} B_0 = -B_1 \end{eqnarray*}$ .) Weißt du eine Begründung, warum die beiden Summanden wegfallen? (Eventuell, dass $\begin{eqnarray*} A_0 = 0 \end{eqnarray*}$ ist und daher auch $\begin{eqnarray*} B_0 = 0 \end{eqnarray*}$ sein muss und somit auch $\begin{eqnarray*} -0 = B_1 \end{eqnarray*}$ folgt?)

03.01.2019, 22:41

HAL 9000

Auf diesen Beitrag antworten »

Wir wissen $\begin{eqnarray*} A_0=A_1=0 \end{eqnarray*}$ . Daraus kann man (z.B. via die ersten beiden Cauchy-Produkt-Werte) dann auch $\begin{eqnarray*} B_0=B_1=0 \end{eqnarray*}$ folgern. Könnte sein, dass du genau das mit deinem letzten Satz (den in Klammern) gemeint hast.

10.01.2019, 04:05

Studentu

Auf diesen Beitrag antworten »

Ja genau, das hatte ich mir schon so gedacht.
Danke für deine Hilfe, Hal 9000 und danke auch an Leopold und Helferlein für die Beteiligung!

Neue Frage »

Antworten »

Formeln aus Rekursionen herleiten

Verwandte Themen