Strong induction with Fibonacci numbers I have two equations that I have been trying to prove. The first of which is:F(n + 3) = 2F(n + 1) + F(n) for n ≥ 1.For this equation the answer is in the back of my book and the proof is as follows:1) n = 1: F(4) = 2F(2) + F(1)  or 3 = 2(1) + 1, true.2) n = 2: F(5) = 2F(3) + F(2) or 5 = 2(2) + 1, true.3) Assume for all r, 1 ≤ r ≤ k: F(r + 3) = 2F(r + 1) + F(r)4) Then F(k + 4) = F(k + 2) + F(k + 3) = 5) 2F(k) + F(k - 1) + 2F(k + 1) + F(k) = 6) 2[F(k) + F(k + 1)] + [F(k - 1) + F(k)] = 7) 2F(k + 2) + F(k + 1)My first question here is how do I know how many values of n to test for? Here they chose two.My next question is how did they get from line 3 to line 4? I understand how the statement is correct but why is this chosen? I also understand that I need to prove it's true for all values of r because if I do that it implies that it is true for k + 1.  Is it just to find a relation to F(r + 3) on line 3? If that was the case why not just have F(k + 3) = F(k + 2) + F(k + 1)?My final question about this is how did they get from line 4 to 5?The second equation I want to prove is:F(n + 6) = 4F(n + 3) + F(n) for n ≥ 1I'm able to prove n = 1 and n = 2 is true but I get stuck on going from what would be line 3 - 4 on this problem. As this is my problem for homework the answer is not in the back of the book.Now that I've gotten the help I just want to update this with the proof for my second equation (I haven't gotten the formatting down yet so bear with me):F(n + 6) = 4F(n + 3) + F(n)1) n = 1: F(7) = 4F(4) + F(1) or 13 = 12 + 1, true.2) n = 2: F(8) = 4F(5) + F(2) or 21 = 20 + 1, true.3) Assume for all r, 1 ≤ r ≤ k: F(r + 6) = 4F(r + 3) + F(r)4) Then F(k + 7) = 4F(k + 4) + F(k + 1) =5) F(k + 4) + F(k + 4) + F(k + 4) + F(k + 4) + F(k + 1) =6) F(k + 4) + F(k + 4) + F(k + 4) + F(k + 3) + F(k + 2)  F(k + 1) =7) F(k + 4) + F(k + 4) + F(k + 4) +F(k + 3) + F(k + 3) =8) F(k + 5) + F(k + 5) + F(k + 4) =9) F(k + 6) + F(k + 5) =10) F(k + 7)
 A: For each $n\geq 0$, let $S(n)$ denote the statement
$$
S(n) : F_n+2F_{n+1}=F_{n+3}.
$$
First note that $S(n)$ has a rather trivial direct proof:
$$
F_{n+3} = F_{n+1}+F_{n+2} = F_{n+1}+(F_n+F_{n+1})=F_n+2F_{n+1}.
$$
Thus, it is really not necessary to prove your statement by using induction, but let's do it anyway since we're on the topic.
Base step: $S(0)$ says $F_0+2F_1=F_3$, which is true since $F_0=0, F_1=1$, and $F_3=2$. 
Inductive step: For some fixed $k\geq 0$, assume that $S(k)$ is true. To be shown is that
$$
S(k+1) : F_{k+1}+2F_{k+2} = F_{k+4}
$$
follows from $S(k)$. Note that $S(k+1)$ can be proved without the inductive hypothesis; however, to formulate the proof as an inductive proof, following sequence of equalities uses the inductive hypothesis:
\begin{align}
F_{k+1}+2F_{k+2} &= F_{k+1}+2(F_k+F_{k+1})\\[0.5em]
                 &= (F_{k+1}+F_k)+(F_k+2F_{k+1})\\[0.5em]
                 &= F_{k+2}+(F_k+2F_{k+1})\\[0.5em]
                 &= F_{k+2}+F_{k+3}\qquad\text{by $S(k)$}\\[0.5em]
                 &= F_{k+4}.
\end{align}
This completes the inductive step $S(k)\to S(k+1)$. 
Thus, by mathematical induction, $S(n)$ is true for every $n\geq 0$. $\Box$
A: They assume that $f(k+3) = 2f(k+1) + f(k)$, then consider $f((k+1)+3) = f(k+4)$.
Setting aside our hypothesis for a moment, we know by definition that
$$f((k+1) + 3) = f(k+4) = f(k+3) + f(k+2) = f((k+1)+2) + f((k+1)+1)$$
Then, substituting what we know about $f(k+3)$:
$$f((k+1) + 3) = f((k+1) + 1) + 2f(k+1) + f(k)$$
$$=f((k+1)+1) + [f(k+1) + f(k)] + f(k+1)$$
$$= 2f((k+1)+1) + f(k+1) = 2f(k+2) + f(k+1)$$
A: The reason for having two initial cases is that the recurrence defining the Fibonacci numbers defines each of them in terms of the two preceding Fibonacci numbers. The proof by induction uses the defining recurrence $F(n)=F(n-1)+F(n-2)$, and you can’t apply it unless you know something about two consecutive Fibonacci numbers.
Note that induction is not necessary: the first result follows directly from the definition of the Fibonacci numbers. Specifically,
$$\begin{align*}
F(n+3)&=\color{brown}{F(n+2)}+F(n+1)\\
&=\color{brown}{F(n+1)+F(n)}+F(n+1)\\
&=2F(n+1)+F(n)\;.
\end{align*}$$
You can use the first result to prove the second; here again no induction is needed. Start with the righthand side:
$$\begin{align*}
4F(n+3)+F(n)&=3F(n+3)+\color{brown}{F(n+3)}+F(n)\\
&=3F(n+3)+\color{brown}{F(n+2)+F(n+1)}+F(n)\\
&=2F(n+3)+\color{blue}{F(n+3)+F(n+2)}+\color{green}{F(n+1)+F(n)}\\
&=2F(n+3)+\color{blue}{F(n+4)}+\color{green}{F(n+2)}\\
&=F(n+4)+F(n+3)+\color{brown}{F(n+3)+F(n+2)}\\
&=F(n+4)+F(n+3)+\color{brown}{F(n+4)}\\
&=2F(n+4)+F(n+3)\;.
\end{align*}$$
Now apply the first result, $F(m+3)=2F(m+1)+F(m)$, with $m=n+4$.
You can also do it by induction, and again you’ll need two base cases to get the induction started. If you want to try this approach, I suggest that you model your work on the induction argument that crash gives.
A: the following relation on the Fibonacci numbers is sometimes useful: (for $n \ge k \ge 0$):
$$
F(n+k) = \sum_{j=0}^k \binom{k}{j}F(n-j)
$$
this gives:
$$
F(n+6) = \sum_{j=0}^3 \binom{3}{j}F(n+3-j) \\
= F(n+3) +\color{blue}{3F(n+2)+3F(n+1)} +F(n) \\
=4 F(n+3)+F(n)
$$
