# 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.

• hint: 9 = (5+4) and distribute. – imranfat Oct 16 '13 at 16:56
• Alternatively you can note that $a^n-b^n=(a-b)\sum _{i=0} ^{n-1} a^i b^{n-1-i}$. – pppqqq Oct 16 '13 at 16:58

\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}

• And don't forget to include verification of the base case in your proof: $n = 0$ or $n = 1$. – Namaste Oct 16 '13 at 17:10
• Okay this seems to make the most sense and is closest to how my prof. teaches it. Dam I really hate theoretical math and proofs! – krb686 Oct 16 '13 at 17:11
• @amWhy: Nice to get a nice answer +1 – Amzoti Oct 18 '13 at 0:57 ${\color{White}{\text{Proof without words.}}}$

• Very nice indeed! – Brian M. Scott Oct 17 '13 at 0:02

$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$

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*}

• My test asked to use induction so that's why I narrowed that down, but thank you for all the in depth info! – krb686 Oct 17 '13 at 3:49
• @krb686: You’re welcome! – Brian M. Scott Oct 17 '13 at 3:50

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.