Given that F(0),F(1),F(2),… represents the Fibonacci sequence, prove that F(k) =3F(k−3)+2F(k−4) , for every integer k⩾4 (k greater than or equal to 4).
*Everything in parenthesis that is also italicized is a subscript.
Now,
I thought you could start with the standard Fibonacci sequence and maybe multiply that by 4, since it's normally k greater than or equal to 1, and then try to show that it's equal to the statement above. I'm not sure if that's correct though, or where else to start if not. The only other idea was to try proof by induction and show that it works for 4 (rather than 1) and then show it for n and n+1.
Thanks in advance
Best Answer
Proof by induction is kind of overkill here, although I think it could work! Try it as a good exercise. For a simpler solution, by definition, $F_k = F_{k - 1} + F_{k - 2}$. We can apply this recursive definition to $F_{k - 1}$ to get $F_{k - 1} = F_{k - 2} + F_{k - 3}$, and to $F_{k - 2}$ to get $F_{k - 2} = F_{k - 3} + F_{k - 4}$. If you substitute those last two equalities into $F_k = F_{k - 1} + F_{k - 2}$, the proof will be complete. In particular, \begin{align*}F_{k} &= F_{k - 1} + F_{k - 2} \\ &= F_{k - 2} + F_{k - 3} + F_{k - 3} + F_{k - 4} \\ &= F_{k - 3} + F_{k - 4} + 2F_{k - 3} + F_{k - 4} \\ &= 3F_{k - 3} + 2F_{k - 2} \end{align*}
As desired.