TU Wien:Mathematik 2 UE (diverse)/Übungen SS07/Beispiel E11

Berechnen Sie die folgende Summe durch Aufstellen und Lösen einer Rekursion:

$\sum _{i=1}^{n}i^{2}$

Lösung von Baccus

Das Erstellen einer Rekursion aus dieser Summenformel dürfte klar sein:

$a_{n}=a_{n-1}+n^{2}$, umgeformt

$a_{n}-a_{n-1}=n^{2}$ (1).

Die charakteristische Gleichung ist also

$\lambda -1=0,\quad \lambda =1$ ($\to$ 1-fache Nullstelle).

Die harmonische Lösung ist also $a_{n}^{(h)}=A$, eine Konstante.

Für eine partikuläre Lösung müssen wir mehr Aufwand treiben (siehe auch TU Wien:Mathematik 2 UE (diverse)/Konversatorium SS07 (vermischt mit SS08)/Ansatzmethode):

Die Störfunktion in (1) ist $n^{2}$, also setzen wir ein Polynom Q(n) vom Grad 2 an:

$a_{n}^{(p)}=(B\cdot n^{2}+C\cdot n+D)\cdot n^{i}$, wobei i=1 (einfache Nullstelle bei $\lambda$).

Wir setzen in (1) ein:

$(Bn^{2}+Cn+D)n\quad -\quad \left(B(n-1)^{2}+C(n-1)+D\right)\cdot (n-1)=n^{2}$

$Bn^{3}+Cn^{2}+Dn\quad -\quad B(n^{3}-3n^{2}+3n-1)-C(n^{2}-2n+1)-D(n-1)=n^{2}$

Kürzen: $3Bn^{2}-3Bn+B+2Cn-C+D=n^{2}$,

Nach Potenzen ordnen: $3Bn^{2}+(-3B+2C)n+(B-C+D)=n^{2}$.

Diese Gleichung kann nur erfüllt sein, wenn folgendes gilt (Koeffizientenvergleich):

$\underbrace {3B} _{=1}n^{2}+\underbrace {(-3B+2C)} _{=0}n+\underbrace {(B-C+D)} _{=0}=n^{2}$.

Für die Konstanten B,C,D ergeben sich also (von linx nach rechz):

• $3B=1\quad \Rightarrow B={\tfrac {1}{3}}$;
• $-3{\tfrac {1}{3}}+2C=0\quad \Rightarrow C={\tfrac {1}{2}}$;
• ${\tfrac {1}{3}}-{\tfrac {1}{2}}+D=0\quad \Rightarrow D={\tfrac {1}{6}}$.

Also ist $a_{n}^{(p)}=({\tfrac {1}{3}}n^{2}+{\tfrac {1}{2}}n+{\tfrac {1}{6}})n$.

Eigentlich könnten wir das Beispiel hier beenden.

Exkurse

Mancher Übungsleiter besteht noch drauf, diese Lösung weiter zu "zerlegen":

• Komplettlösung:

Wir haben bisher ja nur $a^{h}$ und $a^{p}$ bestimmt; aber $a_{n}=a_{n}^{(h)}+a_{n}^{(p)}$.

Na gut: wenn wir (empirisch, aus der Angabe) $a_{0}=0$ setzen, kommen wir auf

$0=A+({\tfrac {1}{3}}n^{2}+{\tfrac {1}{2}}n+{\tfrac {1}{6}})\underbrace {n} _{=0}\quad \Longrightarrow A=0.$

Also ist $a_{n}=a_{n}^{(p)}$.

• Formelheft-Lösung:

In manchen Formelheften steht als Lösung von $\sum _{i=1}^{n}i^{2}={\tfrac {n}{6}}(n+1)(2n+1)$.

Das schaffen wir vielleicht auch noch:

Beim obigen Ergebnis ${\tfrac {1}{6}}$ herausheben: $a_{n}=n({\tfrac {1}{3}}n^{2}+{\tfrac {1}{2}}n+{\tfrac {1}{6}})={\tfrac {n}{6}}(2n^{2}+3n+1)={\tfrac {n}{6}}(n+1)(2n+1)$.

Odr? --Baccus 04:00, 14. Jun 2007 (CEST)

Links

• Diskussion im Informatik-Forum

Ähnliche Beispiele:

• TU Wien:Mathematik 2 UE (diverse)/Übungen SS07/Beispiel E10
• TU Wien:Mathematik 2 UE (diverse)/Übungen SS07/Beispiel E12