Proving that $(3n)!$ is divisible by $n! \times (n + 1)! \times (n + 2)!$ if $n$ is greater than 2

Prove that:

If $n$ is greater than 2, then $(3n)!$ is divisible by $n! \times (n + 1)! \times (n + 2)!$

From Barnard & Child's "Higher Algebra".

I know that the highest power of a prime $p$ contained in $N$! is

$$\left\lfloor{\frac{N}{p}}\right\rfloor + \left\lfloor{\frac{N}{p^2}}\right\rfloor + \left\lfloor{\frac{N}{p^3}}\right\rfloor ...$$

I'm unable to show that the formula above gives a higher value for $N = 3n$ than for the sum of its values when $N$ = $n$ , $n + 1$ and $n + 2$, considering the condition that $n > 2$.

• Source of this question, please? Nov 1, 2014 at 11:00
• This sequence is in OEIS: oeis.org/A161581 Nov 1, 2014 at 11:16
• @GerryMyerson The source is Barnard & Child's "Higher Algebra". It's the exercise 37 on page 11. link
– 8wks
Nov 1, 2014 at 11:54
• An interesting combinatorial approach might be to relate the ratio $\frac{(3n)!}{n!(n+1)!(n+2)!}$ to the number of ways in which three candidates $A,B,C$ may draw an election with $n$ votes each, but in such a way that during the whole scrutiny the numbers of votes fulfill $A\geq B\geq C$. Essentially in the same way Catalan numbers are related to the Bertand ballot problem. Jan 8, 2020 at 22:15

It is an easy exercise to show that for all real numbers $x$ we have $$\lfloor 3x\rfloor=\lfloor x\rfloor+\lfloor x+\frac13\rfloor+\lfloor x+\frac23\rfloor.$$ Thus for all $n$ and all prime powers $p^t\ge3$ we have \begin{aligned} \lfloor \frac{3n}{p^t}\rfloor&=\lfloor \frac{n}{p^t}\rfloor+ \lfloor \frac{n}{p^t}+\frac13\rfloor+\lfloor \frac{n}{p^t}+\frac23\rfloor\\ &=\lfloor \frac{n}{p^t}\rfloor+ \lfloor \frac{n+\frac{p^t}3}{p^t}\rfloor+\lfloor \frac{n+\frac{2p^t}3}{p^t}\rfloor\\ &\ge \lfloor \frac{n}{p^t}\rfloor+ \lfloor \frac{n+1}{p^t}\rfloor+\lfloor \frac{n+2}{p^t}\rfloor. \end{aligned} This leaves us to deal with the case $p^t=2$. But because $n>2$, we see that $3n$ exceeds one power of two higher than any of $n,n+1,n+2$. If $n>4$ (thanks, Petite Etincelle!) we have $3n>2(n+2)$, and in the cases $n=3,4$ we have $3n>8>n+2$. This gives us a necessary extra term compensating for the deficiency at $p^t=2$.

More precisely, if $n=2k+1$ is an odd integer, then $\lfloor \dfrac{3n}2\rfloor=3k+1$ in comparison to $$\lfloor\frac n2\rfloor+\lfloor\frac{n+1}2\rfloor+\lfloor\frac{n+2}2\rfloor=k+(k+1)+(k+1)=3k+2.$$ On the other hand, if $n=2k$ is even, then $\lfloor \dfrac{3n}2\rfloor=3k$ and $$\lfloor\frac n2\rfloor+\lfloor\frac{n+1}2\rfloor+\lfloor\frac{n+2}2\rfloor=k+k+(k+1)=3k+1.$$ In either case we are missing a single factor two, so having that single extra term suffices.

Summing the above inequalities for $p^t\ge3$ and coupling the terms corresponding to $p^t=2$ and $p^t=2^\ell$, where $\ell$ is the largest integer such that $2^\ell\le 3n$ shows that for all primes $p$ we have $$\sum_{t>0}\lfloor\frac{3n}{p^t}\rfloor\ge \sum_{t>0}\lfloor\frac{n}{p^t}\rfloor+\sum_{t>0}\lfloor\frac{n+1}{p^t}\rfloor+\sum_{t>0}\lfloor\frac{n+2}{p^t}\rfloor.$$ The claim follows from this.

• +1, a typo: $3n > 2(n+2)$ asks for $n > 4$. Btw, do you know if there is a combinatorial proof? Such as if we want to prove the Catalan number $\dfrac{(2n)!}{n!(n+1)!}$ is an integer, we can remark $\dfrac{(2n)!}{n!(n+1)!} = {2n \choose n} - {2n \choose n-1}$. The result here looks like a generalization Nov 1, 2014 at 14:00
• Thanks for spotting that error, @PetiteEtincelle. Now fixed. I don't know of that kind of a proof. One may exist, though!? Nov 1, 2014 at 14:13
• I want to revive this post. I think it's very great if there is combinatorial proof as @PetiteEtincelle said. Dec 12, 2021 at 1:27