Prove that $\binom{k+l}{l}$ divides $\binom{2k}{k}\binom{2l}{l}$?

196 Views Asked by At

Here is the question:

For $k \ge 0, l \ge 0$, prove that $\binom{k+l}{l}$ divides $\binom{2k}{k}\binom{2l}{l}$.

I try to prove it by induction on $k$ and with $l$ fixed.

For $k=0$, clearly $\binom{l}{l}=1$ divides $\binom{2l}{l}$.

For the case $k+1$, I have : $\binom{l+k+1}{l}=\frac{(l+k+1)}{(k+1)}\binom{k+l}{l}$ and on the other side : $\binom{2k+2}{k+1}\binom{2l}{l}=\frac{(2k+2)(2k+1)}{(k+1)}\binom{2l}{l}\binom{2k}{k}$.

Then I don't know how to continue.

1

There are 1 best solutions below

5
On BEST ANSWER

Let $p$ be some prime and consider the identity $$\frac{\binom{2k}{k}\binom{2l}{l}}{\binom{k+l}{l}}=\frac{(2k)!(2l)!}{k! l! (k+l)!} \tag{1}$$ and Legendre's theorem $$ \nu_p(n!) = \sum_{k\geq 1}\left\lfloor\frac{n}{p^k}\right\rfloor \tag{2}$$ If we prove that for any prime power $P$ we have $$ \left\lfloor\frac{2k}{P}\right\rfloor+\left\lfloor\frac{2l}{P}\right\rfloor-\left\lfloor\frac{k+l}{P}\right\rfloor-\left\lfloor\frac{k}{P}\right\rfloor-\left\lfloor\frac{l}{P}\right\rfloor \geq 0 \tag{3}$$ it follows that $$ \nu_p\left(\frac{\binom{2k}{k}\binom{2l}{l}}{\binom{k+l}{l}}\right)\geq 0 \tag{4} $$ for any prime $p$, so $\binom{k+l}{l}$ is a divisor of $\binom{2k}{k}\binom{2l}{l}$. Instead of proving the original claim by induction, just prove $(3)$ by induction or the equivalent inequality with fractional parts:

$$ \left\{\frac{2k}{P}\right\}+\left\{\frac{2l}{P}\right\}-\left\{\frac{k+l}{P}\right\}-\left\{\frac{k}{P}\right\}-\left\{\frac{l}{P}\right\} \leq 0. \tag{5}$$