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

Find the sum $$\sum_{0\le i

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 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}$$.

• re your 1st attempt, if i am interpreting it correctly, if i=4,j=8,n=10, then (n-j) is not between i and n. if this is not on point, please explain what you are doing in your 1st attempt. – user2661923 Apr 6 at 3:54
• Thanks a lot for editing – Alex Apr 6 at 6:18

\begin{align} \sum_{0 \le i
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. 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}
• Again, there are no three cases, there is only one and it is $i<j$ as it is said under a summarion sign – Bartek Apr 6 at 9:33