A tricky combinatorial sum

Question

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 !

Answer 1

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

Answer 2

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