An unusal feature of a usual double sum of product of two binomial coefficiens

Question

We know that

$$\sum_{0 \le i \le j \le n} A_i~ A_j= \frac{\left(\sum_{k=0}^{n} A_k\right) ^2+\sum_{k=0}^{n} A_k^2}{2}~~(1)$$ One can find $$ S= \sum_{0 \le i \le j < \infty} ~ 2^{-i-j}$$ using (1), we get $S=8/3$. We can also find $S$ as below: $$S=\sum_{j=0}^{\infty} 2^{-j} \sum_{i=0}^{j} 2^{-i}= \sum_{j=0}^{\infty} 2^{-j} \frac{(2)^{-j-1}-1}{2^{-1}-1} =2\sum_{j=0}^{\infty}[2^{-j}-(2)^{-2j-1}]=8/3.$$ Using (1). we usually get $$T=\sum_{0 \le i \le j \le n} {n \choose i} {n \choose j} = \frac{4^n+{2n \choose n}}{2}.$$ But we cannon get $T$ as $$ T =\sum_{j=0}^{n} {n \choose j} \sum_{i=0}^{j} {n \choose i},$$ because the second term is not doable in a closed form. Any help!

Answer 1

We use the coefficient of operator $[z^j]$ to denote the coefficient of $z^j$ in a series. This way we can write for instance \begin{align*} [z^j](1+z)^n=\binom{n}{j}\tag{1} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{j=0}^n}&\color{blue}{\binom{n}{j}\sum_{i=0}^j\binom{n}{i}}\\ &=\sum_{j=0}^n\binom{n}{j}\sum_{i=0}^j[z^i](1+z)^n\tag{2}\\ &=[z^0](1+z)^n\sum_{j=0}^n\binom{n}{j}\sum_{i=0}^jz^{-i}\tag{3}\\ &=[z^0](1+z)^n\sum_{j=0}^n\binom{n}{j}\frac{z^{-j-1}-1}{z^{-1}-1}\tag{4}\\ &=[z^0](1+z)^n\sum_{j=0}^n\binom{n}{j}\frac{z^{-j}-z}{1-z}\\ &=[z^0]\frac{(1+z)^n}{1-z}\left(\sum_{j=0}^n\binom{n}{j}z^{-j}-z\sum_{j=0}^n\binom{n}{j}\right)\\ &=[z^0]\frac{(1+z)^n}{1-z}\left(\left(1+\frac{1}{z}\right)^n-2^nz\right)\tag{5}\\ &=[z^n](1+z)^{2n}\sum_{j=0}^\infty z^j\tag{6}\\ &=\sum_{j=0}^n[z^j](1+z)^{2n}\\ &=\sum_{j=0}^n\binom{2n}{j}\\ &=\frac{1}{2}\left(\sum_{j=0}^{2n}\binom{2n}{j}+\binom{2n}{n}\right)\tag{7}\\ &\,\,\color{blue}{=\frac{1}{2}\left(4^n+\binom{2n}{n}\right)} \end{align*} and the claim follows.

Comment:

• In (2) we use the coefficient of operator according to (1).

• In (3) we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

• In (4) we use the finite geometric series formula.

• In (5) we apply the binomial theorem twice and observe the term $2^nz$ does not contribute to $[z^0]$.

• In (6) we factor out $\frac{1}{z^n}$ from $\left(1+\frac{1}{z}\right)^n$ and use again the rule as in (3). We also expand the geometric series.

• In (7) we use the symmetry $\binom{2n}{j}=\binom{2n}{2n-j}$ and compensate the factor $\frac{1}{2}$ of the middle term $\binom{2n}{n}$ by additionally adding it.