Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I tried proving inductively but I didn't really go anywhere. So I tried:

Let $3|n(n+1)(n+2)$.

Then $3|n^3 + 3n^2 + 2n \Longrightarrow 3|(n(n(n+3)) + 2)$

But then?

share|improve this question
6  
Have you considered trying the three possibilities of $n=3k, n=3k+1, n=3k+2$ and seeing what that implies? –  abiessu Sep 18 '13 at 20:12
    
But that's systematic, suppose q = 1000. Then $r \in {0, 1, ..., 999}$. @abiessu –  Don Larynx Sep 18 '13 at 20:18
    
Very true, but it is one way to verify the result outside of any proof. –  abiessu Sep 18 '13 at 20:20
    
Proving this by induction is a serious elephant-gun-to-kill-a-fly situation. –  Jack M Sep 19 '13 at 11:58

7 Answers 7

up vote 16 down vote accepted

Here is a proof by induction.

The base case $n=0$ or $n=1$ is trivial.

Suppose that $3$ divides $n(n+1)(n+2)$ and consider $(n+1)(n+2)(n+3)$. Expand on $n+3$ and get $(n+1)(n+2)(n+3) = n(n+1)(n+2)+3(n+1)(n+2)$. Since by hypothesis $3$ divides the first term and it clearly divides the second one, it must divide the sum.

This proof can be generalized to $k \mid n(n+1)\cdots(n+k-1)$ using the same technique.

share|improve this answer
    
WolframAlpha gave me an unclear answer, n(n(n+6) + 11). So is this something that just needs to be done by hand? –  Don Larynx Sep 18 '13 at 20:21
    
+1 for generalizing. :-) –  abiessu Sep 18 '13 at 20:38

you can write $n=3\cdot k + r$ for some $k\in \mathbb{N}$ and $r\in \{0,1,2\}$. Then exactly one of $n,n+1,n+2$ is divisible by 3.

share|improve this answer
    
This isn't immediately clear to me? –  Don Larynx Sep 18 '13 at 20:16
    
@Jossie $n(n+1)(n+2)=(3k + r)\cdot (3k+r+1)\cdot (3k+r+2)$ –  Dominic Michaelis Sep 18 '13 at 20:19
    
More expanded form: $n(n+1)(n+2)=(3k+\{0,1,2\})(3k+\{1,2,3\})(3k+\{2,3,4\})$. Whichever value $r$ takes on, one of those three terms will always be divisible by $3$. –  abiessu Sep 18 '13 at 20:34
    
Either $r=0$ in which case $n=3k$, or $r\gt 0$ when you can choose $s\in \{1,2\}$ such that $n+s=3k+r+s=3(k+1)$. Out of three consecutive numbers, precisely one is divisible by $3$. –  Mark Bennet Sep 18 '13 at 20:44

To do it inductively, we also need a base case: $0 \times 1 \times 2=0$ is divisible by $3$. Then, if $3$ divides $k(k+1)(k+2)=k^3+3k^2+2k$ then \begin{align*} (k+1)(k+2)(k+3) &= k^3+6k^2+11k+6 \\ &= (k^3+3k^2+2k)+3(k^2+3k+2). \end{align*} We know $k^3+3k^2+2k$ is divisible by $3$, by the inductive hypothesis, and $3(k^2+3k+2)$ is divisible by $3$ since $k^2+3k+2$ is an integer. Therefore, by induction, $k(k+1)(k+2)$ is divisible by $3$ for all $k \geq 0$.

Note, if we want to prove it for negative $k$ too, we'd need to perform "induction in reverse".

share|improve this answer

The binomial coefficients are all integers (various proofs). Hence $$\binom r3=\frac {r(r-1)(r-2)}{6}$$ is an integer. Let $r=n+2$, then $6$ is a factor of your product and $3|6$.

In a similar way you can prove that the product of $k$ consecutive integers is divisible by $k!$ - this cam also be done by induction (which is hidden in the statement "the binomial coefficients are all integers" and implicit in the construction of Pascal's Triangle.

share|improve this answer

Assume $n(n+1)(n+2) = 3p$. $$(n+1)(n+2)(n+3) = \frac{n(n+1)(n+2)(n+3)}{n} =3p\cdot\frac{n+3}{n}=3p+3\cdot\frac{3p}{n}$$

Notice $\frac{3p}{n}$ is also an integer by assumption.

With this induction step, the base case has to be $n=1$. Prove the case for $n=0$ separately.

share|improve this answer

Here's a somewhat tedious (but fairly elementary) way. By the division algorithm, we can write $n=3k+r$ for some integers $k,r$ with $0\le r\le 2,$ whence $$\begin{align}n(n+1)(n+2) &= (3k+r)(3k+r+1)(3k+r+2)\\ &= (3k+r)(9k^2+6kr+9k+r^2+3r+2)\\ &= 27k^3+27k^2r+27k^2+9kr^2+18kr+6k+r^3+3r^2+2r\\ &= 3(9k^3+9k^2r+9k^2+3kr^2+6kr+2k+r^2)+r^3+2r.\end{align}$$ All that's left is to show that $r^3+2r$ is a multiple of $3$ for $r=0,1,2$.

share|improve this answer

Consider the binomial $(x+1)^{n+2}$. The coefficient of the $x^3$ term is

$${n+2\choose 3}={(n+2)!\over 3!(n-1)!}={n(n+1)(n+2)\over 6}$$

Every coefficient of $(x+1)^n$ is an integer for $n$ an integer, therefore $6|n(n+1)(n+2)$ and thus $3|n(n+1)(n+2)$.

Note that this mechanism can apply to any integer, including showing that $1000|n(n+1)(n+2)\cdots(n+998)(n+999)$.

As noted elsewhere, this property of the binomial coefficients is provable by induction, which demonstrates that an inductive proof is truly the proper way to show the question's property. In binomial terms, the inductive step occurs by noting that

$${n\choose k-1}+{n\choose k}={n+1\choose k}$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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