I am trying to get a hang on the induction method for proof, but I'm still dubious of many aspect of this proof regarding its application to sequences of integers, such as the Fibonacci sequence.


Prove by induction that this is true. (These are terms in the Fibonacci Sequence)

$F_{n+3} = 2F_{n+1}+F_2F_n$

Fibonacci Numbers:

$1, 1, 2, 3, 5, 8, 13, 21… = $ $F_1,\; F_2, \; F_3, \; F_4, \; F_5, \; F_6, F_7, \; F_8 \ldots$ So, the first step I underwent was preforming some base cases:


For $n=1:$ $F_{(1)+3} = 2F_{(1)+1}+F_2F_{(1)}$

=> It should be true that $F_4 = 2F_2+F_2F_1$

By replacing the F's with the appropriate terms we get

For $n=1$: $3 = 2(1) + (1)(1) = 3$, so $3=3$ is true.


For $n=3$: $F_{(3)+3} = 2F_{(3)+1}+F_2F_{(3)}$

=> It should be true that $F_6 = 2F_4+F_2F_3$

By replacing the F's with the appropriate terms we get

For $n=3$: $8 = 2(3) + (1)(2) = 8$, so $8=8$ is true.


Inductive Hypothesis:

For $n \leq k$ it should hold that $F_{n+3} = 2F_{n+1}+F_2F_n = F_{k+3} = 2F_{k+1}+F_2F_k$

For $n \leq k+2$ it should hold that $F_{n+3} = 2F_{n+1}+F_2F_n = F_{(k+2)+3} = 2F_{(k+2)+1}+F_2F_{k+2}$

For $n \leq k+3$ it should hold that $F_{n+3} = 2F_{n+1}+F_2F_n = F_{(k+3)+3} = 2F_{(k+3)+1}+F_2F_{k+3}$

Inductive Step:

For the Inductive step we consider $k+1$. If the Inductive hypothesis is to hold, we must show that $F_{(k+1)+3} = 2F_{(k+1)+1}+F_2F_{(k+1)}$.

From here I don't know how to proceed. I don't even know if my process up to this point is correct. Looking for aid in my understanding. Thank you in advance for any helpful insights.

So, I know that from my inductive hypothesis,

$F_{k+3} = 2F_{k+1}+F_2F_k$

And in the inductive step I would like to have

$F_{k+4} = 2F_{k+2}+F_2F_{k+1}$,

  • $\begingroup$ Thank you for the edit, wasn't sure about how to do it. $\endgroup$
    – Ian Hoyos
    Nov 21 '14 at 2:22
  • $\begingroup$ That's fine. To learn you can have a look at meta.math.stackexchange.com/questions/5020/… $\endgroup$
    – John Marty
    Nov 21 '14 at 2:24
  • $\begingroup$ @John Marty: It looks like the left of the first equation should be $F_{n+3}$, not $F_n+3$ I don't think it was clear in the original post, but it comes out later. You can get that by putting braces around the subscript, so F_{n+3} $\endgroup$ Nov 21 '14 at 2:24
  • $\begingroup$ Just edited again $\endgroup$
    – Ian Hoyos
    Nov 21 '14 at 2:28

Hint. Write down what you know about $F_{k+2}$ and $F_{k + 3}$ by the induction hypothesis, and what you are trying to prove about $F_{k+4}$. Then recall that $F_{k+4} = F_{k+3} + F_{k+2}$. You'll probably see what you need to do at that point.

  • $\begingroup$ Where is the F_{k+3} that you referenced? when laid out I see F_{k+4} = 2F_{k+2}+F_2F_{k+1}. Does F_{k+3} come out of what makes up the F_{k+4} And I mean: F_{k+4} = F_{k+3} + F_k ? Forgive my formatting. $\endgroup$
    – Ian Hoyos
    Nov 21 '14 at 2:33
  • $\begingroup$ Can you edit your question with what you know from the induction hypothesis for $F_{k+3}$ and $F_{k+2}$? Use dollar signs for math. $\endgroup$
    – Mike
    Nov 21 '14 at 2:37
  • $\begingroup$ Just edited the question with what I know for $F_{k+4}$. Could $F_{k+2}$ be re-written as $F_{k+1}+F_k$? $\endgroup$
    – Ian Hoyos
    Nov 21 '14 at 2:44
  • $\begingroup$ I'm not sure how you're getting the last line. But listen, you haven't written the induction hypothesis for $F_{k+2}$ as I suggested. Also, you write "I have" in one place when what you mean is probably "I would like to have." $\endgroup$
    – Mike
    Nov 21 '14 at 2:52
  • $\begingroup$ Wow, I just got it. Thank you very much $\endgroup$
    – Ian Hoyos
    Nov 21 '14 at 3:07

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.