1. ## mathematical induction

Prove that n^3-n is divisible by 3

Prove that n^3-n is divisible by 3
$n^3 - n = 3a$ for some $a$.

First we see if it holds for $n=0$

$0^3 - 0 = 0$, therefore true for $n=0$

Now we use what's called the induction step, we assume that it's true for $n=k$ where k is some natural nubmer.

This gives us $k^3 - k = 3a$

We then prove this for $n=k+1$, giving us

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

Expanding the brackets gives $k^3 + 3k^2 + 3k + 1 - k - 1$

$k^3 + 3k^2 + 2k$ which can be written as $k^3 + 3k^2 + 3k - k$

$(k^3-k) + 3(k^2 + k) = 3a + 3(k^2 + k)$.

Therefore it is true for $k+1$ if true for $k$.

You know it is true for 0, therefore true for 1. True for one, therefore true for 2....

Hope this helps