9
$\begingroup$

Prove by Induction that for all $n \geq 1$ we have

$$8^n - 3^n \text{is divisible by 5} ...(*)$$

My proof so far

Step 1: For $n=1$ we have $8^1 - 3^1 = 8 - 3 = 5$ which is divisible by 5.

Step 2: Suppose (*) is true for some $n=k\geq 1$ that is $8^k-3^k$ is divisible by 5.

Step 3: Prove that (*) is true for $n=k+1$, that is $8^{k+1} - 3^{k+1}$ is divisible by 5. We have

$$8^{k+1}-3^{k+1} = 8*8^k - 3*3^k$$

Can anyone explain the next logical expansion?

Update:

$$8^{k+1}-3^{k+1} = 8*8^k - 3*3^k = 5*8^k + 3*8^k - 3*3^k = 5*8^k + 3(8^k - 3^k)$$

Now we can say that $5*8^k$ is divisible by 5 since it has the form $5*p$ where $p$ is an integer $\geq 1$

And it is assumed that $8^k-3^k$ is divisible by $5$, then $3(8^k-3^k)$ is divisible by $5$ which means it has the form $5p$

so we reduce the expression to $$5p+5p = 5(p+p)$$

which is of the form $5p$, which is divisible by $5$.

Is my proof correct?

$\endgroup$
  • 2
    $\begingroup$ $8\cdot 8^k=5\cdot 8^k+3\cdot 8^k$. And now it's over. $\endgroup$ – André Nicolas Sep 6 '15 at 1:11
  • $\begingroup$ Or without induction: $8^n-3^n=(8-3)\left(8^{n-1}+8^{n-2}\cdot 3+\cdots+8\cdot 3^{n-2}+3^{n-1}\right)$ $\endgroup$ – user236182 Sep 6 '15 at 1:12
  • $\begingroup$ One quibble with your updated proof. If $5 \cdot 8^k = 5p$ for some $p \in \mathbb{N}$, then $3(8^k - 3^k) = 5r$ for some $r \in \mathbb{N}$. We cannot assume that $p = r$, as you seem to be. $\endgroup$ – N. F. Taussig Sep 6 '15 at 10:28
7
$\begingroup$

There is, more or less, somewhat of a "standard" way of writing out these divisibility proofs involving induction. Given your recent questions on induction, I really would encourage you to take a look at this post on how to write a clear induction proof--I think it would force you to construct clear proofs and it would also force you to know what you are doing and why at each step. That said, see if the following proof makes sense (I am going to write it using the template provided in the linked post above):


For all $n\geq 1, 8^n-3^n$ is divisible by $5$; that is, $5\mid(8^n-3^n)$, and this notation simply means that "$5$ divides $8^n-3^n$."

Proof. For $n\geq 1$, let $S(n)$ denote the statement $$ S(n):5\mid(8^n-3^n)\iff 8^n-3^n=5m, m\in\mathbb{Z}. $$ Base case ($n=1$): $S(1)$ says that $5\mid (8^1-3^1)$, and this is true (all it is saying is that $5$ divides $5$, and that is clearly true).

Inductive step: Fix some $k\geq1$ and assume that $$ S(k):5\mid(8^k-3^k)\iff 8^k-3^k=5\ell, \ell\in\mathbb{Z} $$ is true. To be shown is that $S(k+1)$ follows where $$ S(k+1):5\mid(8^{k+1}-3^{k+1})\iff 8^{k+1}-3^{k+1}=5\eta, \eta\in\mathbb{Z}. $$ Beginning with the left-hand side of $S(k+1)$, \begin{align} 8^{k+1}-3^{k+1}&= 8(8^k)-3(3^k)\tag{law of exponents}\\[0.5em] &= (8^k-3^k)8+5(3^k)\tag{manipulate}\\[0.5em] &= (5\ell)8+5(3^k)\tag{by $S(k)$, the ind. hyp.}\\[0.5em] &= 5(8\ell+3^k)\tag{factor out the $5$}\\[0.5em] &= 5\eta\tag{$\eta=8\ell+3^k, \eta\in\mathbb{Z}$} \end{align} we end up at the right-hand side of $S(k+1)$, completing the inductive step.

By mathematical induction, the proposition $S(n)$ is true for all $n\geq1$. $\blacksquare$


Does all of that make sense? Near the end of your own proof, you write that $5(p+p)$ is of the form $5p$ which is not actually true. The key is to realize how to generalize as above where you can use any number of symbols so long as you do it effectively. Feel free to comment if a step remains unclear.

$\endgroup$
  • $\begingroup$ Excelent, +1 for the detailed steps. I appreciate it because it helps people that is learning, like me $\endgroup$ – JorgeeFG Oct 3 '15 at 2:57
6
$\begingroup$

Continue like this:

$8 \cdot 8^k - 3 \cdot 3^k = (5+3) \cdot 8^k - 3 \cdot 3^k = 5 \cdot 8^k + 3 \cdot (8^k - 3^k)$

$\endgroup$
  • $\begingroup$ Thank you for that awesome hint. I have updated my proof to reflect this. Am I on the right track? $\endgroup$ – lucidgold Sep 6 '15 at 1:24
1
$\begingroup$

Hint: note that $8=5+3$ and then factor.

$\endgroup$
1
$\begingroup$

By the binomial theorem, $8^n=(5+3)^n=5a+3^n$.

Induction is used to prove the binomial theorem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.