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 having some trouble with this question and can't really get how to prove this..

I have to prove $n^3+6n^2+11n+6$ is divisible by $3$ for all $n \geq 0$.

I have tried doing $\dfrac{m}{3}=n$ and then did $m=3n$

then I said $3n=n^3+6n^2+11n+6$ but now I am stuck.

share|improve this question
2  
Induction will be handy here. –  Henry Shearman Jan 31 '12 at 11:22
    
Yeah but ive thought of it thats why I found n=0 gives 6 in the equation which is divisible by 3 then i found n=1 gives 24 which is divisible as well n=2 gave 60....i know i can do induction but I cant think of how to put it in words.. –  Raynos Jan 31 '12 at 11:26
7  
If you know what "mod 3" means then $n^3 + 6n^2 + 11n + 6 \equiv n^3 - n = (n-1)n(n+1) \equiv 0 \pmod 3$... –  Myself Jan 31 '12 at 11:26
    
@Raynos, induction is simple. You prove it for $n=0$, which you have done. Now assume that $n^3+6n^2+11n+6$ is divisible by $3$. You want to prove that the same holds for $n+1$, that is, that $(n+1)^3+6(n+1)^2+11(n+1)+6$ is divisible by $3$. Just expand and collect all multiples of $3$. –  lhf Jan 31 '12 at 12:00
1  
Dear Raynos, The following comment is not directed at solving your problem, but rather at clearing up a misconception that appears in the last two lines of your post: if $n^3 + 6n^2 + 11n+ 6$ is divisible by $3$, then you are correct that you can write as $3$ times another number (this is the meaning of divisible), but you shouldn't call that other number $n$, since it (amost certainly) won't be the same number $n$ that you started with. E.g. when $n = 1$, you get $1^3 + 6 \cdot 1^2 + 11\cdot 1 + 6 = 24 = 3\cdot 8,$ and $8$ is not the same as the original value $n = 1$ that you began with. –  Matt E Jan 31 '12 at 17:32

9 Answers 9

up vote 26 down vote accepted

If you know what "mod 3" means then argue as follows: $$n^3 + 6n^2 + 11n + 6 \equiv n^3 - n = (n-1)n(n+1) \equiv 0 \pmod 3 .$$

If you don't, then write this as: $$ n^3 - n + 12n + 6n^2 + 6 = n(n+1)(n-1) + 3(2n^2 + 4n + 2), $$ and you're left with showing that both terms are divisible by $3$.

Now $n(n+1)(n-1)$ is always a multiple of $3$, because if a number is not a multiple of 3, then either its predecessor or its successor must be.

share|improve this answer
9  
The argument applies equally well to $\pmod{6}$ from the start. –  Did Jan 31 '12 at 11:51
    
thank you for explaining your steps, really helps my understanding –  Raynos Feb 1 '12 at 13:37

We have $$ \begin{align} n^3+6n^2+11n+6 &=6\binom{n}{3}+18\binom{n}{2}+18\binom{n}{1}+6\binom{n}{0}\\ &=6\left(\binom{n}{3}+3\binom{n}{2}+3\binom{n}{1}+\binom{n}{0}\right) \end{align} $$ so $6\mid(n^3+6n^2+11n+6)$ for all $n\in\mathbb{Z}$.

Of course, since $3\mid 6$, we have $3\mid(n^3+6n^2+11n+6)$, as requested.

share|improve this answer
1  
+1, nice connection with Newton's series ! –  lhf Jan 31 '12 at 11:42
1  
@lhf: Thanks! It seems a natural way to go since another common way to handle this kind of problem is using finite differences. –  robjohn Jan 31 '12 at 11:49
7  
@Saeed: it is not tagged homework. Besides, if it were homework, this answer most likely uses topics not yet covered in the class. –  robjohn Jan 31 '12 at 12:19
1  
@Saeed: I've added some parentheses that probably should have been there. –  robjohn Jan 31 '12 at 12:55
6  
@Saeed Number one you don't even know if this is homework. Perhaps the OP is having some conceptual understandings? You can't just assume things like that. Besides I don't think it is particularly nice to go on a downvoting spree based on your comment that "it can't be a problem with mathematician". Have you read the FAQ to this site? It's for people studying mathematics at $\textbf{any}$ level and professionals in related fields. –  user38268 Jan 31 '12 at 14:01

