Prove that $\Sigma_{i=0}^{n-1} (\Sigma_{j=i+1}^n(j(^nC_i) + i(^nC_j))) = n^22^{n-1}$

Question

I have tried setting $$P=\Sigma_{i=0}^{n-1} (\Sigma_{j=i+1}^n(j(^nC_i) + i(^nC_j))$$ then $$P=\Sigma_{i=0}^{n-1} (\Sigma_{j=i+1}^n((n-j)(^nC_i) + (n-i)(^nC_j))$$ now adding them both $$2P=\Sigma_{i=0}^{n-1} (\Sigma_{j=i+1}^n(n((^nC_i)+(^nC_j))))$$ I think that we have to go ahead from here but I'm not able to think of anything else. Am I even on the right path? Please Help. Thanks!

Answer 1

We obtain \begin{align*} \color{blue}{\sum_{i=0}^{n-1}}&\color{blue}{\sum_{j=i+1}^n\left(j\binom{n}{i}+i\binom{n}{j}\right)}\\ &=\sum_{0\leq i<j\leq n}\left(j\binom{n}{i}+i\binom{n}{j}\right)\tag{1}\\ &=\sum_{0\leq i\ne j\leq n}i\binom{n}{j}\tag{2}\\ &=\sum_{0\leq i,j\leq n}i\binom{n}{j}-\sum_{0\leq i=j\leq n}i\binom{n}{j}\\ &=\left(\sum_{i=0}^ni\right)\left(\sum_{j=0}^n\binom{n}{j}\right)-\sum_{i=0}^ni\binom{n}{i}\tag{3}\\ &=\frac{1}{2}n(n+1)2^n-n\sum_{i=1}^n\binom{n-1}{i-1}\tag{4}\\ &=\frac{1}{2}n(n+1)2^n-n\sum_{i=0}^{n-1}\binom{n-1}{i}\tag{5}\\ &=\frac{1}{2}n(n+1)2^n-n2^{n-1}\\ &\,\,\color{blue}{=n^22^{n-1}} \end{align*} and the claim follows.

Comment:

• In (1) we write the index region somewhat more conveniently to better see what's going on.

• in (2) we use the symmetry of the index region and the summands.

• In (3) we can write the sums separating the indices $i$ and $j$.

• In (4) we simplify using closed forms and apply the binomial identity $\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}$.

• In (5) we shift the index to start with $i=0$ and use again a closed form expression as in (4).

Answer 2

I'm going ahead and assume $^nC_i=\binom{n}{i}$ and so $$2P=n\sum_{i=0}^n \sum_{j=i+1}^n \left( \binom{n}{i} + \binom{n}{j} \right) = n\sum_{i=0}^n (n-i)\binom{n}{i} + n\sum_{j=0}^n\sum_{i=0}^{j-1} \binom{n}{j} =n^2\sum_{i=0}^{n} \binom{n}{i}=n^2 2^n$$