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

| cite | improve this answer | |
  • $\begingroup$ Thank you, but is there another elementary method without valuation ? $\endgroup$ – Maman Aug 31 '16 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$ – Jack D'Aurizio Aug 31 '16 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$ – Jack D'Aurizio Aug 31 '16 at 17:01
  • $\begingroup$ @JackD'Aurizio Did you have an equivalence relation in mind? $\endgroup$ – arctic tern Sep 1 '16 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$ – 6005 Sep 2 '16 at 1:05

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.