Prove by induction that (n^3)-n is divisible by 3 for all integers n>0 (typical fp1 problem)

Let P(n) be the statement “(n^3)-n is divisible by 3”

First we’ll examine the base case: P(1)

(n^3)-n=1^3-1=1-1=0

0=3*0, so is divisible by 3, and so P(1) is true

Now assume for some k>0, an integer, that P(k) holds true, i.e. there exists an integer a such that (k^3)-k = 3a.

We want to show that this implies that P(k+1) is true:

(k+1)^3-(k+1)

=k^3+3k^2+3k+1-k-1      (This is just a binomial expansion)

=k^3-k +3k^2+3k            (The 1’s cancel. Since we want to use our assumption we put k^3-k together)

=3a+3k^2+3k                 (Using the inductive hypothesis)

=3b                                 (b is clearly an integer so we’re done)

Now since we’ve shown that P(n) holds for n=1 and that P(k) implies P(k+1), then by mathematical induction it follows that P(n) is true for all integers n>0. q.e.d.