College Algebra, Chapter 9, 9.5, Section 9.5, Problem 18

Prove that $n^3 - n + 3$ is divisible by 3 for all natural numbers $n$.

Let $P(n)$ denote the statement $n^3 - n + 3$ is divisible by 3

Step 1: $P(1)$ is true, since $1^3 - 1 + 3$ is divisible by 3

Step 2: Suppose $P(k)$ is true. Now


$\begin{equation} \begin{aligned} (k + 1)^3 - (k + 1) + 3 =& (k + 1) [(k + 1)^2 - 1] + 3 \\ \\ =& (k + 1) [(k^2 + 2k + 1) - 1] + 3 \\ \\ =& (k + 1) (k^2 + 2k) + 3 \\ \\ =& k^3 + 2k^2 + k^2 + 2k + 3 \\ \\ =& k^3 + 3k^2 + 2k + 3 \\ \\ =& k^3 + 3k^2 + (3 - 1)k + 3 \\ \\ =& k^3 + 3k^2 + 3k - k + 3 \\ \\ =& [k^3 - k + 3] + 3 [k^2 + k] \end{aligned} \end{equation}$


By the induction hypothesis, $k^3 - k + 3$ is divisible by $3$ and $3 [k^2 + k]$ is clearly divisible by $3$ because the statement is in multiple of $3$.

So, $P(k + 1)$ follows from $P(k)$. Thus, by the principle of mathematical induction $P(n)$ holds for all $n$.