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