Proof of a combinatorial identity: $\sum\limits_{i=0}^n {2i \choose i}{2(n-i)\choose n-i} = 4^n$ [duplicate]

Possible Duplicate:
Identity involving binomial coefficients

This was part of a homework assignment that I had, and I couldn't figure it out. Now it is bugging me. Can anyone help me? Although a proof would be nice, I wouldn't mind a push in the right direction.

$\displaystyle\sum_{i=0}^n {2i \choose i}{2(n-i)\choose n-i} = 4^n$

Solution 1:

Added: I have at long last got around to correcting the proof of the crucial lemma.

Here’s a purely combinatorial argument.

Let $\Sigma_{2n}$ be the set of binary strings (strings of $0$’s and $1$’s) of length $2n$. Call a binary string balanced if it contains the same number of $0$’s and $1$’s. Let $\Sigma_{2n}^B$ be the set of balanced members of $\Sigma_{2n}$, and let $\Sigma_{2n}^U$ be the set of unbalanced strings in $\Sigma_{2n}$ that have no balanced initial segment; I’ll call these completely unbalanced. Clearly $\left|\Sigma_{2n}^B\right|=\binom{2n}n$.

For $\sigma=\langle b_1,\dots,b_{2n}\rangle\in\Sigma_{2n}$ and $1\le i\le k\le 2n$ let $\sigma(i,k)=\langle b_i,\dots,b_k\rangle$, and let $e_\sigma(i,k)$ be the excess of $1$’s over $0$’s in $\sigma(i,k)$. Let $\sigma^R(i,k)=\langle b_k,\dots,b_i\rangle$, the reversal of $\sigma(i,k)$. Finally, let $\bar\sigma(i,k)=\langle \bar b_i,\dots,\bar b_k\rangle$, where $\bar b=1-b$ for $b\in\{0,1\}$. Note that $e_{\bar\sigma}(i,k)=-e_\sigma(i,k)$.

Lemma: $\left|\Sigma_{2n}^U\right|=\left|\Sigma_{2n}^B\right|$.

Corrected Proof: I’ll construct a bijection $\Sigma_{2n}^B\to\Sigma_{2n}^U:\sigma\mapsto\hat\sigma$.

Fix $\sigma=\langle b_1,\dots,b_{2n}\rangle\in\Sigma_{2n}^B$. Let $m=\min\{e_\sigma(1,k):k=1,\dots,2n\}\le 0$. If $m=0$, let $\tau=\sigma$. Otherwise, let $h$ be the smallest index such that $e_\sigma(1,h)=m$. Let $\tau=\sigma(h+1,2n)\bar\sigma^R(1,h)$. That is, $\tau$ is obtained from $\sigma$ by transferring the first $h$ bits to the end, reversing their order and complementing them in the process. Now $e_\sigma(1,2n)=0$, so $e_\sigma(h+1,2n)=-m$, and $$e_\tau(1,2n)=e_\sigma(h+1,2n)-e_\sigma(1,h)=-2m>0\;.$$ The choice of $h$ ensures that $e_\tau(1,k)=e_\sigma(h+1,h+k)\ge 0$ for $k=1,\dots,2n$. If $e_\tau(1,k)>0$ for $k=1,\dots,2n$, let $\hat\sigma=\tau\in\Sigma_{2n}^U$.

