Answer to Question #95392 in Algebra for Randy

Question

Proof by induction
n³–n is divisible by 3 for all natural numbers n.

Answer 1

Let P(n) be the mathematical statement n³-n is divisible by 3.

Base Case: When n = 0 we have 0³-0 = 0 = 3 × 0. So P(0) is correct.

Induction hypothesis: Assume that P(k) is correct for some natural number k. That means k³ -k is divisible by 3 and hence that k³-k = 3m for some integer m.

Induction step: We will now show that P(k + 1) is correct. So we will take the original formula and replace the n with (k+1) to get (k+1)³-(k+1) and we will show that this is divisible by 3. At some stage in the proof we will need to use the fact that k³-k = 3m, so when we re-arrange the

formula we will try to get k³-k as part of it.

(k+1)³-(k+1) = k³+3k²+3k+1-k-1 by expanding the brackets

(k+1)³-(k+1) = k³-k+3k²+3k by re-arranging the formula

(k+1)³-(k+1) = 3m+3(k²+k) by the induction hypothesis

(k+1)³-(k+1) = 3(m+k²+k) since both parts of the formula have a common factor of 3.

As m+k²+k is an integer we have that (k + 1)³-(k + 1) is divisible by 3, so P(k + 1) is

correct. Thus, by the principle of mathematical induction, P(n) is correct for all natural numbers n.