8
$\begingroup$

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.

  • 0
    This question get +1 due to the nice diversity of answers it has produced :)2012-01-31

9 Answers 9

29

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.

  • 0
    thank you for explaining your steps, really helps my understanding2012-02-01
19

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
    @lhf: Thanks! It seems a natural way to go since another common way to handle this kind of problem is using finite differences.2012-01-31
14

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

10

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

10

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

6

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.

6

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.

2

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.

  • 0
    Oops, I went overboard and show it is in fact divisble by 62012-02-01
1

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.