# The Fibonacci numbers are recursively defined by $f_1 = f_2 = 1$, and $f_n = f_{n-1} + f_{n-2}$ [duplicate]

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

• Hint: Try proceeding by induction. – Daniel Robert-Nicoud Nov 2 '17 at 22:01
• – Sam OT Nov 2 '17 at 22:06

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!