Problem in Double Summation

Question

While solving the following question from a book:

Prove that $$\mathop{\sum\sum}_{0\leq i<j\leq n}(i+j)\binom{n}{i}\binom{n}{j} = n\left(2^{2n-1}-\frac{1}{2} \binom{2n}{n}\right)$$

It is assumed in the solution provided by the book that

$$P = \mathop{\sum\sum}_{0\leq i<j\leq n}(i+j)\binom{n}{i}\binom{n}{j}$$

and then 'Replacing $i$ by $n-i$ and $j$ by $n-j$

$$P' = \mathop{\sum\sum}_{0\leq i<j\leq n}((n-i)+(n-j))\binom{n}{n-i}\binom{n}{n-j}$$

It is claimed that $P=P'$. I understand why in the argument $\dbinom{n}{i}\dbinom{n}{j}=\dbinom{n}{n-i}\dbinom{n}{n-j}$

But my questions are:

(i) Why $i$ is replaced by $n-i$ and $j$ by $n-j$? What's the intuition? (Apart from exploiting the identity $\dbinom{n}{i}=\dbinom{n}{n-i}$)

(ii) Why in the index, $i$ is not replaced by $n-i$ and $j$ by $n-j$?

(iii) Why is it claimed that $P=P'?$ I am not visualizing this clearly.

Answer 1

I can’t answer your first question without knowing how the argument proceeded after this point, but I can answer your second and third questions. Note that interchanging $i$ and $j$ in $P$ or $P'$ doesn’t change the sum; I’ll go through it in detail below, but this is what ultimately justifies the failure to replace $i$ and $j$ in the index by $n-i$ and $n-j$, respectively. That is,

$$P = \mathop{\sum\sum}_{0\leq i<j\leq n}(i+j)\binom{n}{i}\binom{n}{j}=\mathop{\sum\sum}_{0\leq j<i\leq n}(i+j)\binom{n}{i}\binom{n}{j}$$

