Berechne eine Formel ... mit Hilfe von erzeugenden Funktionen

11.06.2017, 16:36

der_unkluge

Berechne eine Formel ... mit Hilfe von erzeugenden Funktionen

Wunderschönen guten Tag.
Es ist Sonntag, es ist heiß, die Sonne scheint, und ich sitze seit einer gefühlten Ewigkeit an Mathematik.

Mein Problem ist folgendes, und zwar soll ich mit hilfe von erzeugenden Funktionen eine Formel für

$\begin{eqnarray*} \sum\limits_{k=1}^{n} k^{2} \end{eqnarray*}$

finden bzw. berechnen.
Nachdem mein Kopf daran zerbrach wie ich das bewerkstelligen konnte, habe ich die Summe mal bei Wolfram Alpha eingetippt, welcher mir

$\begin{eqnarray*} \frac{1}{6} * n * (n+1)*(2n+1) \end{eqnarray*}$

ausgespuckt hat.
Soweit so gut, aber ich habe wirklich nicht mal den Hauch einer Idee wie ich von der Summe bzw. der Reihe auf diese Formel kommen soll.

Kann mir da jemand helfen?

11.06.2017, 16:39

DarkMath

Auf diesen Beitrag antworten »

Du kannst es doch einfach per Induktion zeigen und fertig.

11.06.2017, 16:42

der_unkluge

Auf diesen Beitrag antworten »

ich muss nicht zeigen, dass es das selbe ist,
ich muss die Formel aus der Summe heraus berechnen.

Wie willst du das mit Induktion anstellen?

11.06.2017, 16:44

DarkMath

Auf diesen Beitrag antworten »

Gut, dann hatte ich deine Frage nicht ganz verstanden. Ich dachte dir geht es nur um die Gleichheit.

11.06.2017, 16:45

adiutor62

Auf diesen Beitrag antworten »

http://www.arndt-bruenner.de/mathe/Allge...mmenformel1.htm

11.06.2017, 16:57

der_unkluge

Auf diesen Beitrag antworten »

Zitat:

Original von adiutor62
http://www.arndt-bruenner.de/mathe/Allge...mmenformel1.htm

Danke dass sieht sehr gut aus, aber den Konnex zu erzeugenden Funktionen finde ich auch hier nicht? :/

11.06.2017, 17:22

Clearly_wrong

Auf diesen Beitrag antworten »

Um die erzeugende Funktion von $\begin{align*} \sum_{k=1}^n k^2 \end{align*}$ zu bekommen, kann man exzessiv die Cauchy-Produktformel verwenden.

Zunächst erhalten wir $\begin{align*} \left(\sum_{n=0}^\infty z^n\right)\left(\sum_{n=1}^\infty z^n\right) = \sum_{n=0}^\infty nz^n \end{align*}$ .

Weiter gilt $\begin{align*} \left(\sum_{n=0}^\infty nz^n\right)\left(\sum_{n=0}^\infty z^n\right) = \sum_{n=0}^\infty \frac{n(n+1)}{2}z^n \end{align*}$ . Dafür wirst du die explizite Darstellung $\begin{align*} \sum_{k=1}^n k = \frac{n(n+1)}{2} \end{align*}$ brauchen.

Es folgt $\begin{align*} \sum_{n=0}^\infty n^2z^n = 2\left(\sum_{n=0}^\infty nz^n\right)\left(\sum_{n=0}^\infty z^n\right)-\sum_{n=0}^\infty nz^n = \left(\sum_{n=0}^\infty nz^n\right)\left(2\left(\sum_{n=0}^\infty z^n\right)-1\right) = \left(\sum_{n=0}^\infty nz^n\right)\left(\sum_{n=0}^\infty z^n+\sum_{n=1}^\infty z^n\right) \end{align*}$ und schließlich

$\begin{align*} \left(\sum_{n=0}^\infty n^2z^n\right)\left(\sum_{n=0}^\infty z^n\right) = \sum_{n=0}^\infty\left( \sum_{k=0}^n k^2\right) z^n \end{align*}$ .

