Example 3.9 Given: $u_{0}=1, u_{1}=2, u_{2}=0$ and
$$
u_{n}=2 u_{n-1}+u_{n-2}-2 u_{n-3} \quad(n \geqslant 3) \text {, }
$$

Find the general term formula for the sequence $\left\{u_{n}\right\}_{n \geqslant 0}$.
The characteristic equation of the recurrence relation
$$
u_{n}=2 u_{n-1}+u_{n-2}-2 u_{n-3} \quad(n \geqslant 3)
$$

is $x^{3}-2 x^{2}-x+2=0$, with characteristic roots $x_{1}=1, x_{2}=-1, x_{3}=$ 2, so
$$
u_{n}=c_{1}+c_{2} \cdot(-1)^{n}+c_{3} \cdot 2^{n} \quad(n=0,1,2, \cdots),
$$

where $c_{1}, c_{2}, c_{3}$ are constants to be determined. From the initial conditions, we get
$$
\left\{\begin{array}{l}
c_{1}+c_{2}+c_{3}=1, \\
c_{1}-c_{2}+2 c_{3}=2, \\
c_{1}+c_{2}+4 c_{3}=0 .
\end{array}\right.
$$

Solving this system of equations yields $c_{1}=2, c_{2}=-\frac{2}{3}, c_{3}=-\frac{1}{3}$, so
$$
u_{n}=2-\frac{2}{3}(-1)^{n}-\frac{1}{3} 2^{n} \quad(n=0,1,2, \cdots) .
$$