Prove that $n(n+1)(n+5)$ is a multiple of $6$

I need to prove that $n(n+1)(n+5)$ is divisible by 6. where $n$ is a natural number. I have used the method of induction. But not successful I got the expression $(k^3+6k^2+5k)+3k^2+15k+12$ when $n=k+1$.

The term inside the bracket is divisible by 6 since we have assumed that the result is true when $n=k$. If we can show that $3k^2+15k+12$ is also divisible by 6, then we are done. But how to proceed?

• Given a natural number $n$, note that the factor $n(n+1)$ implies that $n(n+1)(n+5)$ is a multiple of $2$. Also note that between $n$, $n+1$ and $n+5$ at least one of them (and at most too) is a multiple of $3$. Why? How does this help you? Mar 6, 2016 at 8:16
• Consider the cases that $k$ is even and $k$ is odd seperately. It is easier, however, to not use induction and instead compute $n (n+1) (n + 5)$ modulo 6. Mar 6, 2016 at 8:17
• For your actual question note that $3k^2+15k+12=3(k^2+5k+4)$ and now I ask you, why is $k^2+5k+4$ even and how does it being even help you? Mar 6, 2016 at 8:29
• $3k^{2}+15k+12\equiv 12(k+1)+3k(k+1)$ and $2|k(k+1)$. Mar 6, 2016 at 9:29
• $n(n+1)(n+5)\equiv n(n+1)(n-1)\equiv 0\pmod{6}$, because $n(n+1)(n-1)$ is a product of three consecutive integers, so it is divisible by $2$ and $3$. Mar 6, 2016 at 22:13

\begin{align} n(n+1)(n+5) &=n(n+1)(n+2)+3n(n+1)\\[6pt] &=6\binom{n+2}{3}+6\binom{n+1}{2} \end{align}

Binomial Coefficient Basics

If, instead of Pascal's Triangle, we define the binomial coefficients as $$\binom{n}{k}=\frac{n(n-1)\cdots(n-k+1)}{k!}$$ Then we have \begin{align} \binom{n-1}{k}+\binom{n-1}{k-1} &=\binom{n-1}{k-1}\frac{n-k}k+\binom{n-1}{k-1}\\ &=\binom{n-1}{k-1}\frac nk\\ &=\binom{n}{k} \end{align} Thus, if $\binom{n-1}{k}\in\mathbb{Z}$ for all $k\in\mathbb{Z}$, then $\binom{n}{k}\in\mathbb{Z}$ for all $k\in\mathbb{Z}$.

• Induction on $n$ with $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$. I am assuming that the reader knows a bit about binomial coefficients. This could be very difficult if we don't use any previous results.
– robjohn
Mar 6, 2016 at 17:05
• Rob, yes, I suppose that it is a reasonable assumption (i.e., that the reader knows something about the BC's) - especially given the context of the question here. +1 for a very efficient solution. Mar 6, 2016 at 17:15
• @Dr.MV: I have included an addendum regarding the standard recursion from a more applicable point of view.
– robjohn
Mar 6, 2016 at 18:54
• Excellent ... as always! Wish I could give another vote up. ;-)) Mar 6, 2016 at 21:33

Since we can easily see that $3k^2+15k+12=3(k^2+5k+4)$ is divisible by $3$, it remains to show that it is divisible by $2$.

It suffices to look at $$k^2+k=3k^2+15k+12-2(k^2+7k+6)$$and this is even because $k^2+k=k(k+1)$ is the product of two consecutive natural numbers, and therefore divisible by $2$.

You may also go deeper and prove that $k^2+k$ is even using induction, of course. It will then be induction-within-an-induction.

$$n(n+1)(n+5)=n^3+6n^2+5n\equiv n^3-n\pmod6$$

Now $n^3-n=(n-1)n(n+1)$

One number among $n$, $n+1$, $n+2$ is a multiple of 3.

