Chapter 12, Problem 72RE

To determine

To prove that the Fibonacci number $F_{4n}$ is divisible by 3 for all natural numbers $n$ .

Explanation of Solution

Given:

The Fibonacci number $F_{4n}$ , where $n$ is a natural number.

Proof:

Proof by Mathematical induction:

For $F_{4n}=F_{4\cdot 1}=F_4=3$ . That is, $F_{4n}$ is divisible by 3 for $n=1$ .

Let the proposition is true for $n=k$ . So, there exist a number $m$ such that $F_{4k}=3m$ .

Assume, $F_{4n-1}=p$ .

Then,

  $\begin{array}{l}{F}_{4k+1}=F_{4k}+F_{4k-1}=3m+p\\ F_{4k+2}=F_{4k+1}+F_{4k}=\left(3m+p\right)+3m=6m+p\\ F_{4k+3}=F_{4k+2}+F_{4k+1}=\left(6m+p\right)+\left(3m+p\right)=9m+2p\\ F_{4k+4}=F_{4k+3}+F_{4k+2}=\left(9m+2p\right)+\left(6m+p\right)=15m+3p\end{array}$

That is, $F_{4\left(k+1\right)}=3\left(5m+p\right)$ is divisible by 3.

This shows that the given proposition is true for $n=k+1$ if it is true for $n=k$ .

Thus, by the principle of the mathematical induction $F_{4n}$ is divisible by 3 for all-natural numbers.