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?
 A: 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}}.$$
A: Starting with the recursive statement
$$a_n=\frac{a_{n-1}^2+5}{a_{n-2}}$$
we can manipulate it into
$$a_na_{n-2}-a_{n-1}^2=5$$
Shifting the indices also gives that
$$a_{n-1}a_{n-3}-a_{n-2}^2=5$$
Subtracting the two equations gives
$$(a_n+a_{n-2})a_{n-2}-(a_{n-1}+a_{n-3})a_{n-1}=0$$
$$(a_n+a_{n-2})a_{n-2}=(a_{n-1}+a_{n-3})a_{n-1}$$
$$\frac{a_n+a_{n-2}}{a_{n-1}}=\frac{a_{n-1}+a_{n-3}}{a_{n-2}}$$
Now consider the sequence $b_n=\frac{a_{n+1}+a_{n-1}}{a_n}$. We can evaluate that $a_2=7$, so $b_1=\frac{2+7}{3}=3$. We also have the recursion
$$b_{n-1}=b_{n-2}$$
Hence, it follows that $b_n=3$. Now we have that
$$\frac{a_n+a_{n-2}}{a_{n-1}}=3$$
$$a_n=3a_{n-1}-a_{n-2}$$
You might recognize this recurrence (or if you don't, still continue reading). Notice that the Lucas numbers follow a similar recursion that
$$L_n=L_{n-1}+L_{n-2}$$
$$\implies L_n=2L_{n-2}+L_{n-3}$$
$$\implies L_n=3L_{n-2}-L_{n-4}$$
Moreover, $L_0=2=a_0$ and $L_2=3=a_1$. Since $a_n$ and $L_{2n}$ follow the same recurrence relation and the same initial values it follows that $a_n=L_{2n}$. Hence $a_n$ is a subset of the Lucas numbers.