Insgesamt gilt also $\begin{align*} \sum_{n=0}^\infty\left( \sum_{k=0}^n k^2\right) z^n = \left(\sum_{n=0}^\infty z^n\right)^2\left(\sum_{n=1}^\infty z^n\right)\left(\sum_{n=0}^\infty z^n+\sum_{n=1}^\infty z^n\right) = \left(\sum_{n=0}^\infty z^n\right)^3\left(\sum_{n=1}^\infty z^n\right)+\left(\sum_{n=0}^\infty z^n\right)^2\left(\sum_{n=1}^\infty z^n\right)^2 \end{align*}$ .

Das lässt sich leicht ausrechnen zu $\begin{align*} \frac{z+z^2}{(1-z)^4}= \frac{1}{(1-z)^2}-\frac{3}{(1-z)^3}+\frac{2}{(1-z)^4} \end{align*}$ .

Am Beispiel von $\begin{align*} \frac{1}{(1-z)^2} \end{align*}$ zeige ich dir, wie du davon wieder auf eine Reihendarstellung kommst. Die anderen Summanden machst du dann selbst.

Es ist $\begin{align*} \frac{1}{(1-z)^2} = \frac{d}{dz}\frac{1}{1-z} = \frac{d}{dz}\sum_{n=0}^\infty z^n = \sum_{n=0}^\infty \frac{d}{dz}z^n = \sum_{n=1}^\infty nz^{n-1} = \sum_{n=0}^\infty (n+1)z^n \end{align*}$ .

11.06.2017, 17:46

Clearly_wrong

Auf diesen Beitrag antworten »

Mir ist inzwischen doch was eingefallen, hab meinen Beitrag nochmal editiert.

12.06.2017, 11:57

der_unkluge

Auf diesen Beitrag antworten »

Hallo!
Vielen Dank für deine ausführliche Beschreibung.
Nachdem ich gestern mehrere Stunden dran gesessen bin, und mir auch von Kollegen Tipps geholt habe... bin ich nun kurz vorm resignieren.

Auch bei deiner Methode, scheitere ich bereits beim ersten Schritt.
Müsste nicht eigentlich:

$\begin{align*} \left(\sum_{n=0}^\infty z^n\right)\left(\sum_{n=1}^\infty z^n\right) = \sum_{n=0}^\infty (n+1)z^n \end{align*}$ sein, und nicht $\begin{align*} \sum_{n=0}^\infty nz^n \end{align*}$ ?

Weiter gilt $\begin{align*} \left(\sum_{n=0}^\infty nz^n\right)\left(\sum_{n=0}^\infty z^n\right) = \sum_{n=0}^\infty \frac{n(n+1)}{2}z^n \end{align*}$ .

Auch dieses Ergebnis ist mir, mit Cauchy, nicht ganz verständlich?
Ich weiß nicht ob ich zZ ein Brett vorm Kopf hab, oder einfach zu dumm bin.

12.06.2017, 12:56

Clearly_wrong

Auf diesen Beitrag antworten »

Zu deiner Frage zum ersten Schritt: Beachte, dass die zweite Summe nicht bei 0 beginnt, sondern bei 1.

Die Cauchy-Produktformel ist am einfachsten zu merken, wenn die Summen beide bei 0 beginnen, deswegen schreiben wir die zweite Summe auch in dieser Form als $\begin{align*} \sum_{n=0}^\infty a_n z^n \end{align*}$ mit $\begin{align*} a_0=0 \end{align*}$ und $\begin{align*} a_n = 1 \end{align*}$ für $\begin{align*} n>0 \end{align*}$ . Dadurch fällt in $\begin{align*} \sum_{k=0}^n a_k\cdot 1 \end{align*}$ der erste Summand weg und wir haben nicht $\begin{align*} n+1 \end{align*}$ Summanden, sondern nur $\begin{align*} n \end{align*}$ .

Zu deiner zweiten Frage: Damit ich dir da weiterhelfen kann, müsstest du mir einmal aufschreiben, was deiner Meinung nach herauskommt, wenn du das Cauchyprodukt anwendest. Inklusive Rechenweg bitte.

12.06.2017, 13:20

HAL 9000

Auf diesen Beitrag antworten »

Ohne inhaltlich über die Ideen von Clearly_wrong hinauszugehen, würde ich nur mal kurz darlegen, wie ich das ganze einordnen würde:

Zitat:

