6
$\begingroup$

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.

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

5 Answers 5

22
$\begingroup$

enter image description here

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

$\endgroup$
1
  • $\begingroup$ Very nice indeed! $\endgroup$ Oct 17, 2013 at 0:02
16
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ And don't forget to include verification of the base case in your proof: $n = 0$ or $n = 1$. $\endgroup$
    – amWhy
    Oct 16, 2013 at 17:10
  • $\begingroup$ 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! $\endgroup$
    – krb686
    Oct 16, 2013 at 17:11
  • $\begingroup$ @amWhy: Nice to get a nice answer +1 $\endgroup$
    – Amzoti
    Oct 18, 2013 at 0:57
7
$\begingroup$

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

$\endgroup$
0
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ My test asked to use induction so that's why I narrowed that down, but thank you for all the in depth info! $\endgroup$
    – krb686
    Oct 17, 2013 at 3:49
  • $\begingroup$ @krb686: You’re welcome! $\endgroup$ Oct 17, 2013 at 3:50
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .