midtlinjeg

2021-08-16

Use mathematical induction to prove that ${n}^{3}-n$
is divisible by 3 whenever n is a positive integer.

pierretteA

In the inductive step we assumed that ${k}^{3}-k$ is divisible by 3 which means that ${k}^{3}-k=3M$ where is an integer. Now we can easily deduce $P\left(k\right)\to P\left(k+1\right)$.
${\left(k+1\right)}^{3}-\left(k+1\right)={k}^{3}+3{k}^{2}+3k+1-k-1$
$=\left({k}^{3}-k\right)+3{k}^{2}+3k$
$=3M+3{k}^{2}+3k$
$=3\left(M+{k}^{2}+k\right)$
$=3Z$
where $Z=M+{k}^{2}+k$. Since Z is an integer, it is clear ${\left(k+1\right)}^{3}-\left(k-1\right)$ is divisible by 3 if ${k}^{3}-k$ is divisible by 3. Thus concludes the proof.
Now there is a much easier proof that does not require induction, factor ${n}^{3}-n$ as $n\left(n-1\right)\left(n+1\right)=\left(n-1\right)n\left(n+1\right)$. Now n-1, n and n+2 are 3 consecutive integers, so one of them must be divisible by 3 since n mod 3 can take on 3 different values(0, 1 and 2) and the 3 consecutive integers each have a different value, so one of them will be 0 (mod 3). Since one of the integers in the product is divisible by 3, so is the whole product.

Do you have a similar question?