I am having trouble understanding this example from my book can you please explain further where the r-1 and r-k in the second picture comes from and if you can please explain the second to last step rig by before the (using recurrence relation again) I don't understand how we go from there to the conclusion. Thank you so much.

Prove that in the Fibonacci sequence F(n + 4) = 3F(n + 2) - F(n) for all n 21 Because we want to prove something true for all n = 1, it is natural to think of a proof by induction. And because the value of F(n) depends on both F(n - 1) and F(n - 2), the second principle of induction should be used. For the basis step of the inductive proof, we'll prove two cases, n 1 and n 2. For n = 1, by sub- stituting 1 for n in the equation we want to prove, we get F(5) = 3F(3) - F(1) - or (using values computed in Practice 2) 5 = 3(2) - 1 which is true. For n = 2, F(6) = 3F(4) - F(2) 01 8 = 3(3) - 1 which is also true. Assume that for allr, 1 Srsk, F(r + 4) = 3F(r + 2) - F(-). Now show the case for k + 1, where k +1 23. (We've already proved the case for n = 1 and the case se for n = 2.) Thus we want to show F(k + 1 + 4) 3F(k + 1 + 2) - F(k + 1) or F(k + 5) ? 3F(k + 3) - F(k + 1) From the recurrence relation for the Fibonacci sequence, we have F(k + 5) = F(k + 3) + F(k + 4) (F at any value is the sum of Fat the two previous values) and by the inductive hypothesis, with r = k - 1 and r = k, respectively, F(k + 3) = 3F(k + 1) - F(k 1) and F(k + 4) = 3F(k + 2) - F(1) Therefore F(k + 5) = F(k + 3) + F(k + 4) = [3F(k + 1) - F(k 1)] + [3F(k + 2) F(l)] = 3[F(k + 1) + F(k + 2)] - [F(k 1) + F(10)] = 3F(k + 3) - F(k + 1) (using the recurrence relation again) . This completes the inductive proof