<s>[INST] Proof recursion is a subset of Lucas numbers I need to prove that the recursion $a_n=\frac{a_{n-1}^2+5}{a_{n-2}}$ for $a_0=2,a_1=3$ are the Lucas numbers with even index. I would like to use induction, but I got a fraction that I'm not sure how to simplify into the clean recursion for the Lucas numbers. Is induction the way to go here, or is there a way to manipulate some formula for the Lucas numbers to show that the recursion works?
 [/INST] We know that
$$L_n=\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{1-\sqrt{5}}{2}\right)^n \quad \forall\ n \in \mathbb{N}$$
you can see it here for example. To simplify the calculations, let
$$x=\frac{1+\sqrt{5}}{2}\quad and\quad y=\frac{1-\sqrt{5}}{2}$$
where $x^2+y^2=3$ and $xy=-1$. Then, (with $n\geq 2$)
\begin{align*}
a_{n}\cdot a_{n-2}-a_{n-1}^2&=L_{2n}\cdot L_{2n-2}-L_{2n-1}^2\\
&=(x^{2n}+y^{2n})\cdot (x^{2n-2}+y^{2n-2})-(x^{2n-1}+y^{2n-1})^2\\
&=x^{4n-2}+x^2\underbrace{(xy)^{2n-2}}_{1}+y^2\underbrace{(xy)^{2n-2}}_{1}+y^{4n-2}-x^{4n-2}-2\underbrace{(xy)^{2n-1}}_{-1}-y^{4n-2}\\
&=x^2+y^2+2\\
&=5
\end{align*}
Thus we have $a_n\cdot a_{n-2}-a_{n-1}^2=5$, that is,
$$a_n=\frac{a_{n-1}^2+5}{a_{n-2}}.$$
</s>