Otherwise, let $j$ be minimal such that $e_\tau(1,j)=0$. If $\tau=\langle c_1,\dots,c_{2n}\rangle$, then clearly $c_j=0$. Let $$\tau'=\langle c_1,\dots,c_{j-1},1,c_{j+1},\dots,c_{2n}\rangle\;;$$ then $e_{\tau'}(1,k)>0$ for $k=1,\dots,2n$. Finally, let $\hat\sigma=\overline{\tau'}$; $e_{\hat\sigma}(1,k)<0$ for $k=1,\dots,2n$, so $\hat\tau\in\Sigma_{2n}^U$.

Now fix $\sigma=\langle b_1,\dots,b_{2n}\rangle\in\Sigma_{2n}^U$. Suppose first that $e_\sigma(1,k)>0$ for $k=1,\dots,2n$. Note that $e_\sigma(1,2n)$ is even, and let $m=\frac12e_\sigma(1,2n)$. Let $h$ be the largest index such that $e_\sigma(1,h)=m$, and let $\tau=\bar\sigma^R(h+1,2n)\sigma(1,h)$. The choice of $h$ ensures that $e_\sigma(h+1,2n)=m$ and that $e_\sigma(h+1,k)>0$ for $k=h+1,\dots,2n$, so $e_\tau(1,2n-h)=-m$, and $e_\tau(k,2n-h)>-m$ for $k=1,\dots,2n-h$. Moreover, $e_\sigma(1,k)>0$ for $k=1,\dots,h$, so $e_\tau(1,h)=-m$ is the minimum of $e_\tau(1,k)$ for $k=1,\dots,2n$, and therefore $\sigma=\hat\tau$.

Now suppose that $e_\sigma(1,k)<0$ for $k=1,\dots,2n$; clearly $e_{\bar\sigma}(1,k)>0$ for $k=1,\dots,2n$. Let $j$ be the maximal index such that $\bar b_j=1$ and $e_{\bar\sigma}(1,j)=2$. Let $\sigma'$ be obtained from $\bar\sigma$ by replacing $\bar b_j$ by $0$. Then $e_{\sigma'}(1,k)>0$ for $k=1,\dots,j-1$, $e_{\sigma'}(1,j)=0$, and $e_{\sigma'}(1,k)\ge 0$ for $k=j,\dots,2n$. If $e_{\sigma'}(1,2n)=0$, let $\tau=\sigma'\in\Sigma_{2n}^B$, and observe that $\sigma=\hat\tau$. Otherwise, let $m=\frac12e_{\sigma'}(1,2n)$, and proceed as in the previous paragraph: take $h$ to be the largest index such that $e_{\sigma'}(1,h)=m$, and let $\tau=\overline{\sigma'}^R(h+1,2n)\sigma'(1,h)$. As before, $\sigma=\hat\tau$. The map $\sigma\mapsto\hat\sigma$ is therefore a bijection. $\dashv$

For $\sigma = \langle b_1,\dots,b_{2n}\rangle\in\Sigma_{2n}$ let $m(\sigma)$ be the largest $k$ such that $\langle b_1,\dots,b_{2k}\rangle$ is balanced, if such a $k$ exists; if not, let $m(\sigma)=0$. For $k=1,\dots,2n$ let $\Sigma_{2n}(k) = \{\sigma\in\Sigma_{2n}:m(\sigma)=k\}$. Then $\sigma\in\Sigma_{2n}$ belongs to $\Sigma_{2n}(k)$ iff $\langle b_1,\dots,b_{2k}\rangle$ is balanced, and $\langle b_{2k+1},\dots,b_{2n}\rangle$ is completely unbalanced. There are $\binom{2k}k$ balanced strings of length $2k$, and by the lemma there are $\binom{2(n-k)}{n-k}$ completely unbalanced strings of length $2n-2k$, so $$\left|\Sigma_{2n}(k)\right|=\binom{2k}{k}\binom{2(n-k)}{n-k}.$$ Clearly $\Sigma_{2n} = \bigcup\limits_{k=0}^n\Sigma_{2n}(k)$, where the sets $\Sigma_{2n}(k)$ are pairwise disjoint, so $$\left|\Sigma_{2n}\right| = \sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}.$$ But of course $|\Sigma_{2n}(k)| = 2^{2n} = 4^n$, so we have the desired result: $$\sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=4^n.$$

Solution 2:

Note that this is an autoconvolution (the convolution of a sequence with itself) of $\binom{2k}{k}$. We can determine that the generating function of $\binom{2k}{k}$ is

$$\sum_{k=0}^\infty \binom{2k}{k} x^k=\frac1{\sqrt{1-4x}}$$

The generating function of the autoconvolution is then obtained by squaring the original generating function. Thus you have to determine the coefficients of the function $\dfrac1{1-4x}$, which can be recast as a geometric series...