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.

$\endgroup$
7
  • 2
    $\begingroup$ Induction will be handy here. $\endgroup$ Jan 31, 2012 at 11:22
  • $\begingroup$ 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.. $\endgroup$
    – Raynos
    Jan 31, 2012 at 11:26
  • 7
    $\begingroup$ 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$... $\endgroup$
    – Myself
    Jan 31, 2012 at 11:26
  • $\begingroup$ @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$. $\endgroup$
    – lhf
    Jan 31, 2012 at 12:00
  • 1
    $\begingroup$ 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. $\endgroup$
    – Matt E
    Jan 31, 2012 at 17:32

9 Answers 9

29
$\begingroup$

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.

$\endgroup$
2
  • 12
    $\begingroup$ The argument applies equally well to $\pmod{6}$ from the start. $\endgroup$
    – Did
    Jan 31, 2012 at 11:51
  • $\begingroup$ thank you for explaining your steps, really helps my understanding $\endgroup$
    – Raynos
    Feb 1, 2012 at 13:37
19
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ +1, nice connection with Newton's series ! $\endgroup$
    – lhf
    Jan 31, 2012 at 11:42
  • 1
    $\begingroup$ @lhf: Thanks! It seems a natural way to go since another common way to handle this kind of problem is using finite differences. $\endgroup$
    – robjohn
    Jan 31, 2012 at 11:49
14
$\begingroup$

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

$\endgroup$
0
10
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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

$\endgroup$
0
6
$\begingroup$

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.

$\endgroup$
0
6
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Uh, your second statement is the desired conclusion... $\endgroup$ Feb 1, 2012 at 17:55
  • $\begingroup$ Oops, I went overboard and show it is in fact divisble by 6 $\endgroup$ Feb 1, 2012 at 19:00
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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