Q:

Prove that for each Fibonacci number $f_{4n}$ is a multiple of $3$.

The Fibonacci numbers are defined as follows: $f_0 = 0$, $f_1 = 1$, and $f_n =
f_{n-1} + f_{n-2}$ for $n \ge 2$. Prove that for each $n \ge 0$, $f_{4n}$ is a multiple of $3$. 
I've tried to prove to by induction. So, my basis is $f(0)$, which is true. Then, i assume that it's true for some integer $k$, and I am stuck at this point, can't really get what to do

A:

The question is indeed covered by the material at the link in the comments, but that’s overkill and perhaps not most conducive to learning how to attack such a problem at an elementary level. Start by examining the first few Fibonacci numbers modulo $3$;
$$\begin{array}{rccc}
n:&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\
F_n:&0&1&1&2&3&5&8&13&21&34&55&89&144&233&377&610&987\\
F_n\bmod 3:&0&1&1&2&0&2&2&1&0&1&1&2&0&2&2&1&0
\end{array}$$
These numbers suggest the possibility that the sequence $\langle F_n\bmod 3:n\in\Bbb N\rangle$ is periodic with period $8$, repeating the block $\langle 0,1,1,2,0,2,2,1\rangle$ indefinitely. This would mean that
$$F_n\bmod 3\equiv\begin{cases}
0,&\text{if }n\equiv 0\pmod 8\\
1,&\text{if }n\equiv 1\pmod 8\\
1,&\text{if }n\equiv 2\pmod 8\\
2,&\text{if }n\equiv 3\pmod 8\\
0,&\text{if }n\equiv 4\pmod 8\\
2,&\text{if }n\equiv 5\pmod 8\\
2,&\text{if }n\equiv 6\pmod 8\\
1,&\text{if }n\equiv 7\pmod 8\;.
\end{cases}\tag{1}$$
This is quite straightforward to prove by induction. Let $P(n)$ be the following statement:
$$\begin{align*}
&F_{8n}\equiv0\pmod3,F_{8n+1}\equiv1\pmod3,\\
&F_{8n+2}\equiv1\pmod3,F_{8n+3}\equiv2\pmod3,\\
&F_{8n+4}\equiv0\pmod3,F_{8n+5}\equiv2\pmod3,\text{ and}\\
&F_{8n+6}\equiv2\pmod3,F_{8n+7}\equiv1\pmod3\;.
\end{align*}$$
We saw in the table above that $P(0)$ is true. The induction step is to assume $P(n)$ and prove $P(n+1)$.
Note that this is an example of a phenomenon that is actually quite common: it’s actually easier (or at least more straightforward) to prove the stronger statement that $(1)$ is true for all $n\in\Bbb N$ than to prove directly that each $F_{4n}$ is divisible by $3$.

