# Solution

Prove that $n^3+n$ is even for every positive integer $n$.

Suppose we proceed to argue by induction (although there are more efficient approaches, as the bottom of this page indicates).

Starting with the basis step, we must show that the statement holds for the smallest value of $n$ that we wish to consider.

Since we seek to prove the statement holds for every positive integer, then the smallest value we wish to consider would be $n=1$.

When $n=1$, we note $n^3+n = 1^3 + 1 = 2$, which is even. Thus, the statement is true when $n=1$.

Now we proceed with the inductive step, where we must show that if we know the statement holds for some particular value of $n$, say $n=k$, then the statement must also hold when $n=k+1$.

Equivalently, for this problem, we need to show if the following "inductive hypothesis" is true for some particular value $k$, $$k^3 + k \textrm{ is even}$$ then it must also be true that $$(k+1)^3 + (k+1) \textrm{ is even}$$

To this end, we start by expanding this last expression and regrouping the resulting terms, so that we might create an opportunity to use the inductive hypothesis: $$\begin{array}{rcl} (k+1)^3 + (k+1) &=& k^3 + 3k^2 + 3k + 1 + k + 1\\\\ &=& (k^3 + k) + 3k^2 + 3k + 2\\\\ &=& (k^3 + k) + 3k(k+1) + 2\\\\ \end{array}$$

Note, $3k(k+1)$ must be even as either $k$ or $(k+1)$ must be even. Since $(k^3+k)$ was assumed even (by our inductive hypothesis), and 2 is obviously even as well, we have expressed $(k+1)^3 + (k+1)$ as the sum of three even values. As such $(k+1)^3 + (k+1)$ must be even -- which is what we needed to show.

Having met with success in both the basis and inductive steps, we are free to conclude by the principle of mathematical induction, that $n^3 + n$ must be even for every positive integer $n$.

QED.

As suggested above, however, we can argue the same conclusion much more efficiently with a different (non-induction based) strategy:

Suppose we argue by cases:

We know that every positive integer $n$ must be either even, or odd, so

1. If $n$ is even, then $n^3$ must also be even. So $n^3 + n$ is the sum of two even values, which must be even.

2. If $n$ is odd, then $n^3$ must also be odd. So $n^3 + n$ is the sum of two odd values, which also must be even.

As such, for every positive integer $n$, it must be true that $n^3 + n$ is even.

QED.