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 Answer 1


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

  • $\begingroup$ Thank you, but is there another elementary method without valuation ? $\endgroup$
    – Maman
    Aug 31, 2016 at 16:57
  • 4
    $\begingroup$ @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)$. $\endgroup$ Aug 31, 2016 at 17:00
  • $\begingroup$ 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. $\endgroup$ Aug 31, 2016 at 17:01
  • $\begingroup$ @JackD'Aurizio Did you have an equivalence relation in mind? $\endgroup$
    – anon
    Sep 1, 2016 at 23:28
  • $\begingroup$ @JackD'Aurizio Actually, I am curious about an equivalence relation too. I tried in my answer but I think it doesn't work, so I deleted it. $\endgroup$ Sep 2, 2016 at 1:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .