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

Question

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

Answer 1

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$.