prove by induction that $(a^n - b^n)$ is a multiple of $(a - b)$ for $n \geq 1$

Question

Okay so I just finished a final in discrete mathematics and I could not figure out how to finish this proof:

"Prove by mathematical induction, that $(a^n - b^n)$ is a multiple of $(a - b)$ when $a$ and $b$ are integers and $n \geq 1$.

$\underline{Base case: n = 1}$

$(a^1 - b^1) = (a - b)x$

$x = 1$

$a - b = a - b$

$\underline{Inductive Hypothesis:}$

$n = k$ for some $k$

$(a^k - b^k) = (a - b)x$

$\underline{Inductive Step:}$

$n = k + 1$

$(a^{k + 1} - b^{k + 1}) = (a - b)x_1$

$(a \cdot a^{k}) - (b \cdot b^{k}) = (a - b) x_1$

$a \cdot [(a - b)x + b^k] + b \cdot [(a - b)x - a^k]= (a-b)x_1$

$(a -b)xa + ab^k + (a - b)xb - ba^k = (a - b)x_1$

$(a -b)xa + (a - b)xb - ab^k + ba^k = (a - b)x_1$

$(a -b)xa + (a - b)xb + ba^k - ab^k = (a - b)x_1$

.....

I don't know if I did it right but I couldn't get any further than this.

Answer 1

Assumed $a^k-b^k=(a-b)m,m\in\Bbb Z\implies a^k=b^k+(a-b)m$

We have $a^{k+1}-b^{k+1}=a\times a^k-b^{k+1}=a[b^k+(a-b)m]-b^{k+1}\\=am(a-b)+ab^k-b^{k+1}\\=am(a-b)+b^k(a-b)\\=(am+b^k)(a-b)$

Answer 2

$$ a^n-b^n=(a-b)\sum_{m=0}^{n-1}a^m\cdot b^{n-1-m}$$

Answer 3

Firstly we prove the statement for $n=0,1$ (or $n=1,2$ if you prefer, but the statement is true for $n\geq0$).

Case $n=0$ : $a^0-b^0 = 0 = 0*(a-b)$

Case $n=1$ : $a^1-b^1 = 1*(a-b)$

Now we prove the induction case. Suppose the statement is true for $k\leq n$, and let's prove it for $n+1$: $$ (a^{n+1}-b^{n+1})=(a^n-b^n)(a+b) - a^nb + b^na = (a^n-b^n)(a+b)- ab(a^{n-1} - b^{n-1}) $$

Since both $(a^n-b^n)$ and $(a^{n-1} - b^{n-1})$ are divisible by $(a-b)$ by induction, so is $(a^{n+1}-b^{n+1})$ since it is a sum of their multiples.

Answer 4

Can you do one step of a long division?

$$ \frac{a^{k+1}-b^{k+1}}{a-b} = a^k + b\frac{(a^k-b^k)}{a-b} $$

with the remainder being a polynomial in $a$ and $b$ by induction hypothesis.

Answer 5

1)$n=1 : a-b ✓$

Hypothesis: $a^n-b^n$ is a multiple of $(a-b)$.

Step $n+1$:

$a^{n+1}-b^{n+1} =a a^n -b b^n= $

$aa^n-ba^n+ba^n -bb^n=$

$(a-b)a^n +b(a^n -b^n)=$

$(a-b)a^n +bk(a-b)=$

$ (a-b)(a^n +bk).$

(Since by hypothesis: $a^n-b^n =k(a-b)$).