Problem in Double Summation 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.
 A: 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).
A: 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]$$
A: 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.
