8
$\begingroup$

I am stuck on this problem, and was wondering if anyone could help me out with this. The question is as follows:

Let $n$ be an integer such that $n ≥ 1$. Prove that $6$ divides $n(n + 1)(n + 2)$.

Note: An integer $a$ divides an integer $b$, written $a|b$, if there exists $q ∈ Z$ such that $b = qa$. Alternatively, $a|b$ if dividing $b$ by $a$, $b ÷ a$, results in an integer.

Should I do a proof by induction?

All help/input is appreciated!

$\endgroup$
6
$\begingroup$

The links provided by lab bhattacharjee solve the problem in more generality, but for the sake of completeness...

Let us do an inductive proof. For $n = 0$ things are trivial. Suppose we know the claim for $n$, and we want to prove it for $n+1$. By inductive assumption, $$n(n+1)(n+2) = n^3+2n^2 + 2n = 6 q$$ for some $q$. Now, $$(n+1)(n+2)(n+3) = n(n+1)(n+2) + 3(n+1)(n+2) = 6q + 3(n+1)(n+2)$$ A simple argument (use induction again, if you like) shows that $(n+1)(n+2)$ is divisible by $2$, so you can write $(n+1)(n+2) = 2p$. Consequently, $$(n+1)(n+2)(n+3) = 6(q+p)$$ which finishes the problem.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ I think this answer could use an explanation of why induction is not a good approach to this problem. $\endgroup$ – dfeuer Oct 15 '13 at 20:27
  • 1
    $\begingroup$ I think any approach is good, as long as it works. Personally, I believe it is worth it to try and squeeze as much as possible of methods one is familiar with. If the person posing a problem thinks of induction - why not try it? It generalises quite nicely: Suppose you are trying to prove that $f(n)$ is divisible by $M$ for all $n$. Then just check if $M$ divides $f(0)$, and that $g(n) := f(n+1)-f(n)$ is divisible by $M$ for all $n$. For $g(n)$, if things are not already obvious, just apply the same reasoning. For instance, this proves little Fermat. $\endgroup$ – Jakub Konieczny Oct 16 '13 at 9:53
  • 1
    $\begingroup$ isn't it n(n + 1)(n+2) instead of (n + 2)(n + 3)n ? $\endgroup$ – RiaD Dec 18 '15 at 9:00
8
$\begingroup$

$n$ is either even or odd. Also, it must be congruent, modulo $3$, to either $0$, $1$, or $2$.

| cite | improve this answer | |
$\endgroup$
7
$\begingroup$

Another possibility:

$$\frac{n(n+1)(n+2)}{6}$$ equals the binomial coefficient $$\binom{n+2}{3}$$ which is an integer (since it is the number of 3-element subsets of an ($n+2$)-element set).

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ It's the same as asking why ${ n+2 \choose 3}$ is an integer. $\endgroup$ – user5402 Dec 4 '15 at 17:52
4
$\begingroup$

The product $n(n+1)(n+2) \equiv 0\ (\mathrm{mod}\ 2)$, since if $n$ is even the product will be even, and if $n$ is odd then $n+1$ will be even and again the product is even.

We also know that $n(n+1)(n+2) \equiv 0\ (\mathrm{mod}\ 3)$. You can prove this by notating that $n\ \mathrm{mod}\ 3$ must be $0, 1,$ or $2$, and all of these cases imply the product is divisible by $3$. $$n\equiv0\ (\mathrm{mod}\ 3)\implies n(n+1)(n+2)\equiv0\ (\mathrm{mod}\ 3),$$ $$n \equiv1\ (\mathrm{mod}\ 3)\implies n+2\equiv 0\ (\mathrm{mod}\ 3)\implies n(n+1)(n+2)\equiv0\ (\mathrm{mod}\ 3),$$ $$n\equiv2\ (\mathrm{mod}\ 3)\implies n+1 \equiv 0\ (\mathrm{mod}\ 3) \implies n(n+1)(n+2)\equiv0\ (\mathrm{mod}\ 3).$$

Therefore $n(n+1)(n+2)$ is divisible by $2$ and by $3$, which implies it is divisible by $6$.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Either one of $n$, $n+1$ and $n+2$ is divisible by $3$, because $n$ is either in the form of $3k$, $3k+1$ or $3k+2$. We also have either one of $n$ or $n+1$ is divisible by $2$ because they are two consecutive natural numbers. Thus, the product of $n$, $n+1$ and $n+2$ is always divisible by $2*3=6$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

If we let $m=n+1$, we need to prove that $6 \vert m(m^2-1)$ for all $m \geq 2$. Equivalently, we want to show that $$m^3 \equiv m \bmod6$$ First note that $m \equiv 0,1,2,3,4,5 \pmod 6$. Now observe that following: $$m \equiv 0 \bmod 6 \implies m^3 \equiv 0^3 \bmod 6 \implies m^3 \equiv 0 \bmod6 $$ $$m \equiv 1 \bmod 6 \implies m^3 \equiv 1^3 \bmod 6 \implies m^3 \equiv 1 \bmod6$$ $$m \equiv 2 \bmod 6 \implies m^3 \equiv 2^3 \bmod 6 \implies m^3 \equiv 8 \bmod6 \implies m^3 \equiv 2 \bmod6$$ $$m \equiv 3 \bmod 6 \implies m^3 \equiv 3^3 \bmod 6 \implies m^3 \equiv 27 \bmod6 \implies m^3 \equiv 3 \bmod6$$ $$m \equiv 4 \bmod 6 \implies m^3 \equiv 4^3 \bmod 6 \implies m^3 \equiv 64 \bmod6 \implies m^3 \equiv 4 \bmod6$$ $$m \equiv 5 \bmod 6 \implies m^3 \equiv 5^3 \bmod 6 \implies m^3 \equiv 125 \bmod6 \implies m^3 \equiv 5 \bmod6$$ Hence, in all cases, we have $m^3 \equiv m \bmod 6$, which means that $$6 \vert (m^3-m) \implies 6 \vert n(n+1)(n+2)$$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

If a number is divisible by $6=2\cdot 3$, then it must be divisible by $2$, and also by $3$.

Look at $$n(n+1)(n+2)$$ if $n$ is not divisible by $2$, will any of the other factors be? If $n$ is not divisible by $3$ will any of the factors be?

| cite | improve this answer | |
$\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.