proving Fibonacci numbers using mathematical Induction? Can anyone confirm whether my answer is correct, please.
Let 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}
 A: 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)}$
