Prove by Induction: $8^n - 3^n$ is divisible by $5$ for all $n \geq 1$

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.


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

Tags:

Induction