Identity for convolution of central binomial coefficients: \sum\limits_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=2^{2n}\sum\limits_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=2^{2n}

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.


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:

The problem of giving a combinatorial proof was raised by P. Veress and solved by G. Hajos in the 1930s. A recent proof appears in D.J. Kleitman, Studies in Applied Math. 54 (1975), 289 – 292. See also M. Sved, Math. Intelligencer, vol.6, no. 4 (1984), 44-45.

But I have not looked to check which article gives the proof I have outlined above.

Source : Link , Question Author : Skatche , Answer Author : Phira

Leave a Comment