$$\sum_{i=1}^n i$$
Rekursion: $$x_n=x_{n-1}+n \ \ , \ \ \ x_0=0$$
Homogene Lösung: $$x_n^{(H)}=x_{n-1}^{(H)}= \dots = x_{1}^{(H)}=x_{0}^{(H)}=0$$
Partikuläre Lösung: $$x_n^{(p)}=A+Bn$$
Da allerdings die homogene Lösung konstant ist und A ebenfalls konstant und somit Teil der homogenen Lösung ist, müssen wir den Term mit n multiplizieren. multiplizierenjjj
Also $$x_n^{(p)}=An+Bn^2$$
Diesen Ansatz setzen wir nun in die ursprüngliche rekursive Gleichung ein:
$$An+Bn^2=A(n-1)+B(n-1)^2+n \\ \Rightarrow An+Bn^2=An-A+Bn^2-2Bn+B+n \\ \Rightarrow (2B-1)n+(A-B)=0 \\ \Rightarrow 2B-1=0 \text{ und } A-B=0 \\ \Rightarrow A=B=\frac{1}{2}$$
Somit haben wir die partikuläre Lösung $$x_n^{(p)}=\frac{1}{2}n+\frac{1}{2}n^2$$
Also die Lösungder Rekursion ist: $$x_n=\frac{1}{2}n+\frac{1}{2}n^2=\frac{n(1+n)}{2}$$