Prove that $\sum\limits_{k}\sum\limits_{i\le k}\binom{n}{i}\cdot\sum\limits_{j>k}\binom{n}{j}=\frac{n}{2}\binom{2n}{n}$

Question

Question:

show that

$$\sum_{k=0}^{n-1}\left(\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{k}\right)\left(\binom{n}{k+1}+\cdots+\binom{n}{n}\right)=\dfrac{n}{2}\binom{2n}{n}$$

My idea: let $$a_{k}=\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{k},b_{k}=\binom{n}{k+1}+\cdots+\binom{n}{n}$$

so use Abel identity $$\sum_{k=0}^{n-1}a_{k}b_{k}=S_{n-1}b_{n-1}+\sum_{k=1}^{n-2}S_{k}[b_{k}-b_{k+1}]$$ where $$S_{n}=a_{1}+a_{2}+\cdots+a_{n}$$

then I can't continue,becase I can't how to deal the $S_{k}[b_{k}-b_{k+1}]$

Answer 1

A general principle in such contexts is to try to get rid of the limits of the sums and that, to do so, indicator functions are exquisitely tailored.

In the present case, using the convention that ${k\choose i}=0$ for every integers $(k,i)$ except when $k$ and $i$ are two nonnegative integers such that $k\geqslant i$ (and then ${k\choose i}$ is the usual binomial coefficient, of course), one sees that the LHS of the question is $$S_n=\sum_k\sum_{i\leqslant k}{n\choose i}\sum_{j\gt k}{n\choose j}=\sum_{k,i,j}{n\choose i}{n\choose j}\mathbf 1_{i\leqslant k\lt j}.$$ The RHS above is a triple sum without delimiters (a sum on $\mathbb Z^3$, if you like) hence we can start to work on it.

For each $i\lt j$ there are $j-i$ integers $k$ such that $i\leqslant k\lt j$ hence $$S_n=\sum_{i,j}(j-i){n\choose i}{n\choose j}\mathbf 1_{i\lt j}=U_n-V_n,$$ with $$U_n=\sum_{i,j}j{n\choose i}{n\choose j}\mathbf 1_{i\lt j},\qquad V_n=\sum_{i,j}i{n\choose i}{n\choose j}\mathbf 1_{i\lt j}.$$ Using the identity $j{n\choose j}=n{n-1\choose j-1}$ and the change of variable $j\to j-1$ in the first sum and the identity $i{n\choose j}=n{n-1\choose i-1}$ and the change of variable $i\to i-1$ in the second sum, one gets $$U_n=n\sum_{i,j}{n\choose i}{n-1\choose j}\mathbf 1_{i\leqslant j},\qquad V_n=n\sum_{i,j}{n-1\choose i}{n\choose j}\mathbf 1_{i\lt j-1}.$$ The change of variables $k=n-1-i$, $\ell=n-j$ in $V_n$ transforms the condition $i\lt j-1$ into $\ell\lt k$ hence $$ V_n=n\sum_{k,\ell}{n-1\choose n-1-k}{n\choose n-\ell}\mathbf 1_{\ell\lt k}=n\sum_{k,\ell}{n\choose \ell}{n-1\choose k}\mathbf 1_{\ell\lt k}.$$ Renaming $(\ell,k)$ as $(i,j)$ and comparing the RHS with $U_n$, one sees that all the terms in $U_n-V_n$ cancel except those such that $i=j$, thus, $$S_n=n\sum_{i}{n\choose i}{n-1\choose i}=n\sum_{i}{n\choose i}{n-1\choose n-1-i}.$$ The sum in the RHS is the coefficient of $x^{n-1}$ in the polynomial $$(1+x)^n\cdot(1+x)^{n-1}=(1+x)^{2n-1},$$ hence, finally, $$S_n=n\cdot{2n-1\choose n-1}=\frac12n\cdot{2n\choose n}.$$

Answer 2

