Fibonacci Recursion Equation

Question

For the Fibonacci sequence, prove the formula $a^2_{n+1} = a_n a_{n+2} + (-1)^n$ using induction.

I have done the base case, when $n=3$, because for the Fibonacci sequence, $a_1=a_2=1$. I have no idea where to start for the induction piece.

Answer 1

Assuming that $a_{k+1}^2=a_ka_{k+2}+(-1)^k$ for $k\le n$, you want to show that $$a_{n+2}^2=a_{n+1}a_{n+2}+(-1)^{n+1}$$ or, equivalently, that $$a_{n+2}^2-a_{n+1}a_{n+2}=(-1)^{n+1}\;.$$ A very straightforward approach is to begin by using the Fibonacci recurrence to expand the lefthand side:

$$\begin{align*} a_{n+2}^2-a_{n+1}a_{n+3}&=(a_{n+1}+a_n)^2-(a_n+a_{n-1})(a_{n+2}+a_{n+1})\\ &=a_{n+1}^2+2a_{n+1}a_n+a_n^2-a_na_{n+2}-a_na_{n+1}-a_{n-1}a_{n+2}-a_{n-1}a_{n+1}\\ &=(a_{n+1}^2-a_na_{n+2})+(a_n^2-a_{n-1}a_{n+1})+a_{n+1}a_n-a_{n-1}a_{n+2}\\ &=(-1)^n+(-1)^{n-1}+a_{n+1}a_n-a_{n-1}(a_{n+1}+a_n)\;. \end{align*}$$

Now see if you can simplify that last expression down to $(-1)^{n+1}$. At some point you’ll probably want to use the relationship $a_{n+1}-a_{n-1}=a_n$.

Answer 2

Hint: Replace $a_{n+1}$ with $a_{n+1}+a_n$ and one of the $a_{n+1}$ on the left with $a_n+a_{n-1}$.