0
$\begingroup$

This is the question: The Fibonacci numbers are recursively dened by $f_1 = f_2 = 1$, and $f_n = f_{n-1} + f_{n-2}$ for $n > 1$. Prove that every fourth Fibonacci number is a multiple of $3$.

I've been stuck on this question for a while. If someone could help me out or at least help me start it, that would be great

$\endgroup$
2
0
$\begingroup$

You can then show that $$ f_{4(n+1)} = 2 f_{4n} + 3 f_{n+1} $$ by just repeatedly plugging in the formula. As Daniel suggests, use this along with induction, and you should hopefully be able to get the result! :)

Originally I was just going to write "start with $f_{4(n+1)}$ and repeatedly plug in the formula". Since seeing this answer to the same question elsewhere, I added the right-hand side. Wasn't really anything, but felt I should credit it all the same!

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.