Prove by Induction $F_{2n} = F_{n} * L_{n}$, for n >= 1

Question

Where $F$ is the Fibonacci Sequence, and $L$ is the Lucas Sequence. I need to find the inductive proof of this statement. I've got nearly a page of work in front of me trying to use definitions such as $L_{n} = F_{n-1} + F_{n+1}$, but I keep running into dead ends. The farthest I've appeared to have gotten with the proofs is:

$F_{2n+2} = F_{n+1} * L_{n+1}$ ->

$F_{2n+2} = F_{n+1} * (F_{n} + F_{n+2})$ ->

$F_{2n} + F_{2n+1} = F_{n+1} * (F_{n} + F_{n+2})$ ->

$(F_{n}*L_{n}) + F_{2n+1} = F_{n+1} * (F_{n} + F_{n+2})$

... but I'm not sure where to go from here, or even if my proof is heading in the correct direction. Proof writing is not my forte, so help with this proof is appreciated.

Edit: While @pjhuxford provided an excellent proof for it, I actually need a proof by induction.

Answer 1

One way to have an induction based proof is modify your induction statement to something stronger which give you a better connection between the statement for successive $n$.

Consider following induction statements:

$$\mathcal{S}_n = \begin{cases} F_{2n-1} &= F_{n}^2 + F_{n-1}^2\\ F_{2n} &= F_n L_n = F_n (F_{n+1} + F_{n-1}) \end{cases}$$

It is easy to check $\mathcal{S}_1$ is true (with $F_0 = 0$). Assume $\mathcal{S}_n$ is true, we have

$$\begin{align} F_{2n+1} = F_{2n} + F_{2n-1} &= F_n(F_{n+1} + F_{n-1}) + F_{n-1}^2 + F_n^2\\ &= F_n F_{n+1} + (F_n + F_{n-1})F_{n-1} + F_{n}^2\\ &= F_n F_{n+1} + F_{n+1} F_{n-1} + F_{n}^2\\ &= F_{n+1}(F_n + F_{n-1}) + F_{n}^2\\ &= F_{n+1}^2 + F_{n}^2 \end{align} $$ and $$\begin{align} F_{2n+2} = F_{2n+1} + F_{2n} &= F_{n+1}^2 + \color{red}{F_{n}^2} + \color{green}{F_nF_{n+1}} + F_nF_{n-1}\\ &= F_{n+1}^2 + \color{green}{F_n F_{n+1}} + \color{red}{F_{n}^2} + F_nF_{n-1}\\ &= F_{n+1}(F_{n+1} + F_{n}) + F_n(F_{n} + F_{n-1})\\ &= F_{n+1}F_{n+2} + F_n F_{n+1}\\ &= F_{n+1}(F_{n+2} + F_{n})\\ &= F_{n+1}L_{n+1} \end{align} $$ This means $\mathcal{S}_{n} \implies \mathcal{S}_{n+1}$ and by induction, $\mathcal{S}_n$ is true for all $n$. What you want to prove now follows immediately.

Answer 2

This is probably a bit overkill for this problem, but it is possible to prove that

$$F_n=\frac{(1+\sqrt{5})^n-(1-\sqrt{5})^n}{2^n\sqrt{5}},\;L_n=\frac{(1+\sqrt{5})^n+(1-\sqrt{5})^n}{2^n}$$

Once this is done, then

$$F_nL_n=\frac{\left((1+\sqrt{5})^n-(1-\sqrt{5})^n\right)\left((1+\sqrt{5})^n+(1-\sqrt{5})^n\right)}{2^{2n}\sqrt{5}}=\frac{(1+\sqrt{5})^{2n}-(1-\sqrt{5})^{2n}}{2^{2n}\sqrt{5}}=F_{2n}$$

Answer 3

The fastest way to prove your identity is not to use induction, but just the Binet formula and the identity $a^2-b^2 = (a-b)(a+b)$. Since: $$ F_n = \frac{1}{\sqrt{5}}\left(\sigma^n-\bar{\sigma}^n\right),\qquad L_n = \left(\sigma^n+\bar{\sigma}^n\right) $$ where $\sigma,\bar{\sigma}$ are the roots of the polynomial $x^2-x-1$, the identity is trivial.

As an alternative, in order to prove that $F_{2n}=F_n\cdot L_n$ holds by induction, we can use the addition formula: $$ F_{a+b} = F_{a} F_{b-1} + F_{b} F_{a+1} $$ from which it follows that: $$ F_{2n} = F_n\cdot(F_{n-1}+F_{n+1}).\tag{1} $$ Hence we just need to show that: $$ L_n = F_{n-1}+F_{n+1}, \tag{2}$$ but this is trivial since the identity holds for $n=1,2$ and both the RHS and the LHS satisfy the recurrence relation $X_{n+2}=X_{n+1}+X_n$.

Answer 4

We show by induction that $F_{2n}=F_{n}L_{n}$ and $2F_{2n-1}=F_{n-1}L_{n}+F_{n}L_{n-1}$ for $n\ge1$:

1) When $n=1$, $F_2=1=1\cdot1=F_1L_1$ $\;\;$and $\;\;$$2F_1=2=0\cdot1+1\cdot2$.

2) Assume that $F_{2m}=F_{m}L_{m}$ and $2F_{2m-1}=F_{m-1}L_{m}+F_{m}L_{m-1}$ for $1\le m\le n$ for some $n\in\mathbb{N}$. Then

$\;\;\;F_{2n+2}=F_{2n+1}+F_{2n}=F_{2n}+F_{2n-1}+F_nL_n=[F_{2n}+F_{2n-1}-F_{2n-2}]+F_{2n-2}+F_nL_n$

$\;\;=2F_{2n-1}+F_{n-1}L_{n-1}+F_nL_n=F_{n-1}L_n+F_nL_{n-1}+F_{n-1}L_{n-1}+F_nL_n$

$\;\;=(F_n+F_{n-1})(L_n+L_{n-1})=F_{n+1}L_{n+1}$ $\;\;\;$and

$\;\;\;2F_{2n+1}=2(F_{2n}+F_{2n-1})=2F_{n}L_{n}+F_{n-1}L_{n}+F_{n}L_{n-1}=(F_n+F_{n-1})L_n+F_{n}(L_n+L_{n-1})$

$\;\;=F_{n+1}L_n+F_nL_{n+1}.$

Answer 5

If you are working from the definition $L_n = F_{n-1} + F_{n+1}$, then you want to show $F_{2n} = F_n F_{n-1} + F_{n+1} F_n$.

Let's show that, for any $m$, $F_n F_m + F_{n+1}F_{m+1} = F_{n+m+1}$, by induction on $n$.

In fact, if we fix some particular $m$, then both sides satisfy the Fibonacci recurrence as sequences indexed by $n$. So it's enough to check that this holds for $n=0$ and $n=1$.

Indeed, $F_0 F_m + F_1 F_{m+1} = F_{m+1} = F_{0+m+1}$, and $F_1 F_m + F_2 F_{m+1} = F_m + F_{m+1} = F_{m+2} = F_{1+m+1}$, so, by induction, the two sequences are equal for all $n$.