Show that it is true for n = 1
(1)^3 - 1 = 0 and this is divisible by 3
Assume that it is true for n = k
That is k^3 - k is divisible by 3
Note that we can write this as k (k^2 - 1) = k (k + 1) (k - 1) = (k - 1)(k)(k + 1)
Prove that it is true for k + 1
(k + 1)^3 - (k + 1) factor
(k + 1) [ (k + 1)^2 - 1]
( k + 1) ( k^2 + 2k + 1 - 1 ]
(k + 1) [ k^2 + 2k ]
(k + 1) [ k ( k + 2) ] =
k (k + 1) (k + 2) =
k(k + 1) ( k + 3 - 1) =
k(k + 1) ( k - 1 + 3) =
k(k + 1) (k - 1) + 3k(k+1)
(k-1) (k) (k + 1) + 3k(k + 1)
And we assumed that the first term was divisible by 3
And the second term is a multiple of 3, so it is also divisible by 3
So.... (k + 1)^3 - (k + 1) is divisible by 3
