Proving $n(n^2+5)$ is always even

Question

Prove that $n(n^2+5)$ is even for all $n\in\mathbb{N}$

I think this can be solved by letting $n=2k$ and $n=2k+1$, and arriving at expressions which are both even. I wondered then if this could also be possible by induction. The expression is even for $n=1$ and if $k(k^2+5)$ is even for some k, then the inductive step $n=k+1$ is :

$$\begin{align}(k+1)((k+1)^2+5)&=(k+1)(k^2+2k+6)\\&=k^3+2k^2+6k+k^2+2k+6\\&=k^3+3k^2+8k+6\end{align}$$

Subtracting $k(k^2+5)$ this becomes $3k^2+3k+6$, which is not necessarily even. Is it safe to say that it's "impossible" to prove the statement by induction then, or can this be continued?

Edit : Comments, expression is even!

Answer 1

This is a bit more like what you were doing, but it's also a trick you might find interesting.

Let's write $f(n) = n(n^2+5)$ and let $\Phi(n)$ be the statement

$$ f(n)\text{ is even and } f(n+1)\text{ is also even.}$$

Now we're going to prove $\Phi(n)$ for all $n$ by induction. We need to show $\Phi(0)$ is true and also that $\Phi(n)$ implies $\Phi(n+1)$ for all $n$. The base case is $\Phi(0)$ which just says

$$ f(0)\text{ is even and } f(1)\text{ is also even}\\\\ \equiv \\\\ 0\text{ is even and }6\text{ is also even }$$

Now suppose we know $\Phi(n)$ and we want to prove $\Phi(n+1)$. That is, we know $$ f(n)\text{ is even and } f(n+1)\text{ is also even}$$

and we want to show

$$ f(n+1)\text{ is even and } f(n+2)\text{ is also even}.$$

The $f(n+1)$ part is trivial.

For $f(n+2)$ we will use your method. Expanding $f(n+2)$ we get:

$$\begin{align} f(n+2) & = (n+2)((n+2)^2 + 5) \\ & = (n+2) (n^2+4n+9) \\ & = n^3 + 4n^2 + 9n + 2n^2 + 8n + 18 \\ & = n^3 + 6n^2 + 17n + 18 \end{align}$$

Subtracting $n(n^2+5) = n^3+5n$ as you suggested we get:

$$ 6n^2 + 12n + 18$$

which is obviously even.

---

The $f(n+1)$ part is of no real importance. What we're really doing is using the slightly modified induction principle that if $\Phi(n)$ implies $\Phi(n+2)$, and if $\Phi(0)$ and $\Phi(1)$ are true, then $\Phi(n)$ is true for all $n$.

Answer 2

Not by induction (but see this, this, this and this, maybe they give you an idea). The expression $n(n^2+5)$ is even if $n$ is even (because of the $n$ factor). Therefore, we just need to set $n$ odd and check that the expression is even. Setting $n=2k+1$, we have $$ n^2+5 = 4k^2+4k+6 = 2(2k^2+2k+3) $$ that is even. Therefore, the whole expression is even.

Answer 3

Here is a proof by induction. It's a bit hairy. We want to prove the function $f(n) = n(n^2 + 5)$ is always even. This is equivalent to testing that $f(n)$ is divisible by $2$, $\forall n \in \mathbb{N}$. So we prove that $2 \vert f(n)$, $\forall n \in \mathbb{N}$. We first consider the base case. There is a minor technicality, sometimes $0$ is not considered a member of the naturals, but we will do so here:

$$2 \vert f(0) \iff 2 \vert 0 $$

And so the base case holds. Now we apply induction:

$$2 \vert (n + 1)((n + 1)^2 + 5)$$ $$2 \vert n(n^2 + 5) + 3n^2 + 3n + 6$$

From the induction hypothesis $2 \vert n(n^2 + 5)$ and furthermore we have that $2 \vert 6$ so what remains is to prove that $2 \vert 3n^2 + 3n$. We do so by induction. We define $g(n) = 3n(n + 1)$. We first consider the base case $n = 0$:

$$2 \vert g(0) \iff 2 \vert 0 $$

And so the base case holds. Now we apply induction:

$$2 \vert g(n + 1) \iff 2 \vert 3(n + 1)(n + 2)$$ $$2 \vert g(n + 1) \iff 2 \vert 3n(n + 1) + 6(n + 1)$$

From the induction hypothesis we have that $2 \vert 3n(n + 1)$ and furthermore we have that $2 \vert 6(n + 1)$ and so we conclude $2 | g(n)$, $\forall n \in \mathbb{N}$, which means $2 \vert f(n)$, $\forall n \in \mathbb{N}$ and so $f(n)$ is even $\forall n \in \mathbb{N}$.