Four. (20 points) Let $a_{0}=1, a_{1}=2, a_{n+1}=$ $2 a_{n-1}+n, n=1,2,3, \cdots$. Try to find the expression for $a_{n}$ (the answer should be in the form of a finite sum of expressions involving $n$, and the number of terms should be independent of $n$).
First, we have $a_{2}=2 a_{0}+1=3$. From $a_{n+1}=2 a_{n-1}+n$ and $a_{n+2}=2 a_{n}+n+1$, subtracting these gives
$$
a_{n+2}-a_{n+1}=2\left(a_{n}-a_{n-1}\right)+1.
$$

Let $b_{n}=a_{n+1}-a_{n}$, then from (1) we get
$$
b_{n+1}=2 b_{n-1}+1,
$$

where $b_{0}=a_{1}-a_{0}=1, b_{1}=a_{2}-a_{1}=3-2=1, b_{2}=2 b_{0}+1=3$.
From (2) we get $b_{n+1}+1=2\left(b_{n-1}+1\right)$.
From (3) it is easy to see that
$$
b_{2 k+1}+1=2\left(b_{2(k-1)+1}+1\right)=\cdots=2^{k}\left(b_{1}+1\right)=2^{k+1},
$$

and $b_{2 k}+1=2\left(b_{2(k-1)}+1\right)=\cdots=2^{k}\left(b_{0}+1\right)=2^{k+1}$.
Therefore, $b_{2 k+1}=2^{k+1}-1, b_{2 k}=2^{k+1}-1$.
Since $b_{i-1}=a_{i}-a_{i-1}$, we have
$$
\hat{a}_{n}-a_{0}=\sum_{i=1}^{n}\left(a_{i}-a_{i-1}\right)=\sum_{i=1}^{n} b_{i-1},
$$

which means $a_{n}=1+b_{0}+b_{1}+b_{2}+\cdots+b_{n-1}$.
From (4) and (5) we get
$$
\begin{array}{l}
a_{2 n}=1+\left(b_{0}+b_{1}\right)+\left(b_{2}+b_{3}\right)+\cdots+\left(b_{2 n-2}+b_{2 n-1}\right) \\
=1+2\left(2^{1}-1\right)+2\left(2^{2}-1\right)+\cdots+2\left(2^{n}-1\right) \\
=1-2 n+4\left(2^{n}-1\right)=2^{n+2}-2 n-3.
\end{array}
$$

Thus, $a_{2 n+1}=a_{2 n}+b_{2 n}=\left(2^{n+2}-2 n-3\right)+\left(2^{n+1}-1\right)=3 \times 2^{n+1}-2 n-4, n=0,1,2, \cdots$.
The above two formulas are the general terms of the sequence $\left\{a_{n}\right\}$.