(and similarly for $P'$), so

$$2P=\sum_{\substack{0\le i,j\le n\\i\ne j}}(i+j)\binom{n}i\binom{n}j\,,$$

which is symmetric in $i$ and $j$. This is simply the sum of all terms $(i+j)\binom{n}i\binom{n}j$ such that $0\le i,j\le n$ and $i\ne j$. If we let $k=n-i$ and $\ell=n-j$, so that $i=n-k$ and $j=n-\ell$, this becomes

$$2P=\sum_{\substack{0\le n-k,n-\ell\le n\\n-k\ne n-\ell}}\big((n-k)+(n-\ell)\big)\binom{n}{n-k}\binom{n}{n-\ell}\,.$$

But $0\le n-k,n-\ell\le n$ iff $0\le k,\ell\le n$, and $n-k\ne n-\ell$ iff $k\ne\ell$, so this is simply

$$2P=\sum_{\substack{0\le k,\ell\le n\\k\ne\ell}}\big((n-k)+(n-\ell)\big)\binom{n}{n-k}\binom{n}{n-\ell}\,.$$

Rename $k$ and $\ell$ as $i$ and $j$, respectively — a purely cosmetic change — and you get

$$2P=\sum_{\substack{0\le i,j\le n\\i\ne j}}\big((n-i)+(n-j)\big)\binom{n}{n-i}\binom{n}{n-j}=2P'$$

and hence $P=P'$. (It actually appears to me that it might be easier to work with $2P$ and prove that it’s equal to $n\left(2^{2n}-\binom{2n}n\right)$.)

Added: It’s actually not too hard to give a proof that is partly combinatorial and partly a straightforward computation using very standard identities (that themselves have easy combinatorial proofs). Start by observing that

$$\begin{align*} \sum_{0\le i,j\le n}(i+j)\binom{n}i\binom{n}j&=\sum_{0\le i,j\le n}\left(i\binom{n}i\binom{n}j+j\binom{n}i\binom{n}j\right)\\ &=2\sum_{0\le i,j\le n}i\binom{n}i\binom{n}j\,. \end{align*}$$

Now suppose that you have a pool of $n$ women and $n$ men, and you want to know in how many ways you can choose from it a committee (of any size) and appoint one of the women on the committee to be the chair. A committee of $i$ women and $j$ men can be chosen in $\binom{n}i\binom{n}j$ ways, and there are then $i$ ways to choose the chair; summing over all possible values of $i$ and $j$, we see that there are

$$\sum_{0\le i,j\le n}i\binom{n}i\binom{n}j$$

such committees. On the other hand, it’s clear that we could first pick any of the $n$ women to be the chair and then choose any subset of the remaining $2n-1$ people to fill out the committee, so

$$\sum_{0\le i,j\le n}i\binom{n}i\binom{n}j=n2^{2n-1}\;,$$

and

$$\sum_{0\le i,j\le n}(i+j)\binom{n}i\binom{n}j=n2^{2n}\,.$$

We saw above that

$$2P=\sum_{\substack{0\le i,j\le n\\i\ne j}}(i+j)\binom{n}i\binom{n}j=n2^{2n}-\sum_{i=0}^n2i\binom{n}i^2\,,$$

so

$$\begin{align*} P&=n2^{2n-1}-\sum_{i=0}^ni\binom{n}i^2\\ &=n2^{2n-1}-\sum_{i=0}^nn\binom{n-1}{i-1}\binom{n}i\\ &=n2^{2n-1}-n\sum_{i=0}^n\binom{n-1}{i-1}\binom{n}{n-i}\\ &\overset{*}=n2^{2n-1}-n\binom{2n-1}{n-1}\\ &=n2^{2n-1}-\frac{2n^2}{2n}\binom{2n-1}{n-1}\\ &=n\left(2^{2n-1}-\frac12\binom{2n}n\right)\,, \end{align*}$$

where the starred step uses the Vandermonde identity.

Answer 2

Proving that $$S=\mathop{\sum\sum}_{0\leq i<j\leq n}(i+j)\binom{n}{i}\binom{n}{j} = n\left(2^{2n-1}-\frac{1}{2} \binom{2n}{n}\right)$$ Let $$f(x)=\mathop{\sum\sum}_{0\leq i<j\leq n} x^{i+j} \binom{n}{i}\binom{n}{j}$$ Then $S=f'(1)$

Use $$\mathop{\sum\sum}_{0\leq i<j\leq n} A_i A_j= \frac{1}{2} \left[\left( \sum_{k=0}^{n} A_k \right)^2-\sum_{k=0}^n A^2_k \right]$$ $$f(x)=\frac{1}{2}[(1+x)^{2n}-~_2F_1[-n,-n;1;x^2]]$$ $$f'(x)=n(1+x)^{2n-1}-n^2x ~ ~_2F_1[-n+1,-n+1;2;x^2]$$ $$\implies S=f'(1)=n~2^{2n-1} -n^2~_2F_1[-n+1,-n+1;2;1]$$ $$\implies S=n 2^{2n-1}-n^2 \frac{{2n \choose n}}{2n}$$

For Hypergeometric function $~_2F_1$ see:

https://en.wikipedia.org/wiki/Hypergeometric_function#:~:text=In%20mathematics%2C%20the%20Gaussian%20or,ordinary%20differential%20equation%20(ODE).

Answer 3

A simpler way:

Proving that $$S=\mathop{\sum\sum}_{0\leq i<j\leq n}(i+j)\binom{n}{i}\binom{n}{j} = n\left(2^{2n-1}-\frac{1}{2} \binom{2n}{n}\right)$$

Change $i$ to $(n-i)$ and $j$ to$ (n-j)$ to get $$S=\mathop{\sum\sum}_{0\leq i<j\leq n}[(2n-(i+j)]\binom{n}{n-i}\binom{n}{n-j}=\mathop{\sum\sum}_{0\leq i<j\leq n}[2n-(i+j)]\binom{n}{i}\binom{n}{j}$$ $$\implies 2S=2n\mathop{\sum\sum}_{0\leq i<j\leq n}\binom{n}{i}\binom{n}{j} $$

Use $$\mathop{\sum\sum}_{0\leq i<j\leq n} A_i A_j= \frac{1}{2} \left[\left( \sum_{k=0}^{n} A_k \right)^2-\sum_{k=0}^n A^2_k \right]$$ $$\implies S=\frac{1}{2}\left[\left(\sum_{k=0}^{n} \binom{n}{k}\right)^2-\sum_{k=0}^n \binom{n}{k}^2 \right]$$ $$\implies S=\frac{n}{2}\left[2^{2n}-\binom{2n}{n}\right]$$