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

But none of my answers match with the given answer.

• 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

## 2 Answers

\begin{align} \sum_{0 \le i

• Yes I got it now thanks a lot for the answer – Alex Apr 6 at 6:21
• @RobPratt very nice. – user2661923 Apr 6 at 17:17
• @user2661923, thank you. – RobPratt Apr 6 at 17:23

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}

• i understood your method and Rob Pratt's method but in my second attempt where I am going wrong, I didn't get it. – Alex Apr 6 at 6:23
• I think probably i<j and i>j are not equivalent is it so? – Alex Apr 6 at 6:25
• Actually we often do this in binomial summation questions so I thought maybe it could be applied here too. – Alex Apr 6 at 6:26
• 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