(9) (16 points) Let the sequence $\left\{a_{n}\right\}$ satisfy $a_{1}=3, a_{2}=8, a_{n+2}=2 a_{n+1}+2 a_{n}$, $n \in \mathbf{N}^{*}$, find the general term formula of the sequence $\left\{a_{n}\right\}$.
The characteristic equation corresponding to 9 is $x^{2}=2 x+2$, with characteristic roots $x_{1}=1+\sqrt{3}, x_{2}=$ $1-\sqrt{3}$. Therefore,
$$
a_{n}=A_{1}(1+\sqrt{3})^{n}+A_{2}(1-\sqrt{3})^{n} \text {, }
$$

From the initial conditions, we get
$$
\left\{\begin{array}{l}
A_{1}(1+\sqrt{3})+A_{2}(1-\sqrt{3})=3, \\
A_{1}(1+\sqrt{3})^{2}+A_{2}(1-\sqrt{3})^{2}=8,
\end{array}\right.
$$

Solving these, we find $A_{1}=\frac{2+\sqrt{3}}{2 \sqrt{3}}, A_{2}=\frac{\sqrt{3}-2}{2 \sqrt{3}}$. Thus, the general term formula for the sequence $\left\{a_{n}\right\}$ is
$$
a_{n}=\frac{2+\sqrt{3}}{2 \sqrt{3}}(1+\sqrt{3})^{n}+\frac{\sqrt{3}-2}{2 \sqrt{3}}(1-\sqrt{3})^{n} .
$$