Prove every 4th Fibonacci number is divisible by 3 using mathematical Induction?

Question

Can anyone confirm whether my answer is correct, please.

Let's suppose we have the following fibonacci numbers as shown: $f(0) = 0, f(1) = 1$, and $f(n) = f(n-1) + f(n-2)$ for $n \geq 2$. Prove that for each $n \geq 0, f(4n)$ is a multiple of $3$

$f_0 = 0,f_1= 1,f_n = f_{n-1}+f_{n-2} \text{ for } n \geq 2$ Prove that for each $n \geq 0, f_{4n}$ is a multiple of $3$.

My solution to this question:

\begin{align} f_{4(k+1)} & = f_{4k+4} \\ & = f_{4k+3} + f_{4k+2} \\ & = f_{4k+3} + (f_{4k+1} + f_{4k}) \\ & = (f_{4k+2} + f_{4k+1}) + (f_{4k+1} + f_{4k}) \\ & = f_{4k+1} + f_{4k} + f_{4k+1} + f_{4k+1} + f_{4k} \\ & = 3(f_{4k+1}) + 2(f_{4k}) \end{align}

Answer 1

Calculating $f(n)$ mod $3$ up to $n = 9$ gives

$n$	0	1	2	3	4	5	6	7	8	9
$f(n)$ mod $3$	0	1	1	2	0	2	2	1	0	1

This shows

1. $f(0) \equiv f(4) \equiv 0$ mod $3$
2. $f(n+8) \equiv f(n)$ mod $3$
3. $f(4n) \equiv 0$ mod $3$

Answer 2

What you need to prove is that $f_{4(n + 1)}$ is divisible by 3 (or that it has a factor of 3 in it) for all $n \in \mathbb{N}$. You have to prove that the proposition holds for your base case: $f_4$ which it surely does. Now you assume $f_{4n}$ holds and prove that $f_{4(n + 1)}$ also holds.

To do this, define $f_{4n} = 3m, \hspace{2mm} m \in \mathbb{N}$, (definition of multiple of 3).

Now, we have to construct $f_{4(n + 1)}$, Fibonacci numbers are defined by their predecesors in the form:

$$ f_n = f_{n - 1} + f_{n - 2}$$

We also define $f_{4n - 1} = k, \hspace{2mm} k \in \mathbb{N}$ (this just tells us that it is a natural number, as $F \subset \mathbb{N}$).

We can now procede to construct $f_{4(n + 1)}$ as follows:

$$ f_{4n + 1} = f_{4n} + f_{4n - 1} = 3m + k $$

$$ f_{4n + 2} = f_{4n + 1} + f_{4n} = (3m + k) + (3m) = (6m + k)$$

$$ f_{4n + 3} = f_{4n + 2} + f_{4n + 1} = (6m + k) + (3m + k) = (9m + 2k)$$

$$ f_{4n + 4} = f_{4n + 3} + f_{4n + 2} = (9m + 2k) + (6m + k) = (15m + 3k)$$

Now, we can factor out 3 in the last step:

$$ f_{4n + 4} = 3(5m + k)$$

but $ f_{4n + 4} = f_{4(n + 1)} $, we showed that if the proposition for $f_{4n}$ holds, it also holds for $ f_{4(n + 1)}$