Original von Clearly_wrong
Es ist $\begin{align*} \frac{1}{(1-z)^2} = \frac{d}{dz}\frac{1}{1-z} = \frac{d}{dz}\sum_{n=0}^\infty z^n = \sum_{n=0}^\infty \frac{d}{dz}z^n = \sum_{n=1}^\infty nz^{n-1} = \sum_{n=0}^\infty (n+1)z^n \end{align*}$ .

Das ganze kann man durch weitere Differentiationen fortsetzen und gelangt zu dem für alle natürliche Zahlen $\begin{align*} m \end{align*}$ und komplexe $\begin{align*} |z|<1 \end{align*}$ gültigen

$\begin{align*} \frac{1}{(1-z)^{m+1}} = \sum_{n=0}^{\infty} \binom{n+m}{m} z^n\qquad (*) \end{align*}$ .

Für festes $\begin{align*} m \end{align*}$ sind diese Funktionen $\begin{align*} n\mapsto\binom{n+m}{m} \end{align*}$ Polynome, für $\begin{align*} m=0,1,\ldots \end{align*}$ bilden diese Polynome eine Basis des entsprechenden Vektorraums der Polynome über $\begin{align*} n \end{align*}$ .

Wir betrachten hier nun $\begin{align*} f(z):=\sum_{n=0}^{\infty} \left(\sum_{k=0}^n k^2\right) z^n \end{align*}$ . Zunächst erhält man (u.a. durch Indexverschiebung)

$\begin{align*} zf(z) = \sum_{n=0}^{\infty} \left(\sum_{k=0}^n k^2\right) z^{n+1} = \sum_{n=1}^{\infty} \left(\sum_{k=0}^{n-1} k^2\right) z^n \end{align*}$

und damit per Differenzbildung

$\begin{align*} (1-z)f(z) = f(z)-zf(z) = \sum_{n=0}^{\infty} n^2 z^n \end{align*}$ .

Basierend auf $\begin{align*} n^2 = (n+2)(n+1)-3(n+1)+1 = 2\binom{n+2}{2}-3\binom{n+1}{1}+\binom{n}{0} \end{align*}$ heißt das via (*) dann

$\begin{align*} (1-z)f(z) = \frac{2}{(1-z)^3}-\frac{3}{(1-z)^2}+\frac{1}{(1-z)} \end{align*}$

$\begin{align*} f(z) = \frac{2}{(1-z)^4}-\frac{3}{(1-z)^3}+\frac{1}{(1-z)^2} \end{align*}$ ,

dieselbe Gleichung steht oben auch schon mal bei Clearly_wrong, nur anders hergeleitet. Auf letztere Gleichung wenden wir erneut (*) an, diesmal in der anderen Richtung, und erhalten

$\begin{align*} f(z) = \sum_{n=0}^{\infty} \left[ 2\binom{n+3}{3}-3\binom{n+2}{2}+\binom{n+1}{1} \right] z^n \end{align*}$ .

Das Zusammenfassen des [..]-Terms ergibt dann die gesuchte Summenformel für $\begin{align*} \sum_{k=0}^n k^2 \end{align*}$ .

Kurz gesagt: Kerngedanke ist, in einem Term wie $\begin{align*} \sum_{n=0}^{\infty} P(n) z^n \end{align*}$ das Polynom $\begin{align*} P(n) \end{align*}$ nicht zur Basis $\begin{align*} \{1,n,n^2,\ldots\} \end{align*}$ darzustellen, sondern zur alternativen Basis $\begin{align*} \left\{\binom{n}{0},\binom{n+1}{1},\binom{n+2}{2},\ldots\right\} \end{align*}$ .

12.06.2017, 20:31

Clearly_wrong

Auf diesen Beitrag antworten »

Danke für die Ergänzung. Die Differenz zu betrachten, um die erzeugende Funktion herzuleiten, ist ein schöner Trick, der sich auch leichter verallgemeinern lässt, als der Cauchyprodukt-Ansatz.

Weiter ergibt sich ein schöner Beweis, dass $\begin{align*} \sum_{k=0}^n k^m \end{align*}$ immer ein Polynom höchstens (m+1). Grades sein muss und man somit eine explizite Darstellung mit Interpolationspolynomen bestimmen kann.

Neue Frage »

Antworten »

Berechne eine Formel ... mit Hilfe von erzeugenden Funktionen

Verwandte Themen