13
$\begingroup$

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

$\endgroup$
4
  • 3
    $\begingroup$ Source of this question, please? $\endgroup$ Nov 1, 2014 at 11:00
  • 3
    $\begingroup$ This sequence is in OEIS: oeis.org/A161581 $\endgroup$
    – Irvan
    Nov 1, 2014 at 11:16
  • 1
    $\begingroup$ @GerryMyerson The source is Barnard & Child's "Higher Algebra". It's the exercise 37 on page 11. link $\endgroup$
    – 8wks
    Nov 1, 2014 at 11:54
  • $\begingroup$ 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. $\endgroup$ Jan 8, 2020 at 22:15

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ +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 $\endgroup$ Nov 1, 2014 at 14:00
  • $\begingroup$ Thanks for spotting that error, @PetiteEtincelle. Now fixed. I don't know of that kind of a proof. One may exist, though!? $\endgroup$ Nov 1, 2014 at 14:13
  • $\begingroup$ I want to revive this post. I think it's very great if there is combinatorial proof as @PetiteEtincelle said. $\endgroup$
    – LoveMaths
    Dec 12, 2021 at 1:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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