$$ \begin{align} &\sum_{k=0}^n\left(\sum_{i=0}^k\binom{n}{i}\right)\left(\sum_{j=k+1}^n\binom{n}{j}\right)\tag{1}\\ &=\sum_{k=0}^n\sum_{i=0}^k\sum_{j=k+1}^n\binom{n}{i}\binom{n}{j}\tag{2}\\ &=\sum_{\substack{i,j=0\\i\lt j}}^n\sum_{k=i}^{j-1}\binom{n}{i}\binom{n}{j}\tag{3}\\ &=\sum_{\substack{i,j=0\\i\lt j}}^n(j-i)\binom{n}{i}\binom{n}{j}\tag{4}\\ &=n\sum_{\substack{i,j=0\\i\lt j}}^n\left[\binom{n}{i}\binom{n-1}{j-1}-\binom{n-1}{i-1}\binom{n}{j}\right]\tag{5}\\ &=n\sum_{\substack{i,j=0\\i\lt j}}^n\left[\binom{n-1}{i}\binom{n-1}{j-1}-\binom{n-1}{i-1}\binom{n-1}{j}\right]\tag{6}\\ &=n\sum_{\substack{i,j=0\\i\lt j}}^n\left[\binom{n-1}{i+1}\binom{n-1}{j}-\binom{n-1}{i-1}\binom{n-1}{j}\right]\tag{7}\\ &=n\sum_{j=0}^n\left[\binom{n-1}{j}\binom{n-1}{j}+\binom{n-1}{j-1}\binom{n-1}{j}\right]\tag{8}\\[6pt] &=n\left[\binom{2n-2}{n-1}+\binom{2n-2}{n-2}\right]\tag{9}\\[6pt] &=n\binom{2n-1}{n-1}\tag{10}\\[6pt] &=\frac n2\binom{2n}{n}\tag{11} \end{align} $$ Explanation:
$\:\ (2)$: distribute product over sum
$\:\ (3)$: change order of summation
$\:\ (4)$: evaluate sum in $k$
$\:\ (5)$: $k\binom{n\vphantom{1}}{k}=n\binom{n-1}{k-1}$
$\:\ (6)$: $\binom{n\vphantom{1}}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$ (Pascal recursion)
$\:\ (7)$: reindex the sum of the left term
$\:\ (8)$: telescoping sum
$\:\ (9)$: sum each term using Vandermonde's Identity
$(10)$: $\binom{n\vphantom{1}}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$ (Pascal recursion)
$(11)$: $n\binom{2n}{n}=2n\binom{2n-1}{n-1}$ ( similar to $(5)$ )

Answer 3

Suppose we seek to show that $$\sum_{k=0}^{n-1} \left(\sum_{q=0}^k {n\choose q}\right) \left(\sum_{q=k+1}^n {n\choose q}\right) = \frac{1}{2} n {2n\choose n}.$$

Using the integral representation $${n\choose q} = {n\choose n-q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n-q+1}} \; dz$$

we get for the first factor $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n+1}} \sum_{q=0}^k z^q \; dz = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n+1}} \frac{1-z^{k+1}}{1-z} \; dz \\ = 2^n - \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n+1}} \frac{z^{k+1}}{1-z} \; dz$$

and for the second factor $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n+1}} \frac{z^{k+1}-z^{n+1}}{1-z} \; dz = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n+1}} \frac{z^{k+1}}{1-z} \; dz.$$

These add to $2^n$ as they obviously should.

Summing from $k=0$ to $n-1$ we get a positive and a negative piece. The positive piece is

$$2^n \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n}} \sum_{k=0}^{n-1} \frac{z^{k}}{1-z} \; dz \\ = 2^n \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n}} \frac{1-z^n}{(1-z)^2} \; dz \\ = 2^n \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n}} \frac{1}{(1-z)^2} \; dz.$$

The negative piece is $$\frac{1}{2\pi i} \int_{|z_1|=\epsilon} \frac{(1+z_1)^n}{z_1^{n}(1-z_1)} \frac{1}{2\pi i} \int_{|z_2|=\epsilon} \frac{(1+z_2)^n}{z_2^{n}(1-z_2)} \sum_{k=0}^{n-1} z_1^k z_2^k \; dz_2 \; dz_1 \\ = \frac{1}{2\pi i} \int_{|z_1|=\epsilon} \frac{(1+z_1)^n}{z_1^{n}(1-z_1)} \frac{1}{2\pi i} \int_{|z_2|=\epsilon} \frac{(1+z_2)^n}{z_2^{n}(1-z_2)} \frac{1-z_1^n z_2^n}{1-z_1z_2} \; dz_2 \; dz_1 \\ = \frac{1}{2\pi i} \int_{|z_1|=\epsilon} \frac{(1+z_1)^n}{z_1^{n}(1-z_1)} \frac{1}{2\pi i} \int_{|z_2|=\epsilon} \frac{(1+z_2)^n}{z_2^{n}(1-z_2)} \frac{1}{1-z_1z_2} \; dz_2 \; dz_1.$$

