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

Question

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

Answer 1

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.

Answer 2

An elementary proof.

From \begin{equation} \arcsin x=\sum_{\ell=0}^{\infty}\frac{1}{2^{2\ell}}\binom{2\ell}{\ell}\frac{x^{2\ell+1}}{2\ell+1}, \quad |x|<1, \end{equation} it follows that \begin{equation*} \frac{1}{2}\arcsin(2x)=\sum_{k=0}^{\infty}\frac{1}{2k+1}\binom{2k}{k}x^{2k+1},\quad |x|<\frac{1}{2} \end{equation*} and, by differentiation, \begin{equation*} \frac{1}{\sqrt{1-4x^2}\,}=\sum_{k=0}^{\infty}\binom{2k}{k}x^{2k},\quad |x|<\frac{1}{2}. \end{equation*} Squaring on both sides, using the geometric series expansion, and utilzing the Cauchy product of the multiplication of two power series yield \begin{equation*} \sum_{k=0}^\infty2^{2k}x^{2k}=\frac{1}{1-4x^2}=\Biggl[\sum_{k=0}^{\infty}\binom{2k}{k}x^{2k}\Biggr]^2 =\sum_{k=0}^\infty\Biggl[\sum_{i=0}^k\binom{2i}{i}\binom{2(k-i)}{k-i}\Biggr]x^{2k}, \quad |x|<\frac{1}{2}. \end{equation*} Equating the coefficients of $x^{2k}$ results in $$ \sum_{i=0}^k\binom{2i}{i}\binom{2(k-i)}{k-i} =\sum_{i+j=k}\binom{2i}{i}\binom{2j}{j} =2^{2k}, \quad k\ge0. $$

The idea of this elementary proof comes from the following paper

Feng Qi, Chao-Ping Chen, and Dongkyu Lim, Several identities containing central binomial coefficients and derived from series expansions of powers of the arcsine function, Results in Nonlinear Analysis 4 (2021), no. 1, 57--64; available online at https://doi.org/10.53006/rna.867047.

This elementary proof is simpler than the proof of Theorem 3.4 on page 232 in the following paper

Necdet Batır, Hakan Küçük, and Sezer Sorgun, Convolution identities involving the central binomial coefficients and Catalan numbers, Transactions on Combinatorics 10 (2021), no. 4, 225--238; available online at https://dx.doi.org/10.22108/toc.2021.127505.1821.