Solution: Let $P(n)$ be the proposition “$n^3−n$ is divisible by $3$ whenever $n$ is a positive integer”. Basis Step:The statement $P(1)$ is true because $1^3−1=0$ is divisible by $3$. This completes the basis step. Inductive Step:Assume that $P(k)$is true; i.e. $k^3−k$ is divisible by $3$. To complete the inductive step, we must show that when we assume the inductive hypothesis, it follows that $P(k+1)$, the statement that $(k+1)^3− (k+1)$ is divisible by $3$, is also true. That is,we must show that $(k+1)^3− (k+1)$ is divisible by $3$ . $(k+1)^3− (k+1) =(k^3+3k^2+3k+1)-(k+1)$ this where I want to factorize ..need help.
[Math] Use mathematical induction to prove that $n^ 3 − n$ is divisible by 3 whenever n is a positive integer.
induction
Best Answer
In the inductive step we assumed that $k^3 - k$ is divisible by 3 which means that $k^3 - k = 3M$ where $M$ is an integer. Now we can easily deduce $P(k) \rightarrow P(k+1)$. \begin{align} (k + 1)^3 - (k + 1) &= k^3 +3k^2 +3k + 1 -k - 1\\ &= (k^3- k) + 3k^2 + 3k\\ &= 3M +3k^2 + 3k\\ &= 3(M + k^2 + k)\\ &= 3Z \end{align} where $Z = M + k^2 + k$. Since $Z$ is an integer, it is clear $(k + 1)^3 - (k + 1)$ 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(n - 1)(n + 1) = (n - 1)n(n+1)$. Now $n - 1, n$ and $n+1$ are 3 consecutive integers, so one of them must be divisible by 3 since $n \text{ 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.