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

  • $\begingroup$ A generic hint for proving things about Fibonacci numbers by induction: formulate the conjecture in such a way that it involves all of them. As induction hypothesis assume that it holds for two previos values (the recurrence relation refers to both of them so this is natural). Observe that the base case needs to check it for two first values of the parameter. $\endgroup$ – Jyrki Lahtonen Oct 14 '14 at 4:44

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

  • $\begingroup$ well, that seems to make sense. But then, how do I prove P(n+1)? like F8(n+1) = 0? $\endgroup$ – user2847624 Oct 15 '14 at 3:45
  • $\begingroup$ @user2847624: In eight pieces. The first thing that you have to prove is that $F_{8(n+1)}\equiv0\pmod3$. Your induction hyp. tells you that $F_{8n+6}\equiv2\pmod3$ and $F_{8n+7}\equiv1\pmod3$, so $$F_{8(n+1)}=F_{8n+8}=F_{8n+6}+F_{8n+7}\equiv2+1\pmod3\;,$$ and hence $F_{8(n+1)}\equiv0\pmod3$, as desired. Now keep going in this fashion for $7$ more steps. $\endgroup$ – Brian M. Scott Oct 15 '14 at 3:47
