# Direct combinatorial proof that $2^{2k} = \sum \binom{2i}{i}\binom{2j}{j}$?

In a purely algebraic way, I've just stumbled onto the fact that

$$2^{2k} = \sum_{i+j=k} \binom{2i}{i}\binom{2j}{j},$$

i.e. that the self-convolution of the sequence $\binom{2k}{k}$ is the sequence $2^{2k}$. This is the type of identity for which I would expect there to be a beautiful, simple, direct, and probably well-known combinatorial argument. I just spent some time looking for it but couldn't find it.

Is there a direct combinatorial proof of the above?

Geometric remark: such an argument would partition the vertices of an even-dimensional hypercube into some sort of combinatorially meaningful classes of size $\binom{2i}{i}\binom{2j}{j}$. For example, for $k=2$, the vertices of the $4$-cube would be partitioned into classes of size $6=1\cdot 6$, $4=2\cdot 2$, and $6=6\cdot 1$.

• mathoverflow.net/questions/206967/bit-string-bijection/… – Gjergji Zaimi Apr 8 '17 at 20:59
• Writing $\binom{2n}{n} = \binom{-\frac{1}{2}}{n}(-4)^n$, this becomes an instance of Vandermonde's identity $\sum_{i+j = k} \binom{\alpha}{i} \binom{\beta}{j} = \binom{\alpha+\beta}{k}$ with $\alpha = \beta = -\frac{1}{2}$. Vandermonde's Identity admits combinatorial proofs for integer $\alpha, \beta$. – Ofir Gorodetsky Apr 8 '17 at 21:20

Yes, this has an elementary combinatorial interpretation, because $${2i \choose i} 2^{-2i} {2j\choose j}2^{-2j}$$ (for $i+j=k$) is the probability that the time of the last return to the starting point of a random walk of length $2k$ equals $2i$. This takes some work to show, but is completely elementary; see for example Theorem 3.1 of my (undergraduate level) notes on random walks (I should also add that this material is taken straight from Feller's book).
Now your identity is an immediate consequence because after division by $2^{-2k}$ the RHS computes the probability that the last return time equals something.