Given the recursive nature of Fibonacci numbers, a proof by induction seems to be the logical way to go. Have you considered that?
The Fibonacci numbers are defined by , and
Prove if , then
This is one of those times where it's easy to see intuitively, it's hard to see formally.
Considering the Fibonacci sequence
It falls into a pattern of
From, as the first term is even, it's clear to see that every third term beginning from is divisible by 3, as it is the sum of the 2 previous numbers which are odd.
But this just scaffolding, scrap work.
Any tips on how to codify this formally?