How can I prove by induction that $9^k - 5^k$ is divisible by 4?

${\color{White}{\text{Proof without words.}}}$

$$\begin{align} 9\cdot 9^k - 5\cdot 5^k & = (4 + 5)\cdot 9^k - 5\cdot 5^k \\ \\ & = 4\cdot 9^k + 5 \cdot 9^k - 5\cdot 5^k \\ \\ & = 4\cdot 9^k + 5(9^k - 5^k)\\ \\ & \quad \text{ use inductive hypothesis}\quad\cdots\end{align}$$

$9^{k+1}-5^{k+1}=(8+1)9^k-(4+1)5^k=9^k-5^k+4(2\cdot 9^k-5^k)$ The secret to induction proofs is usually to find a way to relate the $k+1$ case to the $k$ case.

Alternately, just note $9\equiv 1 \pmod 4, 5 \equiv 1 \pmod 4$, so $9^k-5^k \equiv 1^k-1^k \pmod 4$