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$.