# prove for all $n\geq 0$ that $3 \mid n^3+6n^2+11n+6$

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.

• Induction will be handy here. Jan 31, 2012 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.. Jan 31, 2012 at 11:26
• 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$... Jan 31, 2012 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, 2012 at 12:00
• 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. Jan 31, 2012 at 17:32

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.

• The argument applies equally well to $\pmod{6}$ from the start.
– Did
Jan 31, 2012 at 11:51
• thank you for explaining your steps, really helps my understanding Feb 1, 2012 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.

• +1, nice connection with Newton's series !
– lhf
Jan 31, 2012 at 11:42
• @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, 2012 at 11:49

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

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

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

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.

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.

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.

• Uh, your second statement is the desired conclusion... Feb 1, 2012 at 17:55
• Oops, I went overboard and show it is in fact divisble by 6 Feb 1, 2012 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.