# 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? Commented Sep 18, 2013 at 20:12
• But that's systematic, suppose q = 1000. Then $r \in {0, 1, ..., 999}$. @abiessu Commented Sep 18, 2013 at 20:18
• Very true, but it is one way to verify the result outside of any proof. Commented Sep 18, 2013 at 20:20
• Proving this by induction is a serious elephant-gun-to-kill-a-fly situation. Commented Sep 19, 2013 at 11:58
• Commented Dec 4, 2015 at 12:47

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? Commented Sep 18, 2013 at 20:21

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? Commented Sep 18, 2013 at 20:16
• @Jossie $n(n+1)(n+2)=(3k + r)\cdot (3k+r+1)\cdot (3k+r+2)$ Commented Sep 18, 2013 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$. Commented Sep 18, 2013 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$. Commented Sep 18, 2013 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}$$