Prove it for $n=0,1,2$, which is a simple calculation. Every number is of the form $n=3x+r$ where $r=0,1,2$. Now expand $n^3+6n^2+11n+6$ in terms of $x$ and $r$. You'll get $r^3+6r^2+11r+6$ plus a multiple of $3$.

share|improve this answer

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

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

Now , since this last expression represents a product of three consecutive integers it has to be divisible by $3$ .

share|improve this answer

What you can do is the following: Every integer in the universe is either of the form $3m, 3m+1 $ or $3m+2$. Then do a casebash:

If $n=3m$, then clearly $3|(3m)^3+6(3m)^2+11(3m) + 6$.

If $n = 3m+ 1$, then putting this into your expression above we get

$$\begin{eqnarray} (3m+1)^3 + 6(3m+1)^2 + 11(3m+1) + 6 &=& 3(\text{stuff}) + 24 \\ &=& \text{a multiple of 3}. \end{eqnarray}$$

You can do a similar computation for $n= 3m+2$ as well so you are done.

share|improve this answer

Here is a solution using induction:

Let $f(x)=x^3+6x^2+11x+6$

Since we want to see if it is divisible by 3 let us assume that $f(x)=3m$.

For the case where $x=0$, $f(0)=6$ which is divisible by 3.

Now that we have proved for one case let us prove for the case of $f(x+1)$

$$f(x+1)=(x+1)^3+6(x+1)^2+11(x+1)+6$$ $$= x^3+3x^2+3x+1+6x^2+12x+6+11x+11+6$$ $$=(x^3+6x^2+11x+6)+3x^2+15x+18$$

And since $x^3+6x^2+11x+6=3m$ $$f(x+1)=3m+3x^2+15x+18=3(m+x^2+5x+6)$$ Which is divisible by 3.

share|improve this answer

There's an algorithm for finding rational roots of a polynomial with integer coefficients, and if you use that to factor this polynomial you get $$ n^3 + 6n^2 + 11n + 6 = (n+1)(n+2)(n+3). $$ For any $n$, one of those three factors is a multiple of $3$.

share|improve this answer

We have $$n^3 + 6n + 11n + 6 = (n+1)(n+2)(n+3).$$ A run of three consecutive integers has an integer in it divisible by 2, so $$2|n^3 + 6n + 11n + 6.$$ A run of three consecutive integers has an integer in it divisible by 3, so $$3|n^3 + 6n + 11n + 6.$$

Since 2 and 3 are relatively prime, the desired conclusion follows right away.

share|improve this answer
    
Uh, your second statement is the desired conclusion... –  The Chaz 2.0 Feb 1 '12 at 17:55
    
Oops, I went overboard and show it is in fact divisble by 6 –  ncmathsadist Feb 1 '12 at 19:00

A simple fact to remember is that the "modulo k" operator can be copied "inside" addition, subtraction and multiplication without altering the result... to say it more formally

$$(a + b)_{mod\ k} = (a_{mod\ k} + b_{mod\ k})_{mod\ k}$$ $$(a - b)_{mod\ k} = (a_{mod\ k} - b_{mod\ k})_{mod\ k}$$ $$(ab)_{mod\ k} = ((a_{mod\ k})(b_{mod\ k}))_{mod\ k}$$ $$(a^n)_{mod\ k} = ((a_{mod\ k})^n)_{mod\ k}$$

Your problem is to prove that $(n^3 + 6n^2 + 11n + 6)_{mod\ 3} = 0$. Just expanding the problem statement using the above equations you get:

$$((n_{mod\ 3})^3 + (6_{mod\ 3})(n_{mod\ 3})^2 + (11_{mod\ 3})(n_{mod\ 3}) + 6_{mod\ 3})_{mod\ 3} = 0$$

Observing that $6_{mod\ 3}=0$ and $11_{mod\ 3}=2$ the expression can be simplified to

$$ ((n_{mod\ 3})^3 + 2(n_{mod\ 3}))_{mod\ 3} = 0 $$

Given that $n_{mod\ 3}$ is either 0, 1 or 2 you only need to test these three cases and this is trivial as it amounts to checking that $(0+0)$, $(1+2)$ and $(8+4)$ are all divisible by 3.

Note of course that it was also quite obvious without any computation that adding or subtracting $6$ or $6n^2$ (both multiples of 3) was not going to change the fact that an expression is divisible by 3 or not.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.