4
$\begingroup$

Prove that $(2n)!$ is always divisible by $n!(n+1)!$.

Context: I am a beginner in number theory. To build up my foundation I am following the book Higher Algebra by S. Barnard and J.M. Child.

I know that the problem could be easily solved by doing simple algebraic manipulation and arguing that Catalan numbers are always integers, but I am wondering if there is another approach to attack this problem, particularly using Legendre's formula.

$\endgroup$
4
  • 1
    $\begingroup$ The number $\frac{(2n)!}{n!\,(n+1)!}=\frac{1}{n+1}\,\binom{2n}{n}$ is known as the $n$-th Catalan number. There are several ways to prove that it is an integer, but I highly recommend that you search on your own since you already know the name of this number. $\endgroup$ Jul 31 '17 at 14:53
  • $\begingroup$ @MichaelRozenberg Does it matter? With the information I gave, he should be able to look for a proof on his own. There are probably many answers to this exact question on this site already. One of these links will most likely offer a method he is looking for. $\endgroup$ Jul 31 '17 at 15:05
  • $\begingroup$ I was curious if there were any examples of proving integrality for ratios of factorials without using combinatorics and found this question on MO. $\endgroup$ Jul 31 '17 at 15:11
  • $\begingroup$ @TrevorGunn For this problem in particular, you can use the identity $$\lfloor 2x\rfloor=\lfloor x\rfloor + \left\lfloor x+\frac{1}{2}\right\rfloor$$ for all $x\in\mathbb{R}$, if you want to avoid even using the fact that binomial coefficients are integers. If you agree that the fact that binomial coefficients are integers is not combinatorial, then the wikipedia page and Michael Rozenberg give alternative non-combinatorial proofs. $\endgroup$ Jul 31 '17 at 15:15
8
$\begingroup$

Write it in lowest terms; what is its denominator?

Since it is $\frac1{n+1}\binom{2n}n$, the denominator must divide $n+1$.

Since it is $\frac{1}{2n+1}\binom{2n+1}n$, the denominator must divide $2n+1$.

Since $n+1$ and $2n+1$ are coprime, the denominator must be $1$.

$\endgroup$
1
  • $\begingroup$ Thankyou@Especially Lime.This is an elegant solution. $\endgroup$
    – Rohit
    Aug 2 '17 at 9:05
2
$\begingroup$

Because $$\frac{(2n)!}{n!(n+1)!}=4\binom{2n-1}{n}-\binom{2n+1}{n}$$

$\endgroup$

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.