We evaluate the inner integral by taking the sum of the negatives of the residues of the poles at $z_2=1$ and $z_2=1/z_1$ instead of computing the residue of the pole at zero by using the fact that the residues sum to zero.

Re-write the integral as follows. $$\frac{1}{2\pi i} \int_{|z_2|=\epsilon} \frac{(1+z_2)^n}{z_2^{n}(z_2-1)} \frac{1}{z_1z_2-1} \; dz_2 \\ = \frac{1}{z_1} \frac{1}{2\pi i} \int_{|z_2|=\epsilon} \frac{(1+z_2)^n}{z_2^{n}(z_2-1)} \frac{1}{z_2-1/z_1} \; dz_2.$$

Now the negative of the residue at $z_2 = 1$ is $$-\frac{1}{z_1} 2^n \frac{1}{1-1/z_1} = 2^n \frac{1}{1-z_1}.$$

Substituting this into the outer integral we get $$2^n\frac{1}{2\pi i} \int_{|z_1|=\epsilon} \frac{(1+z_1)^n}{z_1^{n}(1-z_1)^2} \; dz_1.$$

We see that this piece precisely cancels the positive piece that we obtained first.

Continuing the negative of the residue at $z_2 = 1/z_1$ is $$-\frac{1}{z_1} \frac{(1+1/z_1)^n}{1/z_1^n \times (1/z_1-1)} = -\frac{1}{z_1} \frac{(1+z_1)^n}{(1/z_1-1)} = - \frac{(1+z_1)^n}{(1-z_1)}.$$

We now substitute this into the outer integral flipping the sign because this was the negative piece to get $$\frac{1}{2\pi i} \int_{|z_1|=\epsilon} \frac{(1+z_1)^{2n}}{z_1^{n}(1-z_1)^2} \; dz_1.$$

Extracting the residue at $z_1=0$ we get $$\sum_{q=0}^{n-1} {2n\choose n-1-q} (q+1) = \sum_{q=0}^{n-1} {2n\choose n+q+1} (q+1) \\ = - n \sum_{q=0}^{n-1} {2n\choose n+q+1} + \sum_{q=0}^{n-1} {2n\choose n+q+1} (n+q+1) \\ = -n \left(\frac{1}{2} 2^{2n} - \frac{1}{2} {2n\choose n}\right) + 2n \sum_{q=0}^{n-1} {2n-1\choose n+q} \\ = -n \left(\frac{1}{2} 2^{2n} - \frac{1}{2} {2n\choose n}\right) + 2n \frac{1}{2} 2^{2n-1} \\ = \frac{1}{2} n {2n\choose n}.$$

Remark. If we want to do this properly we also need to verify that the residue at infinity of the inner integral is zero. We use the formula for the residue at infinity

$$\mathrm{Res}_{z=\infty} h(z) = \mathrm{Res}_{z=0} \left[-\frac{1}{z^2} h\left(\frac{1}{z}\right)\right]$$

which in the present case gives for the inner term in $z_2$ $$- \mathrm{Res}_{z_2=0} \frac{1}{z_2^2} \frac{(1+1/z_2)^n}{1/z_2^n \times (1-1/z_2)} \frac{1}{1-z_1/z_2} \\ = - \mathrm{Res}_{z_2=0} \frac{1}{z_2^2} \frac{(1+z_2)^n}{(1-1/z_2)} \frac{1}{1-z_1/z_2} \\ = - \mathrm{Res}_{z_2=0} \frac{(1+z_2)^n}{(z_2-1)} \frac{1}{z_2-z_1}$$ which is zero by inspection.