<s>[INST] How can I prove by induction that $9^k - 5^k$ is divisible by 4? Recently had this on a discrete math test, which sadly I think I failed.  But the question asked:

Prove that $9^k - 5^k$ is divisible by $4$.

Using the only approach I learned in the class, I substituted $n = k$, and tried to prove for $k+1$ like this:
$$9^{k+1} - 5^{k+1},$$
which just factors to $9 \cdot 9^k - 5 \cdot 5^k$.
But I cannot factor out $9^k - 5^k$, so I'm totally stuck.
 [/INST] $$\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}$$
</s>