# Proving Lucas Identity by Induction

I am trying to prove the following identity (I decided to use induction, but if that's not the best way feel free to mention that in the answers):

$$L^2_n = 5F^2_n + 4(-1)^n \space\space where\space\space n\ge1$$

$L(x)$ is the corresponding Lucas number for term x, and $F(x)$ is the corresponding Fibonacci number for term x (both series are indexed at 1; the Lucas series starts {1,3,4...} and the Fibonacci series starts {1,1,2...}). I proved the base cases for $L_1=1$ and $L_2=3$, but I am having trouble with the inductive step. By induction, we know the following to be true:

$$L^2_{n-1} = 5F^2_{n-1} + 4(-1)^{n-1}$$ $$L^2_{n-2} = 5F^2_{n-2} + 4(-1)^{n-2}$$

We also know the recurrence relation for Lucas numbers: $L_n = L_{n-1} + L_{n-2}$. If we square both sides of this relation, we get $L_n^2 = L_{n-1}^2 + L_{n-2}^2 + 2L_{n-1}L_{n-2}$. The first two of these values I can use the induction hypothesis to substitute in the expressions listed above, but I'm stuck on what to do with the $2L_{n-1}L_{n-2}$ term. The only thing I have thought of so far is to try to multiply the two formulas above and then try to square root the product at the end. I start by multiplying the equations:

$$L^2_{n-1}L^2_{n-2} = (5F^2_{n-1} + 4(-1)^{n-1})(5F^2_{n-2} + 4(-1)^{n-2})$$

However that just gives me this mess:

$$25F_{n-1}^2F_{n-2}^2 + 20F_{n-2}^2(-1)^{n-1} + 20F_{n-1}^2(-1)^{n-2} - 16$$

What can I do with that? Where do I go from here? Or did I make a wrong turn?

-

## 1 Answer

I'm not sure where that's going to lead you, but here's another approach. I assume you know the identity $L_n = F_{n+1} + F_{n-1}$ ? If not, that one's an easier induction. Then \begin{align*} L_n^2 &= F_{n+1}^2 + F_{n-1}^2 + 2F_{n+1}F_{n-1} \\ &= \left(F_n + F_{n-1}\right)^2 + F_{n-1}^2 +2F_{n+1}F_{n-1}\\ &= F_n^2 + F_{n-1}^2 + 2F_{n}F_{n-1} + F_{n-1}^2 + 2F_{n+1}F_{n-1}\\ &= F_n^2 + 2F_{n-1}\left(F_{n-1}+F_n\right) + 2F_{n+1}F_{n-1}\\ &= F_n^2 + 2F_{n-1}F_{n+1} + 2F_{n+1}F_{n-1}\\ &= F_n^2 + 4F_{n-1}F_{n+1}\\ &= 5F_n^2 + 4\left(-1\right)^n \end{align*}

The last step may look mysterious if you haven't seen Cassini's identity $$\left(-1\right)^n = F_{n+1}F_{n-1} - F_{n}^2$$

The cutest way to get Cassini's identity is that

$$\left(\begin{matrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{matrix}\right) = \left(\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}\right)^n$$

and take determinants.

-