Evaluate using combinatorial argument or otherwise :$\sum_{i=0}^{n-1}\sum_{j=i+1}^{n}\left(j\binom{n}{i}+i\binom{n}{j}\right)$

Question

Evaluate using combinatorial argument or otherwise $$\sum_{i=0}^{n-1}\sum_{j=i+1}^{n}\left(j\binom{n}{i}+i\binom{n}{j}\right)$$ My Attempt

By plugging in values of $i=0,1,2,3$ I could observe that this double summation is nothing but $$\left(1+2+3+...+n\right)\left(\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+...+\binom{n}{n}\right)-\left(1\binom{n}{1}+2\binom{n}{2}+...+n\binom{n}{n}\right)$$which simplifies to $$\frac{n(n+1)}{2}.2^n-n.2^{n-1}=n^22^{n-1}$$ which is indeed the answer.

But I am having problem to do this summation by combinatorial argument.

$$\sum_{i=0}^{n-1}\sum_{j=i+1}^{n}\left(j\binom{n}{i}+i\binom{n}{j}\right)=\sum_{i=0}^{n-1}\sum_{j=i+1}^{n}\left(\binom{n}{i}\binom{j}{1}+\binom{n}{j}\binom{i}{1}\right)$$

That is as far as I could go.

Answer 1

More generally, note that $$\sum_{i,j: i<j} (a_{ij} + a_{ji}) = \sum_{i,j: i < j} a_{ij} + \sum_{i,j: i > j} a_{ij} = \sum_{i,j: i\not= j} a_{ij} = \sum_{i,j} a_{ij} - \sum_i a_{ii}.$$ Taking $a_{ij}=j\binom{n}{i}$ yields \begin{align} \sum_{i,j: i<j} \left(j\binom{n}{i} + i\binom{n}{j}\right) &= \sum_{i=0}^n \sum_{j=0}^n j\binom{n}{i} - \sum_{i=0}^n i\binom{n}{i} \\ &= \sum_{j=1}^n j \sum_{i=0}^n \binom{n}{i} - \sum_{i=1}^n i\binom{n}{i} \\ &= \sum_{j=1}^n j 2^n - n\sum_{i=1}^n \binom{n-1}{i-1} \\ &= \frac{n(n+1)}{2} 2^n - n2^{n-1} \\ &= n^2 2^{n-1}. \end{align}

---

For a combinatorial interpretation of $$\sum_{i,j: i\not= j} j\binom{n}{i} = n^2 2^{n-1},$$ maybe consider committees with a chair and vice chair (different from the chair) chosen from people $\{0,1,\dots,n\}$, subject to the restriction that $0$ cannot be the chair. The RHS is clear. For the LHS, $j$ could represent the larger of the chair and vice chair, leaving $j$ choices $\{0,1\dots,j-1\}$ for the smaller of the two, and $i$ could represent the number of members chosen from among $\{1,2,\dots,n\}$.

Answer 2

Here's an analytical way. There are probably simpler ones.

$\begin{array}\\ a(n) &=\sum_{i=0}^{n-1}\sum_{j=i+1}^{n}\left(j\binom{n}{i}+i\binom{n}{j}\right)\\ &=\sum_{i=0}^{n-1}\sum_{j=i+1}^{n}j\binom{n}{i}+\sum_{i=0}^{n-1}\sum_{j=i+1}^{n}i\binom{n}{j}\\ &=b(n)+c(n)\\ b(n) &=\sum_{i=0}^{n-1}\sum_{j=i+1}^{n}j\binom{n}{i}\\ &=\sum_{i=0}^{n-1}\binom{n}{i}\sum_{j=i+1}^{n}j\\ c(n) &=\sum_{i=0}^{n-1}\sum_{j=i+1}^{n}i\binom{n}{j}\\ &=\sum_{j=0}^{n}\sum_{i=0}^{j-1}i\binom{n}{j}\\ &=\sum_{j=0}^{n}\binom{n}{j}\sum_{i=0}^{j-1}i\\ &=\sum_{i=0}^{n}\binom{n}{i}\sum_{j=0}^{i-1}j \qquad \text{(swap } i \text{ and } j)\\ b(n)+c(n) &=\sum_{i=0}^{n-1}\binom{n}{i}\sum_{j=i+1}^{n}j+\sum_{i=0}^{n}\binom{n}{i}\sum_{j=0}^{i-1}j\\ &=\sum_{i=0}^{n}\binom{n}{i}\sum_{j=i+1}^{n}j+\sum_{i=0}^{n}\binom{n}{i}\sum_{j=0}^{i-1}j\\ &=\sum_{i=0}^{n}\binom{n}{i}(\sum_{j=i+1}^{n}j+\sum_{j=0}^{i-1}j)\\ &=\sum_{i=0}^{n}\binom{n}{i}(\sum_{j=0}^{n}j-i)\\ &=\dfrac{n(n+1)}{2}\sum_{i=0}^{n}\binom{n}{i}-\sum_{i=0}^{n}i\binom{n}{i})\\ &=\dfrac{n(n+1)}{2}2^n-n2^{n-1}\\ &=n2^{n-1}(n+1-1)\\ &=n^22^{n-1}\\ \end{array} $

Answer 3

Reindex the double sum as a product of two single sums minus diagonal terms: $$\sum_{0\le i,j\le n,i\ne j}i\binom nj=\sum_{0\le i,j\le n}i\binom nj-\sum_{i=0}^ni\binom ni$$ $$=\left(\sum_{i=0}^ni\right)\left(\sum_{j=0}^n\binom nj\right)-\sum_{i=0}^ni\binom ni$$ $$=\frac{n(n+1)}2\cdot2^n-\sum_{i=0}^ni\binom ni$$ This last sum is well-known to be $n2^{n-1}$ (and can be proved combinatorially), so the answer is $$n(n+1)2^{n-1}-n2^{n-1}=n^22^{n-1}$$