Computing the binomial sum $\sum_{0\le i<j\le n}j\binom ni$

Question

Find the sum $$\sum_{0\le i<j\le n}j\binom ni.$$

My 1st attempt: replacing $j$ with $n-j$. So the expression turns out to be $$S=\sum n\binom ni-\sum j\binom ni$$ So adding the original and the final expression we get simply $S=n2^{n-1}$.

My second attempt: considering 3 parts:

Part 1: $i=j$, $\sum_{i=j}i\binom ni= n2^{n-1}$

Part 2: $i<j$ and $i>j$ they are equivalent, so we get $2S$

Part 3 : taking $i\in[0..n]$ and $j=[0..n]$ which gives $\frac{n(n+1)}22^n$

Combining all the parts I get $n^22^{n-2}$.

But none of my answers match with the given answer.

Answer 1

\begin{align} \sum_{0 \le i<j\le n} j \binom{n}{i} &= \sum_{i=0}^n \sum_{j=i+1}^n j \binom{n}{i}\\ &= \sum_{i=0}^n \binom{n}{i} \sum_{j=i+1}^n j \\ &= \sum_{i=0}^n \binom{n}{i} \frac{(n+i+1)(n-i)}{2} \\ &= \frac{1}{2}\sum_i \binom{n}{i} (n^2+n-i(i-1)-2i) \\ &= \frac{1}{2}(n^2+n)\sum_i \binom{n}{i} -\frac{1}{2}\sum_i \binom{n}{i} i(i-1)-\sum_i \binom{n}{i} i \\ &= \frac{1}{2}(n^2+n)\sum_i \binom{n}{i} -\frac{1}{2}n(n-1)\sum_i \binom{n-2}{i-2}-n\sum_i \binom{n-1}{i-1} \\ &= \frac{1}{2}(n^2+n)2^n -\frac{1}{2}n(n-1)2^{n-2}-n 2^{n-1} \\ &= (3n^2+n)2^{n-3} \end{align}

Answer 2

You cannot simply swap $j$ with $j$ and claim later that the sum on the right is the same as the one you started with, because $i<j$. You can rewrite the sum as: $$\sum_{i=0}^n\sum_{j=i+1}^n j{n \choose i}=\sum_{i=0}^n{n \choose i}\sum_{j=i+1}^n j=\sum_{i=0}^n\frac{(n-i)(n+i+1)}{2}{n \choose i}$$ Which you can disassemble into the sums of the form: \begin{align} \sum_{i=0}^n{n \choose i}&=2^n\\ \sum_{i=0}^n i{n \choose i}&=n 2^{n-1}\\ \sum_{i=0}^n i^2{n \choose i}&=n (n+1) 2^{n-2} \end{align}