Example 2 (2003 Western China Mathematical Olympiad adapted) The sequence $\left\{a_{n}\right\}$ satisfies $a_{0}=0, a_{n+1}=k a_{n}+$ $\sqrt{\left(k^{2}-1\right) a_{n}^{2}+1}(n=0,1,2, \cdots, k \geqslant 2)$, where $k$ is a given positive integer. Find the general term formula of the sequence $\left\{a_{n}\right\}$.
Solution: From the given condition, we have $a_{n+1}^{2}-2 k a_{n} a_{n+1}+a_{n}^{2}-1=0$.
Therefore, $a_{n+2}^{2}-2 k a_{n+1} a_{n+2}+a_{n+1}^{2}-1=0$.
Subtracting the above two equations yields $a_{n+2}^{2}-a_{n}^{2}-2 k a_{n+1} a_{n+2}+2 k a_{n} a_{n+1}=0$.
That is, $\left(a_{n+2}-a_{n}\right)\left(a_{n+2}+a_{n}-2 k a_{n+1}\right)=0$.
We can prove that the sequence $\left\{a_{n}\right\}$ is strictly increasing, hence $a_{n+2}=2 k a_{n+1}-a_{n} \cdots$ (1)
It is easy to see that $a_{0}=0, a_{1}=1$.
The characteristic equation of (1) is $x^{2}=2 k x-1$, solving it gives $x=k \pm \sqrt{k^{2}-1}$.

Therefore, we can assume $a_{n}=A\left(k+\sqrt{k^{2}-1}\right)^{n}+B\left(k-\sqrt{k^{2}-1}\right)^{n}\left(n \in \mathbf{N}^{*}\right)$.
Combining with $a_{0}=0, a_{1}=1$, we have
$\left\{\begin{array}{l}a_{1}=A k+A \sqrt{k^{2}-1}+B k-B \sqrt{k^{2}-1}=1 \\ a_{0}=A+B=0\end{array}\right.$.
Solving it yields $A=\frac{1}{2 \sqrt{k^{2}-1}}, B=-\frac{1}{2 \sqrt{k^{2}-1}}$.
Thus, $a_{n}=\frac{1}{2 \sqrt{k^{2}-1}}\left(k+\sqrt{k^{2}-1}\right)^{n}-\frac{1}{2 \sqrt{k^{2}-1}}\left(k-\sqrt{k^{2}-1}\right)^{n}\left(n \in \mathbf{N}^{*}\right)$.
Analysis: For non-linear recurrence relations, they are generally linearized first, and then other methods are sought. In this problem, the recurrence relation is transformed into $a_{n+1}^{2}-2 k a_{n} a_{n+1}+a_{n}^{2}=1$, and by taking $n$ and $n+1$, two equations are obtained. Subtracting them further simplifies the equation, ultimately leading to a second-order linear recurrence relation.