# Induction proof for Fibonacci numbers

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.

QUESTION:

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}$,

• Thank you for the edit, wasn't sure about how to do it. – Ian Hoyos Nov 21 '14 at 2:22
• That's fine. To learn you can have a look at meta.math.stackexchange.com/questions/5020/… – John Marty Nov 21 '14 at 2:24
• @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} – Ross Millikan Nov 21 '14 at 2:24
• Just edited again – 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.
• 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. – Mike Nov 21 '14 at 2:37
• 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$? – Ian Hoyos Nov 21 '14 at 2:44
• 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." – Mike Nov 21 '14 at 2:52