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.
 A: $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$
A: 
${\color{White}{\text{Proof without words.}}}$
A: Note that induction is not actually needed: you can instead use the identity
$$x^n-y^n=(x-y)\sum_{k=0}^{n-1}x^ky^{n-1-k}\;.$$
In this case it becomes
$$9^n-5^n=4\sum_{k=0}^{n-1}x^ky^{n-1-k}\;,$$
and since the summation clearly yields an integer, we have $4\mid 9^n-5^n$. The identity is a standard one, but it’s also not hard to prove:
$$\begin{align*}
(x-y)\sum_{k=0}^{n-1}x^ky^{n-1-k}&=x\sum_{k=0}^{n-1}x^ky^{n-1-k}-y\sum_{k=0}^{n-1}x^ky^{n-1-k}\\\\
&=\sum_{k=0}^{n-1}x^{k+1}y^{n-1-k}-\sum_{k=0}^{n-1}x^ky^{n-k}\\\\
&=\sum_{k=1}^nx^ky^{n-k}-\sum_{k=0}^{n-1}x^ky^{n-k}\\\\
&=x^ny^0+\sum_{k=1}^{n-1}x^ky^{n-k}-\sum_{k=1}^{n-1}x^ky^{n-k}-x^0y^n\\\\
&=x^n-y^n\;.
\end{align*}$$
A: $$\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}$$
A: It sounds like you understand the basic idea, but you're having trouble with the "trick" in the inductive step.  This is common for proofs by mathematical induction, and you'll get better at it with more experience.
As you said, you're assuming that
$
9^k-5^k
$
is divisible by four, and you want to prove that
$
9^{k+1}-5^{k+1}
$
is divisible by four.  You noticed that you can write the last expression as
$9\cdot 9^k-5\cdot 5^k$, and you said you're having trouble applying your assumption to it.  What happens if you add $9\cdot 5^k-9\cdot 5^k$ to your expression?  This is just zero, so you're not changing anything, but you can write
$$
9^{k+1}-5^{k+1}
=9\cdot 9^k-5\cdot 5^k+9\cdot 5^k-9\cdot 5^k
=9\cdot (9^k-5^k)+(9-5)\cdot 5^k.
$$
By the assumption, the first term, $9\cdot (9^k-5^k)$, is divisible by four, and by observation, the second term, $(9-5)\cdot 5^k$, is divisible by four, so the sum of the two terms and therefore $9^{k+1}-5^{k+1}$ are divisible by four.  This is what you wanted to show.
You can always add zero (or multiply by one), and by writing zero (or one) in a particular way, you can sometimes make an argument easier to prove.  Also, since your proof is by mathematical induction, you need to show that $9^n-5^n$ is divisible by four for, say, $n=0$ or $n=1$.  You may have already done so and not asked about it in your question, but it's worth mentioning.
