Moins difficile qu'il n'en a l'air.

Pour $u_0=3$ on a, sauf erreur, $v_n=F_{2^{n+2}}$

avec $F_m$, le m-ième nombre de Fibonacci.

Si $-2\leq u_{0}\leq 2$ soit $\theta =\arccos \frac{u_{0}}{2}$. Alors : $u_{n}=2\cos 2^{n}\theta =\frac{\sin 2^{n+1}\theta }{\sin 2^{n}\theta }$, d'où $v_n$.
Si $u_0>2$, de même en remplaçant $\cos$ par $\cosh$.
On peut sans doute récupérer le beau résultat de Fin de Partie avec les polynômes de Tchebychev.
Inutile de supposer $u_0$ rationnel.
Il me semble qu'on a vu ceci sur ce forum il y a peu.
Bonne fin de dimanche.
F. Ch.

Parce que $T^2 - 2aT \pm1 =0$ admet des solutions non nulles dans $\C$ ?

e.v.

Je ne sais plus où j'ai vu (ou cru voir) cet exercice. Si je le savais je le dirais.
On a intérêt à observer les propriétés des fonctions usuelles $\exp, \sin, \cos, \tan, \cot, \sinh, \cosh, \tanh, \coth$ sur $\mathbb{C}$ : zéros, périodes, ensemble de définition, ensemble-image. C'est faisable élémentairement, sans recourir à la "grande" théorie de la fonction d'une variable complexe.

Je reviens sur la contribution de Fin de Partie.
Pourquoi $u_0=3$ ? C'est le plus petit entier naturel pour qui la réponse n'est pas triviale. Premiers termes et OEIS, c'est l'approche moderne et expérimentale.
Je pensais prouver ce résultat avec les polynômes de Tchebychev, et c'est peut-être possible, mais j'ai une autre idée.
On connaît la formule de Binet (Jacques, pas Alfred) pour la suite de Fibonacci : $F_{n}=\frac{\alpha ^{n}-\beta ^{n}}{\alpha -\beta }$, $\alpha =\frac{1+\sqrt{5}}{2},\beta =\frac{1-\sqrt{5}}{2}$.
Si $u_0=3$ et $u_{n+1}^{{}}=u_{n}^{2}-2$ alors par récurrence : $u_{n}^{{}}=\alpha ^{2^{n+1}}+\beta ^{2^{n+1}}$, et par suite : $u_{n}^{{}}=\frac{F_{2^{n+2}}}{F_{2^{n+1}}}$. Etc.
Noter que les $u_n$ sont des nombres de Lucas.
Bonne soirée.
F. Ch.