Since $5 \pmod 3 \equiv 2$, among $n$, $n+1$ and $n+5$, one is a multiple of 3.

Either $n$ or $n+1$ must be an even number (since they are consecutive numbers).

Therefore, n(n+1)(n+5) is a multiple of 2.

As $n(n+1)(n+5)$ is a has both 3 and 2 as factors, it is a multiple of 6.

• As your approach is slightly different from the other answers (and, perhaps, more intuitive), I laud your answer. However, your formatting is a little bizarre (I've tried to clean it up a little---you can roll back the edit if you really don't like it), and your argument is a little unclear (in the fourth line, for example, the pronoun "it" is ambiguous; by "it" do you mean the original polynomial?). I think that it might be a good idea to spend a little bit of editing your answer to add a little bit of exposition and clear up some of the ambiguity. Sep 11, 2018 at 22:16
• Thanks, @XanderHenderson I have also tried to remove some ambiguity. One major reason why my approach is different from the other approaches is that I do not know/understand how the other approaches work. Sep 16, 2018 at 12:58

Continuing from your start, let $k^3+6k^2+5k=6p$ for some $p\in\mathbb Z$.

Now, $$(k+1)(k+2)(k+6)=(k^3+6k^2+5k)+3k^2+15k+12=6p+3k^2+15k+12=6p+3(k^2+5k+4)=6p+3(k+1)(k+4)$$

Case 1: $k$ is even.

Then, $k+4$ is also even. We can thus write $k+4=2q$ for some $q\in\mathbb Z$.

Hence, $$6p+3(k+1)(k+4)=6p+3(k+1)(2q)=6p+6q(k+1)=6(p+q(k+1))$$ where $(p+q(k+1))\in\mathbb Z$.

Thus, the statement is true when $k$ is even.

Case 2: $k$ is odd.

Then, $k+1$ is even. We can thus write $k+1=2q$ for some $q\in\mathbb Z$.

Hence, $$6p+3(k+1)(k+4)=6p+3(k+4)(2q)=6p+6q(k+4)=6(p+q(k+4))$$ where $(p+q(k+4))\in\mathbb Z$.

Thus, the statement is true when $k$ is odd.

Suppose $n$ is a multiple of 6. Then we are done. Suppose $n$ is neither a multiple of 2 or 3. Then $n+1$ must be even, and if $n+1$ is still not a multiple of 3 then $n+5$ is. Note $n+5\equiv n+2$ (mod 3) and since neither $n$ nor $n+1$ is a multiple of 3, then $n+2$ is. If $n$ is even but not a multiple of 3, we proceed the same way to show either $n+1$ or $n+2$ is. The only case left is when $n$ is an odd multiple of 3 then $n+1$ is even and we are done. In any case, we get a factor of 2 and a factor of 3.

You are almost done! Take $3k^2+15k+12$ modulo $6$ to reduce it to proving that $3k(k+1)$ is divisible by $6$. We already have a factor of $3$, so it suffices to show that $k(k+1)$ must be even. But out of any two consecutive numbers exactly one must be even, so their product must be even too; we are done.

You just needed one more step. \begin{align}n(n+1)(n+5) = & (n+1)(n+2)(n+6) \\ = & n^3+9 n^2+20 n+12 \\ = & (n^3+6n^2+5n)+3n^2+15n+12 \\ = & n(n+1)(n+5)+\underbrace{3n(n+5)}_{\star}+12\end{align}

$\bigstar$ If $n$ is even, then $3n$ is divisible by 6, otherwise $n$ is odd and $3(n+5)$ is divisible by 6.

Of course you could have done this immediately.

• $n(n+1)$ is divisible by $2$.
• If neither $n$ nor $n+1$ are divisible by $3$, then $n+2$ and $n+5$ will be.
• exactly one of the three factors, $n$, $n+1$, $n+5$ is divisible by $3$.
• Therefore $n(n+1)(n+5)$ is divisible by $2$ and $3$, and thus by $6$.