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

Question

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!

Answer 1

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.

Answer 2

Let $A (a, b)$ be any extended sequence of Fibonacci such that: $A_0 = a, A_1 = b, A_{n + 2} = A_{n + 1} + A_n$.

Then the tuple $<a, b>$ represents one of those sequences.

And adding two sequences is equivalent to adding those tuples. (Linearity of sequences with respect to the sum).

With that it is easy to verify that:

$$L_{n + 4} -L_n = A(7,11) - A(2,1) = A(7-2,11-1) = A(5, 10) = 5 A(1,2) = 5F_{n + 2}$$