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_1n + A_2n^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_0n + A_1n^2 + A_2n^3$

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

$A_0n+A_1n^2+A_2n^3-A_0(n-1)-A_1(n-1)^2-A_2(n-1)^3 = n^2$

$A_0n+A_1n^2+A_2n^3-(A_0n-A_0)-(A_1n^2-2A_1n+A_1)-(A_2n^3-3A_2n^2+3A_2n-A_2) = n^2$

$A_0+2A_1n-A_1+3A_2n^2-3A_2n+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$