TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 225

Berechnen Sie die folgenden Summen durch Aufstellen und Lösen einer Rekursion mittels Ansatzmethode.

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

Lösung

Ansatz: $\sum _{i=1}^{n}i^{2}=\sum _{i=1}^{n-1}i^{2}+n^{2}$

Diesen Ansatz können wir umformen in eine inhomogene Differenzengleichung 1. Grades:

$\Rightarrow x_{n}=x_{n-1}+n^{2}$

Also lösen wir zuerst die homogene Gleichung:

$x_{n}^{(h)}=x_{n-1}^{(h)}\Rightarrow x_{0}=c,c=const.$

Jetzt gilt es noch eine partikuläre Lösung zu finden:

Ansatz für Störfunktion $n^{2}:\ x_{n}^{(p)}=A_{0}+A_{1}n+A_{2}n^{2}$

Wenn $A_{0}=c$ ist, wäre die homogene Lösung hier enthalten. Da das nicht sein darf, müssen wir noch den ganzen Term mit n multiplizieren.:

$x_{n}^{(p)}=A_{0}n+A_{1}n^{2}+A_{2}n^{3}$

Dann setzen wir obigen Term hier ein: $x_{n}-x_{n-1}=n^{2}$

$A_{0}n+A_{1}n^{2}+A_{2}n^{3}-A_{0}(n-1)-A_{1}(n-1)^{2}-A_{2}(n-1)^{3}=n^{2}$

$A_{0}n+A_{1}n^{2}+A_{2}n^{3}-(A_{0}n-A_{0})-(A_{1}n^{2}-2A_{1}n+A_{1})-(A_{2}n^{3}-3A_{2}n^{2}+3A_{2}n-A_{2})=n^{2}$

$A_{0}+2A_{1}n-A_{1}+3A_{2}n^{2}-3A_{2}n+A_{2}=n^{2}$

Eine Gleichung, drei Variablen - das schreit nach Koeffizientenvergleich

quadratische Teile: $3A_{2}=1\Rightarrow A_{2}={\frac {1}{3}}$

lineare Teile: $2A_{1}-3A_{2}=0\Rightarrow A_{1}={\frac {1}{2}}$

konstante Teile: $A_{0}-A_{1}+A_{2}=0\Rightarrow A_{0}={\frac {1}{2}}-{\frac {1}{3}}={\frac {1}{6}}$

$\Rightarrow x_{n}^{(p)}={\frac {1}{3}}n^{3}+{\frac {1}{2}}n^{2}+{\frac {1}{6}}n$

Durch Zusammensetzen ergibt sich die allgemeine Lösung:

$x_{n}=x_{n}^{(h)}+x_{n}^{(p)}={\frac {1}{3}}n^{3}+{\frac {1}{2}}n^{2}+{\frac {1}{6}}n+c$