5
$\begingroup$

Statement: $\frac{8^k-3^k}{5}=M, M\in\mathbb{N}$

Base case: $P(1): \frac{8-3}{5}=1\in\mathbb{N}$

Assume $P(n): \frac{8^n-3^n}{5}=N$

Then, $P(n+1)=8^{n+1}-3^{n+1}=5K$, where $K$ is in terms of $M$

Writing LHS in terms of $N$:

$8^n-3^n=5N \to 8\cdot8^n-8*3^n=40N$

$8^{n+1}-3^{n+1}=40M+5\cdot3^{n+1}$

Dividing through by $5$:

$\frac{8^{n+1}-3^{n+1}}{5}=8M+3^{n+1}=K$ , where $K$ is clearly an integer, as $M$ and $N$ Are defined to be integers.

———————————————————————————————

Questions:

  1. Is this proof valid?
  2. Adding to that, is that last deduction of $K\in\mathbb{N}$ fair?
$\endgroup$
  • 2
    $\begingroup$ $8^n-3^n=(5+3)^n-3^n=\sum_{i=1}^{n} \binom{n}{i}5^{i}3^{n-i}=5\cdot\sum_{i=1}^{n} \binom{n}{i}5^{i-1}3^{n-i}$ $\endgroup$ – Sil Apr 7 at 12:13
1
$\begingroup$

Yes, your proof is correct. Below I explain how to view the arithmetical essence of the matter more conceptually as the result of a product rule, first using congruences, and later using bare divisibility (in case you don't know congruences).

Conceptually the induction follows very simply by multiplying the first two congruences below using CPR = Congruence Product Rule, $ $

$$\begin{align}\bmod 5\!:\qquad \color{#c00}{8}\ &\equiv\ \color{#c00}{3}\\ 8^{\large n}&\equiv 3^{\large n}\quad\ \ \ P(n)\\ \Rightarrow\ \ \color{#c00}{8}\,8^{\large n}&\equiv 3^{\large n}\color{#c00}{3}\quad\ P(n\!+\!1),\ \ \rm by \ CPR\end{align}\qquad $$

i.e. the proof is a special case of the (inductive) proof of the Congruence Power Rule.. Note how the use of congruences highlights innate arithmetical structure allowing us to reduce the induction to an easy one $\,a\equiv b\,\Rightarrow\, a^n\equiv b^n,\,$ with obvious inductive step: multiply by $\,a\equiv b\,$ via the product rule.

If you don't know congruences we can preserve this arithmetical essence by using an analogous product rule for divisibility (DPR), $ $ where $\ m\mid n\ $ means $\,m\,$ divides $\,n,\,$ namely

$$\quad\, \begin {align} &5\mid\ \color{#c00}{8\,\ \ -\ 3}\\ &5\mid\ \ \ 8^{\large n} -\ 3^{\large n}\quad\ P(n)\\ \Rightarrow\ \ &5\mid\ \color{#c00}{8}8^{n}\! -\!\color{#c00}33^{\large n}\quad\ \ P(n\!+\!1),\ \ \rm by\ DPR \end{align} $$

$\begin{align}{\bf Divisibility\ Product\ Rule}\ \ \ \ &m\mid\ a\ -\ b\qquad {\rm i.e.}\quad \ a\,\equiv\, b\\ &m\mid \ \ A\: -\: B\qquad\qquad \ A\,\equiv\, B\\ \Rightarrow\ \ &\color{}{m\mid aA - bB}\quad \Rightarrow\quad aA\equiv bB\!\pmod{\!m}\\[.2em] {\bf Proof}\,\ \ m\mid (\color{#0a0}{a\!-\!b})A + b(\color{#0a0}{A\!-\!B}) &\,=\, aA-bB\ \ \text{by $\,m\,$ divides $\rm\color{#0a0}{green}$ terms by hypothesis.}\end{align}$

Remark $ $ The proof in Jose's answer is nothing but a (numerical) special case of the prior proof - see here where I explain that at length. Further discussion on related topics is in many prior posts.

$\endgroup$
3
$\begingroup$

Your proof is correct. I suggest that you use $\implies$ instead of $\rightarrow$ in your proofs. Besides, it would have beeen simpler if you had written\begin{align}8^{n+1}-3^{n+1}&=8\times8^n-8\times3^n+8\times3^n-3^{n+1}\\&=8\times(8^n-3^n)+5\times3^n.\end{align}

$\endgroup$
  • $\begingroup$ The (unmotivated) proof above is a special case of the proof of the Congruence (or Divisibility) Product Rule, and the proof is much more simple and natural when presented that way, as I explain in my answer. $\endgroup$ – Bill Dubuque Apr 7 at 13:25
0
$\begingroup$

Hint: Use that if $$8\equiv 3\mod 5$$ then $$8^n\equiv 3^n\mod 5$$

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