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.

  • 2
    Induction will be handy here.2012-01-31
  • 0
    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..2012-01-31
  • 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$...2012-01-31
  • 0
    @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$.2012-01-31
  • 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.2012-01-31
  • 0
    So setting $3 n = n^3 + 6 n^2 + 11 n = 6$ is *not* the correct way to proceed (it is already not true in the case $n = 1$, as we just saw). As the answers below show, questions of this type are usually best answered by manipulating the expression $n^3 + 6n^2 + 11 n + 6$ in some way, not by setting it equal to something else. Regards,2012-01-31
  • 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.

  • 12
    The argument applies equally well to $\pmod{6}$ from the start.2012-01-31
  • 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
    +1, nice connection with [Newton's series](http://en.wikipedia.org/wiki/Newton_series#Newton.27s_series) !2012-01-31
  • 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
    Uh, your second statement is the desired conclusion...2012-02-01
  • 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.