Example 2-39 Find $S_{n}=\sum_{k=0}^{n} k^{2}$.
$$
\begin{array}{l}
S_{n}=1+2^{2}+3^{2}+\cdots+(n-1)^{2}+n^{2} \\
S_{n-1}=1+2^{2}+3^{2}+\cdots+(n-1)^{2} \\
S_{n}-S_{n-1}=n^{2} \\
S_{n-1}-S_{n-2}=(n-1)^{2} \\
S_{n}-2 S_{n-1}+S_{n-2}=2 n-1 \\
S_{n-1}-2 S_{n-2}+S_{n-3}=2(n-1)-1 \\
S_{n}-3 S_{n-1}+3 S_{n-2}-S_{n-3}=2 \\
S_{n-1}-3 S_{n-2}+3 S_{n-3}-S_{n-4}=2 \\
S_{n}-4 S_{n-1}+6 S_{n-2}-4 S_{n-3}+S_{n-4}=0 \\
S_{0}=0, S_{1}=1, S_{2}=5, S_{3}=14
\end{array}
$$

Then we have
Similarly
Subtracting gives
Similarly
Subtracting gives
Similarly
Then
$S_{n}-S_{n-1}=n^{2}$
$S_{n-1}-S_{n-2}=(n-1)^{2}$
$S_{n}-2 S_{n-1}+S_{n-2}=2 n-1$
$S_{n-1}-2 S_{n-2}+S_{n-3}=2(n-1)-1$
$S_{n}-3 S_{n-1}+3 S_{n-2}-S_{n \cdot 3}=2$
$S_{n \cdots 1}-3 S_{n-2}+3 S_{n-3}-S_{n-4}=2$
$S_{n}-4 S_{n-1}+6 S_{n-2}-4 S_{n-3}+S_{n-4}=0$
$S_{0}=0, S_{1}=1, S_{2}=5, S_{3}=14$

The corresponding characteristic equation is:
$$
x^{4}-4 x^{3}+6 x^{2}-4 x+1=(x-1)^{4}=0
$$
$x=1$ is a 4-fold root.
So we have
$$
S_{n}=\left(A+B n+C n^{2}+D n^{3}\right) 1^{n}
$$

Based on $S_{0}=0, S_{1}=1, S_{2}=5, S_{3}=14$, we get a system of equations for $A, B, C, D$:
$$
\begin{array}{c}
\left\{\begin{array}{l}
A=0 \\
B+C+D=1 \\
2 B+4 C+8 D=5 \\
3 B+9 C+27 D=14
\end{array}\right. \\
\left|\begin{array}{lll}
1 & 1 & 1 \\
2 & 4 & 8 \\
3 & 9 & 27
\end{array}\right|=12 \\
B=\frac{1}{12}\left|\begin{array}{ccc}
5 & 4 & 8 \\
14 & 9 & 27
\end{array}\right|=\frac{1}{6} \\
C=\frac{1}{12}\left|\begin{array}{ccc}
1 & 1 & 1 \\
2 & 5 & 8 \\
3 & 14 & 27
\end{array}\right|=\frac{1}{2}, D=\frac{1}{3}
\end{array}
$$

Then
$$
S_{n}=\frac{1}{6} n+\frac{1}{2} n^{2}+\frac{1}{3} n^{3}=\frac{1}{6} n\left(1+3 n+2 n^{2}\right)=\frac{1}{6} n(n+1)(2 n+1)
$$

Given that $S_{n}$ is a cubic polynomial in $n$, we can assume
$$
S_{n}=A+B n+\frac{1}{2!} C n(n-1)+\frac{1}{3!} D n(n-1)(n-2)
$$

This is more convenient for determining the undetermined coefficients without solving a system of equations.
For example, when $n=0$, $S_{0}=A=0$;
When $n=1$, $S_{1}=A+B=1$, then $B=1$;
When $n=2$, $S_{2}=2 B+C=5$, then $C=3$;
When $n=3$, $S_{3}=3 B+3 C+D=14$, then $D=2$;
Hence
$$
S_{n}=n+\frac{3}{2} n(n-1)+\frac{1}{3} n(n-1)(n-2)=\frac{1}{6} n(n+1)(2 n+1)
$$