It's not difficult to show that
$$(1-z^2)^{-1/2}=\sum_{n=0}^\infty \binom{2n}{n}2^{-2n}z^{2n}$$
On the other hand, we have $(1-z^2)^{-1}=\sum z^{2n}$. Squaring the first power series and comparing terms gives us
$$\sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}2^{-2n}=1$$
that is,
$$\sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=2^{2n}$$
My question: is there a more direct, combinatorial proof of this identity? I've been racking my brains trying to come up with one but I'm not having much success.
Best Answer
It is possible to give a direct combinatorial proof, but it is quite difficult to find it.
One possibility is to use paths between points with integer coordinates and steps $(1,1)$ and $(1,-1)$.
1) $\binom{2n}{n}$ counts all paths from $(0,0)$ to $(2n,0)$.
2) $2^{2n}$ counts all paths starting from $(0,0)$ with $2n$ steps.
3) $\binom{2n}{n}$ counts all paths with $2n$ steps that never touch the $x$-axis again after the start. (This one is not obvious, but can be proved with a bijection.)
Now you can conclude that all paths are a concatenation of a path that returns a certain number of times to the $x$-axis and a path that never does.
Note that the main difficulty here was that the two binomial coefficients are interpreted differently.
Edited to add reference: In Richard P. Stanley: Enumerative Combinatorics Volume 1, Chapter 1, Solution to exercice 2c the following reference is given:
But I have not looked to check which article gives the proof I have outlined above.