5
$\begingroup$

I'm looking for a clean expression of the following combinatorial sum :

$$\sum\limits_{k=0}^{n}\frac{{n \choose k}^2}{{{2n} \choose {2k}}}$$ I recall being told it does have a neat expression.

However, I'm not familiar with combinatorics or anything related to evaluating non trivial finite sums such as this, so I basically lack methods to tacke this.

Any insight would be great !

$\endgroup$
10
$\begingroup$

We can simplify it a bit by rearranging the factorials: $$ \frac{\binom nk^2}{\binom{2n}{2k}} = \frac{\frac{n!\,n!}{k!\,k!\,(n-k)!\,(n-k)!}}{\frac{(2n)!}{(2k)!\,(2n-2k)!}} = \frac{n!\,n!}{(2n)!} \cdot \frac{(2k)!}{k!\,k!} \cdot \frac{(2n-2k)!}{(n-k)!\,(n-k)!} = \frac{\binom{2k}{k} \binom{2(n-k)}{n-k}}{\binom{2n}{n}}. $$ So this allows us to factor out a term that does not depend on $n$: $$ \sum_{k=0}^n \frac{\binom nk^2}{\binom{2n}{2k}} = \frac{1}{\binom{2n}{n}} \sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}. $$ The sum that's left simplifies nicely using generating functions, though I'm not aware of a good way to do it that avoids them. If we start with the identity $$ \frac1{\sqrt{1-4x}} = \sum_{i \ge 0} \binom{2i}{i} x^i $$ then we can conclude that the coefficient of $x^n$ in the square of $\frac{1}{\sqrt{1-4x}}$ is precisely the sum we want: the sum as $k$ goes from $0$ to $n$ represents the coefficient of $x^k$ taken from one factor times the coefficient of $x^{n-k}$ taken from the other. But the coefficient of $x^n$ in $\frac{1}{1-4x}$ is just $4^n$: it's a geometric series. So we conclude that $$ \sum_{k=0}^n \frac{\binom nk^2}{\binom{2n}{2k}} = \frac{1}{\binom{2n}{n}} \sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k} = \frac{4^n}{\binom{2n}{n}}. $$

$\endgroup$
  • $\begingroup$ Thank you, neat proof ! $\endgroup$ – Harmonic Sun Sep 1 '18 at 14:03
  • $\begingroup$ Nice solution! I have added an answer avoiding the generating function approach. $\endgroup$ – tarit goswami Sep 1 '18 at 14:14
5
$\begingroup$

For first part using the same way of rearranging as @MishaLavrov have done: $$\frac{\binom nk^2}{\binom{2n}{2k}} = \frac{\frac{n!\,n!}{k!\,k!\,(n-k)!\,(n-k)!}}{\frac{(2n)!}{(2k)!\,(2n-2k)!}} = \frac{n!\,n!}{(2n)!} \cdot \frac{(2k)!}{k!\,k!} \cdot \frac{(2n-2k)!}{(n-k)!\,(n-k)!} = \frac{\binom{2k}{k} \binom{2(n-k)}{n-k}}{\binom{2n}{n}}.$$

The motivation behind doing this was to get a good form, means to make the denominator constant for a constant $n$, so that dealing with the sum can be made easier. Now, to avoid the way of using generating functions to get the sum, I will use combinatorial argument. Let's concentrate on the sum $$\sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}$$ Argument:

For specific group, composed of $2n$ people, they'll choose $k$ boys and $(n-k)$ girls. To choose such people, group will be divided to $2k$ people group and $2(n-k)$ people group, each for boy and girl. Find the number of cases satisfying the condition(group composed of same people will be considered the same group no matter to the order). Then we can do the problem's statement as following: first, choose $k$ boys and $(n-k)$ girls. second, choose $k$ boys dropouts and $n-k$ girls dropouts. Each doesn't interfere other's case so the formula comes out to be $(\sum_{k=0}^{n})\binom{n}{k})^2$, which is $4^n$.

Hence, our required sum: $$\frac{1}{\binom{2n}{n}} \sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=\frac{4^n}{\binom{2n}{n}}.$$

$\endgroup$
  • 1
    $\begingroup$ Wow nice one, I didn't think it was possible to sum it with a purely combinatorial argument ! $\endgroup$ – Harmonic Sun Sep 1 '18 at 14:46
  • $\begingroup$ @HarmonicSun Yeah, it is a way. You need to develop a situation cleverly, and count the number of such arrangements in two different way. As, no. of such case doesn't matter in which way you have counted, you can relate a form of a binomial expression with another. $\endgroup$ – tarit goswami Sep 1 '18 at 17:19

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.