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

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.

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}$$
• @Maman: a combinatorial proof comes from considering that $\binom{2k}{k}\binom{2l}{l}$ is the number of paths in a $(k+l)\times(k+l)$ grid that goes from $(0;0)$ to $(k+l;k+l)$ by travelling towards north or east, and passing through the point $(k;k)$. – Jack D'Aurizio Aug 31 '16 at 17:00
• If you are able to put an equivalence relation over this set of paths, in such a way that every equivalence class has $\binom{k+l}{l}$ elements, you are done. – Jack D'Aurizio Aug 31 '16 at 17:01