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)

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$
