TSSFL TECHNOLOGY STACK

Posted: **Fri Jan 15, 2016 11:51 am**

Problem

Prove by induction on $n$ that $3$ always divides $n^3 - n$ .

Proof

$3$ divides $n^3 - n$ $\implies$ $\frac{n^3 - n}{3} = m, \implies n^3-n = 3m, \ m\in \mathbb{Z}$ .

Thus,

For $n = 1,$ $n^3 - n = 1^3 - 1 = 0 = 3(0),$ and hence the result is true for $n = 1$

For $n = 2,$ $n^3-n = 2^3 - 2 = 8-2 = 6 = 3(2)$ , the result is also true for $n = 2$

Assume the result holds for $n = k,$ so $k^3 - k = 3r, \ r\in \mathbb{Z},$ we prove for $n = k+1$ .

Now,
$(k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1 \\ \\ = (k^3 - k) + 3k^2 + 3k \\ \\ = (k^3-k) + 3(k^2 + k) \\ \\ = 3r + 3(k^2 + k) \\ \\ = 3(r+k^2 +k) = 3j, \ j\in \mathbb{Z}$ .

We conclude that the results are valid for all natural numbers $n$ .

TSSFL TECHNOLOGY STACK

Algebra - Proof by Mathematical Induction

Algebra - Proof by Mathematical Induction