Example 4 Given $a_{1}=a_{2}=1, a_{n}=\frac{a_{n-1}^{2}+2}{a_{n-2}}(n \geqslant 3)$, find $a_{n}$.
Solution 1: We just need to find constants $p, q$ such that $a_{n}=p a_{n-1}+q a_{n-2}$, then we can use the characteristic root method to find the expression for $a_{n}$. From $a_{1}=a_{2}=1, a_{3}=\frac{a_{2}^{2}+2}{a_{1}}=3, a_{4}=\frac{a_{2}^{2}+2}{a_{2}}=11$, we get
$$
\left\{\begin{array} { l } 
{ p + q = 3 , } \\
{ 3 p + q = 1 1 , }
\end{array} \text { so } \left\{\begin{array}{l}
p=4, \\
q=-1,
\end{array}\right.\right.
$$

That is, $a_{n}=4 a_{n-1}-a_{n-2}(n \geqslant 3)$. We will prove this conclusion by induction.
Since $a_{1}=a_{2}=1, a_{3}=3$, we have $a_{3}=4 a_{2}-a_{1}$. Assume $a_{k}=4 a_{k-1}-a_{k-2}(k \geqslant 3)$, then
$$
\begin{aligned}
a_{k+1} & =\frac{a_{k}^{2}+2}{a_{k-1}}=\frac{a_{k}\left(4 a_{k-1}-a_{k-2}\right)+2}{a_{k-1}}=4 a_{k}-\frac{a_{k} a_{k-2}-2}{a_{k-1}} \\
& =4 a_{k}-\frac{1}{a_{k-1}}\left[\left(\frac{a_{k-1}^{2}+2}{a_{k-2}}\right) a_{k-2}-2\right]=4 a_{k}-a_{k-1} .
\end{aligned}
$$

This proves that for all $n \geqslant 3$, we have
$$
a_{n}=4 a_{n-1}-a_{n-2} \text {. }
$$

Since the roots of the characteristic equation $r^{2}=4 r-1$ are $r_{1,2}=2 \pm \sqrt{3}$, we have $a_{n}=c_{1}(2+\sqrt{3})^{n}+c_{2}(2-\sqrt{3})^{n}$. Define $a_{0}$ to satisfy $a_{2}=4 a_{1}-a_{0}$, i.e., $a_{0}=4 a_{1}-a_{2}=3$. From $a_{0}=3, a_{1}=1$, we get
$$
\left\{\begin{array}{l}
c_{1}+c_{2}=3, \\
c_{1}(2+\sqrt{3})+c_{2}(2-\sqrt{3})=1,
\end{array}\right.
$$

Solving, we get $c_{1}=\frac{-5+3 \sqrt{3}}{2 \sqrt{3}}, c_{2}=\frac{5+3 \sqrt{3}}{2 \sqrt{3}}$, thus
$$
a_{n}=\frac{1}{2 \sqrt{3}}\left[(-5+3 \sqrt{3})(2+\sqrt{3})^{n}+(5+3 \sqrt{3})(2-\sqrt{3})^{n}\right] \text {. }
$$

Solution 2: The original recurrence relation can be transformed into $a_{n} a_{n-2}=a_{n-1}^{2}+2$.
Substituting $n+1$ for $n$ in the above equation, we get $a_{n+1} a_{n-1}=a_{n}^{2}+2$.
Subtracting the two equations, we get $a_{n+1} a_{n-1}-a_{n} a_{n-2}=a_{n}^{2}-a_{n-1}^{2}$,
which simplifies to $\frac{a_{n+1}+a_{n-1}}{a_{n}}=\frac{a_{n}+a_{n-2}}{a_{n-1}}$.
Let $b_{n}=\frac{a_{n}+a_{n-2}}{a_{n-1}}(n \geqslant 3)$, then $b_{n}=b_{n-1}=\cdots=b_{3}=\frac{a_{3}+a_{1}}{a_{2}}=4$,
so $\frac{a_{n}+a_{n-2}}{a_{n-1}}=4$, i.e., $a_{n}=4 a_{n-1}-a_{n-2}$, and the rest is the same as Solution 1.