# Mathematical Induction prove that $n^3+5n$ is divisible by $6$

Sorry, I know this will be a duplicate on the site but the other solution I found confusing and the method look completely different to what I was taught.
Prove that $n^3 + 5n$ is divisible by $6$ by using induction

The question is
Prove by mathematical Induction $(n^3+5n)$ is divisible by $6$

Here is what I have done Assume $n=k$ is true
$\sum_{1}^{k} k =\dfrac{(k^3+5k)}{6}$
Now assume $n=k+1$ is true
$\sum_{1}^{k+1} k+1 =\dfrac{(k+1)^3+5(k+1)}{6}$
Then now $\dfrac{(k+1)^3+5(k+1)}{6}=\sum_{1}^{k} k + (k+1)$
$\dfrac{(k+1)^3+5(k+1)}{6}=\dfrac{(k^3+5k)}{6} + (k+1)$
$\dfrac{(k+1)^3+5(k+1)}{6}=\dfrac{(k^3+5k)}{6} + \dfrac{(6k+6)}{6}$
$\dfrac{(k+1)^3+5(k+1)}{6}=\dfrac{(k^3+11k+6)}{6}$
But the other side doesnt equate (LHS)
$\dfrac{(k^3+3k^2+3k+1)+5k+5}{6}$
$\dfrac{(k^3+3k^2+8k+6)}{6}\ne\dfrac{(k^3+11k+6)}{6}$
I hope my method was clear enough so you can see where I went wrong. It would be much more use to me if you solved it as I learn better from looking at solutions and then applying them to other questions.

• Why do you assume $\sum_{1}^{k} k =\frac{(k^3+5k)}{6}$?
– user
Mar 12 '18 at 15:53
• alternatively (just a thought), $n^3+5n$ is actually $(n-1)n(n+1)+6n$ Mar 12 '18 at 15:55
• $(n+1)^3+5(n+1)= (n^3+5n)+3(n^2+n+2)$. Thus, we have to show that $(n^2+n+2)$ is even. Mar 12 '18 at 15:58

As an alternative for induction step assume $n^3+5n=6k$ is true and we need to prove that $(n+1)^3+5(n+1)=6h$.

Let observe that

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

then we need to show that $3n^2+3n$ is divisibleby $6$ wich can be easily verified by plugging $n=2r$ and $n=2s+1$.

When you start, you assume the given statement is true for $n=k$. The given statement is that $n^3 + 5n$ is divisible by $6$. Then you have to assume $k^3+5k$ is divisible by $6$, i.e., $$6N = k^3+5k$$ for some integer $N$.

There's nothing in the statement about the sum from $1$ to $n$, so the $\sum_1^k k$ term doesn't belong.

From there, you now ask whether $(k+1)^3 + 5(k+1)$ is divisible by $6$, i.e.,

$$6M = (k+1)^3 + 5(k+1)$$ for some integer $M$ (with no relation to $N$, yet). To demonstrate such an integer $M$ exists we expand the right side:

$$6M = k^3 + 3k^2 + 8k + 6$$ $$6M = (k^3 + 5k) + (3k^2 + 3k + 6)$$ $$6M = 6N + (3k^2 + 3k + 6)$$ $$M = N + \frac{3k^2+3k+6}{6} = N + \frac{k^2+k+2}{2} = N+1+\frac{k^2+k}{2}$$

So the problem now reduces to showing that $k^2+k$ is divisible by $2$. But $k^2$ and $k$ have the same parity, so their sum is always even; thus we're done.

I don't follow the induction step. First the base case when $n=1$ is clear since $6\mid 6$. Now suppose that the claim holds when $n=k$ for some $k\geq 1$. This means that $k^3+5k=6m$ for some $m\in \mathbb{N}$. We want to show that $(k+1)^3+5(k+1)$ is divisible by $6$. Expand $$(k+1)^3+5(k+1)=k^3+5k+6+3(k^2+k)$$ and use the induction hypothesis, as well as the fact that the product of two consecutive integers is even.

Alternatively, we can express the polynomial in the binomial coefficient basis using the fact that $$n^k=\sum_{j=0}^k S(k,j)n^{\underline{j}} =\sum_{j=0}^k S(k,j)\binom{n}{j}j!$$ where $S(k,j)$ is the stirling number of the second kind to yield that $$n^3+5n=6\binom{n}{1}+6\binom{n}{2}+6\binom{n}{3}$$

$$n^3+5n = n(n^2+5)$$ On the RHS, factor occur in odd, even pairs, so product is even and divisible by $2$. $$n(n^2+5) \equiv n(n^2+2) \qquad \mod 3$$ Hence if $n \equiv 0$ (mod $3)$ then $3$ divides into the result and if $n \equiv \pm 1$ then $n^2 \equiv +1$ thus $3 | (n^2+2)$ and thus if both $2$ and $3$ are factors, then so is $6$.

a one line proof $$n^3+6n-n=(n-1)n(n+1)+6n$$ ready!

Saying that

$$n^3+5n \text{ is divisible by } 6$$

is not at all the same as saying that

$$\sum_1^k k = \frac{k^3+5k}{6}$$

First of all, I am really confused about that expression $\sum_1^k k$ ... which would seem to be just $k+k+k ....$ ($k$ times), i.e. $k \cdot k$ or $k^2$. Now, was that maybe supposed to be $\sum_{i=1}^k i$?

OK, but that is just a technicality.

Much more importantly: why would you use any kind of sum here?! What does this problem have to do with sums? It has absolutely nothing to do with sums.

So, you're immediately starting on the wrong foot.

$$n^3+5n \text{ is divisible by } 6$$
$$\text{there is some number } k \text{ such that } n^3+5n =6k$$