Proof recursion is a subset of Lucas numbers

Question

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?

Answer 1

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}}.$$

Answer 2

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.