College Algebra, Chapter 9, Review Exercises, Section Review Exercises, Problem 70

Prove that Fibonacci number $F_{4n}$ is divisible by $3$ for all natural numbers $n$
Step 1: $P(1)$ is true, since $F_{4(1)} = F_4 = 3$ is divisible by $3$
Step 2: Suppose $P(k)$ is true. Now by definition of the Fibonacci sequence

$
\begin{equation}
\begin{aligned}
F_{4(k+1)} &= F_{4k + 4} = F_{4k + 3} + F_{4k+1}\\
\\
&= F_{4k + 2} + F_{4k + 1} + F_{4k + 1}\\
\\
&= F_{4k} + F_{4k + 1} + F_{4k + 1} + F_{4k + 1}\\
\\
&= F_{4k} + 3 \cdot F_{4k + 1}
\end{aligned}
\end{equation}
$

By the induction hypothesis, $F_{4k}$ is divisible by 3 and $3$. $F_{4k +1}$ is clearly divisible by $3$ since the statement is a multiple of $3$.
So, $P(k+1)$ follows from $P(k)$. Thus, by the principle of mathematical induction, $P(n)$ holds for all $n$.