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)

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)$$
