# Proof that $n^3 + 3n^2 + 2n$ is a multiple of $3$.

I'm struggling with this problem:

For any natural number $n$, prove that $n^3 + 3n^2 + 2n$ is a multiple of $3$.

That $n^3 + 3n^2 + 2n$ is a multiple of $3$ means that: $n^3 + 3n^2 + 2n = 3 \times k$ where $k \in \mathbb N$ So I tried to find a the number $k$.

The best result I found was: $n^3 + 3n^2 + 2n = n(n+1)(n+2)$ But I'm lagging at the last step, to prove that it is a multiple of $3$.

(However, I got the intuition, If you see the multiples of $3$: $\{0, 3, 6, 9,\dotsc\}$ there is a difference of $3$ between them.

So $n(n+1)(n+2)$ incorporates that difference. This means that if you take a number $n$ then $n$ or $n+1$ or $n+2$ could be a multiple of $3$ and so their multiplication is a multiple of $3$) But I couldn't extend that idea into a consistent mathematical proof.

Also this problem doesn't help either: Proof that $n^3+2n$ is divisible by 3

-
In $\mathbb{Z}_3$, n is either $0,1$ or $2$. From Euclidian algorithm $n=3q$ or $n=3q$ +1 or $n=3q +2$, with q $\in \mathbb{Z}$. Replace $n$ in the equation by each case and see the result. – Alexis Marchand Oct 6 '13 at 18:38

Among three consecutive integers, one must be a multiple of three. Reason: if $n=3k$, we're done. If $n=3k+1$ then $n+2=3j$ is a multiple of three. If $n=3k+2$, then $n+1=3m$ is a multiple of three. In any case, $3\mid n(n+1)(n+2)$.

-
That's what I found but couldn't express as a consistent mathematical proof. – user93957 Oct 6 '13 at 18:37
@Adobe True. But any natural number can be expressed either as $3k,3k+1$ or $3k+2$. So we look into the three possible cases. All of them yield a positive result, so we're done. – Pedro Tamaroff Oct 6 '13 at 18:43
@Adobe Do you know what the Euclidean algorithm is? – Pedro Tamaroff Oct 6 '13 at 18:52
Anyway, I found a little proof (not really one) without using what I haven't already learnt. So thank you so much @PedroTamaroff for your effort, that was really helpful! ;-) – user93957 Oct 6 '13 at 19:54

HINT: $$n^3+3n^2+2n=n^3-n+3n^3+3n\equiv \underbrace{(n-1)n(n+1)}_{\text{ product of three consecutive integers}}\pmod3$$

Among three consecutive integers, on must be divisible by $3$

-
$n(n+1)(n+2)$ that I found is also the product of three consecutive integers but I couldn't express the "one must be divisible by 3" mathematically. – user93957 Oct 6 '13 at 18:38
@Adobe, though over-killing, we can use induction as follows: If $F(n)=(n+1)n(n-1),F(n+1)-F(n)=(n+2)(n+1)n-(n+1)n(n-1)=3(n+1)n$ Now, what is $F(0)$ or $F(1)?$ – lab bhattacharjee Oct 6 '13 at 18:42

Yes, you're on the right track and have realized the important points. Now consider using the pigeonhole principle: It's clear that none of the numbers $n$, $n + 1$, $n + 2$ leave the same remainder when divided by $3$, and the remainders lie in $\{0, 1, 2\}$. Three remainders, three distinct numbers: One of them has to be zero.

-
+1 on the pigeonhole principle. – Pedro Tamaroff Oct 6 '13 at 19:37

In response to your inductive proof link to another example, I thought you might find a similar proof useful to prove that $n^3 + 3n^2 + 2n = n(n+1)(n+2)$ is a multiple of $3$ (I will say divisible by 3, you can modify it yourself if you care).

$\textbf{Proof:}$ (by induction on $n$):

For the basis $n=1$, the result is trivial.

Assume the divisibility holds for $n=k$, that is, $$3 \, | \, k(k+1)(k+2).$$

Let $n=k+1$. Then

$$(k+1)(k+2)(k+3)=k(k+1)(k+2) + 3(k+1)(k+2).$$

Now clearly $$3 \, | \, 3(k+1)(k+2),$$ and from our inductive hypothesis, we have that $$3 \, | \, k(k+1)(k+2).$$ Hence $$3 \, | \, (k(k+1)(k+2) + 3(k+1)(k+2)).$$ Therefore $3 \, | \, n(n+1)(n+2)\, \forall \, n \in \mathbb{N}$.

-
Eloquently explained, thanks! :-) – user93957 Oct 6 '13 at 19:56
You could have made that algebra much easier in the middle by just splitting the factor of k+3 and leaving the other two factors alone. – Chris Oct 6 '13 at 22:49
Its not a bad way. I just got to the end and thought "oooh, that looks like a nice result. Oooh, look it factorises nicely to a really nice result! oh wait, that's what we started with..." – Chris Oct 6 '13 at 23:01
@Chris : On afterthought, I removed the entire middle of that algebra as it is so painfully obvious. Maybe I should not do algebra while eating omelettes. Nice call there, thanks for the read. – J. W. Perry Oct 6 '13 at 23:18