Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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. –  Hypem Oct 6 '13 at 18:38
    

4 Answers 4

up vote 7 down vote accepted

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)$.

share|improve this answer
    
That's what I found but couldn't express as a consistent mathematical proof. –  user93957 Oct 6 '13 at 18:37
    
@Adobe Added something. –  Pedro Tamaroff Oct 6 '13 at 18:37
1  
@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
1  
@Adobe Do you know what the Euclidean algorithm is? –  Pedro Tamaroff Oct 6 '13 at 18:52
1  
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$

share|improve this answer
1  
$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.

share|improve this answer
3  
+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}$.

share|improve this answer
    
Eloquently explained, thanks! :-) –  user93957 Oct 6 '13 at 19:56
1  
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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.