# $5F_{n+1} = L_{n+4} − L_n.$

I'm very new to induction proof and need some help to show that for $$n ∈ N$$ we have the relation between the Fibonacci and Lucas numbers:

$$5F_{n+1} = L_{n+4} − L_n.$$

I know that I should show true for n = 1 and k = n+1. I also know that the Fibonacci numbers are defined recursively, $$F_0 = 0, F_1 = 1$$, and $$F_n = F_{n-1}+F_{n-2}$$, for n > 1.

The Lucas numbers are defined recursively,

$$L_0 = 2, L1 = 1,$$ and $$L_n = L_{n-1}+L_{n-2}$$,for n >1.

Thanks for any help!

• You should learn the basics of Latex or Mathjax. – Jean Marie Mar 1 at 22:18
• Here is a helpful formatting reference for typesetting mathematical expressions. – Théophile Mar 1 at 22:26
• Where are you stuck? Have you tried showing it true for $n=1$? In formulas involving the Fibonaccis, it's often best to work with 'double induction' where you assume that the statement is true for $n=k$ and for $n=k-1$ and try to derive it for $n=k+1$; in this particular example, there's one natural thing to try doing from your two assumed cases... – Steven Stadnicki Mar 1 at 22:30
• Take a look at maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/… – Jean Marie Mar 1 at 22:40

Here's a few steps you can follow:

1. Show that the statement holds for $$n=0$$.

2. Show that the statement holds for $$n=1$$.

3. Assume the statement holds for every $$n$$ from $$0$$ up to $$k$$, then show that it must hold for $$n=k+1$$ as well.

Obviously 1 and 2 are the easy parts. To get you started on 3, we need to prove that $$5F_{k+2}=L_{k+5}-L_{k+1}$$. Be careful not to assume this is true! (Many people learning induction make the mistake of assuming what they are trying to prove.) Instead, use the following facts: $$F_{n+2} = F_{n+1} + F_n\\ L_{n+2} = L_{n+1} + L_n\\ \textrm{(by definition of Fibonacci and Lucas numbers)}\\ {\ }\\ 5F_{k+1}=L_{k+4}-L_{k}\\ 5F_{k}=L_{k+3}-L_{k-1}\\ \textrm{(by induction hypothesis)}\\$$

So: \begin{align} 5F_{k+2} &= 5(F_{k+1} + F_k)\\ &= \ldots\\ &= L_{k+5} - L_{k+1} \end{align}

It remains only to fill in the missing lines.

• Thank you! I believe I have started part 3 correctly: 5Fk+2 = 5(Fn+1 + Fn) = (Lk+4 - Lk) + (Lk+3 - Lk-1). Now I'm a bit stuck. Have I made a mistake, or did I begin correctly? – user635758 Mar 7 at 17:04
• @user635758 Yes, this is right. (By the way, I just noticed I had written the wrong subscripts: it should be $5F_{k+2}=5(F_{k+1}+F_k)$. Sorry for any confusion.) As a next step, rearrange your last expression like so: $(L_{k+4}-L_k)+(L_{k+3}-L_{k-1}) = (L_{k+4}+L_{k+3})-(L_k+L_{k-1})$. From there, you're basically at the end: compare this to the expression you're aiming for. – Théophile Mar 7 at 17:12
• I can't seem to get the last expression to equal Lk+5-Lk+1. If I try filling in the expressions Lk+5 - Lk+1 = (𝐿𝑘+4+𝐿𝑘+3)−(𝐿𝑘+𝐿𝑘−1) with k = 1, I get 16 = 22, which is not equal? – user635758 Mar 7 at 17:48
• @user635758 Hmm. For $k=1$, you should get $L_{k+5}-L_{k+1}=L_6-L_2=18-3=15$. And $(L_{k+4}+L_{k+3})-(L_k+L_{k-1})=(L_5+L_4)-(L_1+L_0)=(11+7)-(1+2)=18-3=15$. We know they must be equal by the very definition of Lucas numbers! – Théophile Mar 7 at 17:59
• @user635758 You're welcome! – Théophile Mar 7 at 19:03