# Prove $3|n(n+1)(n+2)$ by induction

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?

-
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

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.

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

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

-

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.

-

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.

-

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

-

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

-