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.

  • $\begingroup$ 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. $\endgroup$ – user2661923 Apr 6 at 3:54
  • $\begingroup$ Thanks a lot for editing $\endgroup$ – Alex Apr 6 at 6:18

\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}

| cite | improve this answer | |
  • $\begingroup$ Yes I got it now thanks a lot for the answer $\endgroup$ – Alex Apr 6 at 6:21
  • $\begingroup$ @RobPratt very nice. $\endgroup$ – user2661923 Apr 6 at 17:17
  • $\begingroup$ @user2661923, thank you. $\endgroup$ – 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<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}

| cite | improve this answer | |
  • $\begingroup$ i understood your method and Rob Pratt's method but in my second attempt where I am going wrong, I didn't get it. $\endgroup$ – Alex Apr 6 at 6:23
  • $\begingroup$ I think probably i<j and i>j are not equivalent is it so? $\endgroup$ – Alex Apr 6 at 6:25
  • $\begingroup$ Actually we often do this in binomial summation questions so I thought maybe it could be applied here too. $\endgroup$ – Alex Apr 6 at 6:26
  • $\begingroup$ Again, there are no three cases, there is only one and it is $i<j$ as it is said under a summarion sign $\endgroup$ – Bartek Apr 6 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.