Closed form for $\sum_{k=0}^{n} k \sum_{j=0}^k {n \choose j}$

Question

Closed form for $$S=\sum_{k=0}^{n} k \sum_{j=0}^k {n \choose j}$$ becomes interesting because we do not know the $j$-sum but on the other hand we can simply expand $S$ as $$S=\sum_{k=0}^n f_k {n \choose k},$$ where $f_k$ is like frequency of $k$-th binomial coefficient. The question is what could be the closed form for $S$ with proof?

Answer 1

You have :

$$S = \sum_{k=0}^n k \sum_{j=0}^k {n \choose j} = \sum_{j=0}^n \sum_{k=j}^n k {n \choose j} = \sum_{j=0}^n {n \choose j}\sum_{k=j}^n k = \sum_{j=0}^n {n \choose j} \left[ \frac{n(n+1)}{2} - \frac{(j-1)j}{2}\right]$$ $$=\frac{n(n+1)}{2} 2^n - \frac{1}{2}\sum_{j=0}^n j(j-1) {n \choose j} = n(n+1) 2^{n-1} - n(n-1)2^{n-3}$$ $$=2^{n-3} \left( -n(n-1) + 4n(n+1)\right) = 2^{n-3} \left( 3n^2 + 5n\right)$$