1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ You should learn the basics of Latex or Mathjax. $\endgroup$ – Jean Marie Mar 1 at 22:18
  • $\begingroup$ Here is a helpful formatting reference for typesetting mathematical expressions. $\endgroup$ – Théophile Mar 1 at 22:26
  • 1
    $\begingroup$ 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... $\endgroup$ – Steven Stadnicki Mar 1 at 22:30
  • $\begingroup$ Take a look at maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/… $\endgroup$ – Jean Marie Mar 1 at 22:40
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user635758 Mar 7 at 17:04
  • $\begingroup$ @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. $\endgroup$ – Théophile Mar 7 at 17:12
  • $\begingroup$ 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? $\endgroup$ – user635758 Mar 7 at 17:48
  • $\begingroup$ @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! $\endgroup$ – Théophile Mar 7 at 17:59
  • $\begingroup$ @user635758 You're welcome! $\endgroup$ – Théophile Mar 7 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.