Example 2-38 Find $S_{n}=\sum_{k=0}^{n} k$.

.
$$
\begin{array}{l}
S_{n}=1+2+3+\cdots+\overline{n-1}+n \\
S_{n-1}=1+2+3+\cdots+\overline{n-1} \\
S_{n}-S_{n-1}=n \\
S_{n-1}-S_{n-2}=n-1 \\
S_{n}-2 S_{n-1}+S_{n-2}=1 \\
S_{n-1}-2 S_{n-2}+S_{n-3}=1 \\
S_{n}-3 S_{n-1}+3 S_{n-2}-S_{n-3}=0 \\
S_{0}=0, S_{1}=1, S_{2}=3
\end{array}
$$

Then we have
Similarly
Subtracting gives
Similarly
Thus

The corresponding characteristic equation is
$$
x^{3}-3 x^{2}+3 x-1=(x-1)^{3}=0
$$
$x=1$ is a triple root.
So we have

That is
$$
\begin{array}{l}
S_{n}=\left(A+B n+C n^{2}\right)(1)^{n}=A+B n+C n^{2} \\
S_{0}=0, \quad \text { then } A=0 \\
S_{1}=1, B+C=1 \\
S_{2}=3,2 B+4 C=3 \text {, then } B=C=\frac{1}{2} \\
S_{n}=\frac{1}{2} n+\frac{1}{2} n^{2}=\frac{1}{2} n(n+1)
\end{array}
$$

This proves the formula
$$
1+2+3+\cdots+n=\frac{1}{2} n(n+1)
$$