# Proving something is an integer

Please DO NOT post a full solution. I'm only after hints. :-)

A question asked me to prove that by mathematical induction $n^3+3n^2+2n$ is divisible by $6.$ I have done this.

Now in the next part it told me to prove it WITHOUT mathematical induction. I can't seem to figure this out.

So far I have reasoned that we need to rewrite $n^3+3n^2+2n = 6m$ where $m$ is an integer. That is equivalent to proving that $\frac{n^3+3n^2+2n}{6}= m.$ Am I on the right track? Any hints?

I also had an idea to somehow use the floor or ceiling function. Or perhaps I should factorize and manipulate it.

-
$n^3+3n^2+2n=n(n+1)(n+2)$ – L. F. Sep 10 '13 at 0:32
Thanks for the hint! – Bobby Wong Sep 10 '13 at 0:45

Factorise $n^3+3n^2+2n$ and use the fact that among every three consecutive numbers, we will get a multiple of 3, and that among every two consecutive numbers we should get a multiple of 2.

-
Oh you can assume that result? Thanks! :) – Bobby Wong Sep 10 '13 at 0:43

A combinatorial argument: $$\frac{n^3+3n^2+2n}{6}=\frac{(n+2)(n+1)(n)}{3!}=\binom{n+2}{3}.$$

-
Yes I viewed the question like this also in my many attempts but I failed to see how combinatorial is divisible by 6. :/ – Bobby Wong Sep 10 '13 at 0:44
@BobbyWong the RHS is an integer, and so the LHS must be an integer too. – Dan Rust Sep 10 '13 at 0:49
Ah thank you very much! – Bobby Wong Sep 10 '13 at 0:53

Hint: Depending on the remainder of $n$ mod $6$, compute the reminder of $n^3 + 3n^2 + 2n$ mod $6$. (6 cases)

-
I'm not too sure what you mean by residue sorry. – Bobby Wong Sep 10 '13 at 0:44

Hint: $$\begin{array}{|r|l|}\hline n\pmod{6}&0&1&2&3&4&5\\\hline n^2\pmod{6}&0&1&4&3&4&1\\\hline n^3\pmod{6}&0&1&2&3&4&5\\\hline n^3+3n^2+2n\pmod{6}&?&?&?&?&?&?\\\hline \end{array}$$

-
So I think you are getting at I do the same for $3n^2$ and $2n$ and add the columns of the table up to find I will get 0s in the final row. Hence it will be 0 (mod 6) – Bobby Wong Sep 10 '13 at 0:53
Yep, the final row should all be $0$s. – Dan Rust Sep 10 '13 at 0:54