How to calculate $\sum_{k=1}^n \left(k \sum_{i=0}^{k-1} {n \choose i}\right)$ How do I calculate the following summation?
$$\sum_{k=1}^n \left[k \sum_{i=0}^{k-1} {n \choose i}\right]$$
 A: $\displaystyle\sum_{k=1}^n\left[\sum_{i=0}^{k-1} k{n\choose i}\right]=\sum_{i=0}^{n-1}\left[\sum_{k=i+1}^{n}k{n\choose i}\right]=\sum_{i=0}^{n-1}\left[{n\choose i}\sum_{k=i+1}^n k\right]=$
$\displaystyle = \sum_{i=0}^{n-1}{n\choose i} \left[\dfrac{n(n+1)}{2}-\dfrac{i(i+1)}{2}\right]=\dfrac{n(n+1)}{2}(2^{n}-1)-\sum_{i=0}^{n-1}\dfrac{i(i+1)}{2}{n\choose i}$
$\displaystyle =\dfrac{n(n+1)}{2}(2^{n}-1)-\sum_{i=0}^{n-1}\left[\dfrac{n(n-1)}{2}{n-2\choose i-2}+n{n-1\choose i-1}\right]$
$\displaystyle =\dfrac{n(n+1)}{2}(2^{n}-1)-\dfrac{n(n-1)}{2}(2^{n-2}-1)-n(2^{n-1}-1)$
$\displaystyle =n(3n+1).2^{n-3}$
A: We can do it by using generating functions:
Consider the g.f. for $\binom{n}{k}$
\begin{align*}
(1+x)^n = \sum_{k=0}^n \binom{n}{k} x^k
\end{align*}
and the sum of the coefficients can be given by
$$\frac{(1+x)^n-2^n\, x^{n+1}}{1-x} = \sum_{k=0}^n \sum_{i=0}^k \binom{n}{i} x^k$$
Differentiating both sides w.r.t $x$ and taking $\displaystyle \lim_{x\to 1}$ gives
$$\sum_{k=0}^n k\, \sum_{i=0}^k \binom{n}{i}  = 2^{n - 3} {\left(3 \, n + 5\right)} n$$
Hence,
\begin{align*}
\sum_{k=0}^n k\, \sum_{i=0}^{k-1} \binom{n}{i} &= \left(\sum_{k=0}^n k\, \sum_{i=0}^k \binom{n}{i}\right) - \left(\sum_{k=0}^n k\, \binom{n}{k}\right)\\\\
&=n {\left(3 \, n + 5\right)} \, 2^{n - 3}  - n\, 2^{n-1}\\\\
&= n {\left(3 \, n + 1\right)} \, 2^{n - 3}
\end{align*}
A: Hint 1: interchange the order of summation. 
Hint 2: do you know how to find $\sum i {n \choose i}$?
Hint 3: do you know how to find $\sum i(i-1) {n \choose i}$?
A: (Note: I have attempted to incorporate
OP's edit to the problem.)
$\begin{array}\\
\sum_{k=1}^n (k \sum_{i=0}^{k-1} {n \choose i})
&=\sum_{k=1}^n \sum_{i=0}^{k-1} (k {n \choose i})\\
&=\sum_{i=0}^{n-1} \sum_{k=i+1}^n (k {n \choose i})\\
&=\sum_{i=0}^{n-1} {n \choose i}\sum_{k=i+1}^n k \\
&=\sum_{i=0}^{n-1} {n \choose i}\left(\frac{n(n+1)}{2}-\frac{i(i+1)}{2}\right) \\
&=\frac{n(n+1)}{2}\sum_{i=0}^{n-1} {n \choose i}-\sum_{i=0}^{n-1} {n \choose i}\frac{i(i+1)}{2} \\
&= S-T\\
\end{array}
$
$S
=\frac{n(n+1)}{2}\sum_{i=0}^{n-1} {n \choose i}
=\frac{n(n+1)}{2}(\sum_{i=0}^{n} {n \choose i}-{n \choose n})
=\frac{n(n+1)}{2}(2^n-1)
$.
$T = \sum_{i=0}^{n-1} {n \choose i}\frac{i(i+1)}{2}$.
Consider $t_i = {n \choose i}\frac{i(i+1)}{2}$.
$t_0 = 0, t_1=n$.
For $i \ge 1$,
I would like to use the identity
${ n \choose m}{m \choose k}
={n \choose k}{n-k \choose m-k}
$.
$\begin{array}\\
t_i
&={n \choose i}\frac{i(i+1)}{2}\\
&={n \choose i}\left(\frac{i(i-1)}{2}+i\right)\\
&={n \choose i}({i \choose 2}+{i \choose 1})\\
&={n \choose i}{i \choose 2}+{n \choose i}{i \choose 1}\\
&={n \choose 2}{n-2 \choose i-2}+{n \choose 1}{n-1 \choose i-1}\\
\end{array}
$
$\begin{array}\\
T 
&= t_0+t_1+\sum_{i=2}^{n-1} t_i\\
&= n+\sum_{i=2}^{n-1} \left( {n \choose 2}{n-2 \choose i-2}+{n \choose 1}{n-1 \choose i-1}\right)\\
&= n+\sum_{i=2}^{n-1} {n \choose 2}{n-2 \choose i-2}+\sum_{i=2}^{n-1}{n \choose 1}{n-1 \choose i-1}\\
&= n+ {n \choose 2}\sum_{i=2}^{n-1}{n-2 \choose i-2}+{n \choose 1}\sum_{i=2}^{n-1}{n-1 \choose i-1}\\
&= n+ {n \choose 2}\sum_{i=0}^{n-3}{n-2 \choose i}+{n \choose 1}\sum_{i=1}^{n-1}{n-1 \choose i}\\
&= n+ {n \choose 2}\left(\sum_{i=0}^{n-2}{n-2 \choose i}-1\right)+{n \choose 1}\sum_{i=0}^{n-1}{n-1 \choose i}-1\\
&= n+ {n \choose 2}\left(2^{n-2}-1\right)+{n \choose 1}(2^{n-1}-1)\\
&= n+ \frac{n(n+1)}{ 2}\left(2^{n-2}-1\right)+n(2^{n-1}-1)\\
&=  \frac{n(n+1)}{ 2}\left(2^{n-2}-1\right)+n2^{n-1}\\
\end{array}
$
$\begin{array}\\
S-T
&=\frac{n(n+1)}{2}(2^n-1)-\left( \frac{n(n+1)}{ 2}\left(2^{n-2}-1\right)+n2^{n-1}\right)\\
&=2^{n-2}\left(2n(n+1)-\frac{n(n+1)}{ 2} -2n\right) -\frac{n(n+1)}{2}- \frac{n(n+1)}{ 2}\\
&=2^{n-2}\frac{3n(n+1)-4n}{ 2}-n(n+1)\\
&=2^{n-2}\frac{n(3n-1)}{ 2}-n(n+1)\\
\end{array}
$
As usual,
this was done off the top of my head,
so there is a good chance of error,
but it's late and I'm tired,
so I'll stop here.
All corrections will be appreciated.
A: Here is a  slightly different take on this that  emphasises the use of
formal power series.
Suppose we seek to evaluate
$$Q_n = \sum_{k=1}^n k \sum_{q=0}^{k-1} {n\choose q}.$$
We have $$\sum_{q=0}^n {n\choose q} z^q = (1+z)^n$$
and therefore
$$\sum_{q=0}^{k-1} {n\choose q}
= [z^{k-1}] \frac{1}{1-z} (1+z)^n$$
because multiplication by $1/(1-z)$ sums coefficients.

The sum now becomes
$$\sum_{k=1}^n k [z^{k-1}] \frac{1}{1-z} (1+z)^n
= \sum_{k=0}^{n-1} (k+1) [z^k] \frac{1}{1-z} (1+z)^n$$

Once more deploying multiplication by $1/(1-z)$ this is equivalent to
$$[z^{n-1}] \frac{1}{1-z}
\sum_{k=0}^{n-1} z^k (k+1) [z^k] \frac{1}{1-z} (1+z)^n.$$
The  operator  sequence  that   extracts  the  coefficient  on  $z^k$,
multiplies  by  $k+1$  and   thereafter  by  $z^k$  is  a  generalized
annihilated coefficient  extractor and represents  multiplication by
$z$  followed  by differentiation,  so  we  get
$$Q_n  = [z^{n-1}] \frac{1}{1-z}
\left(\frac{z}{1-z} (1+z)^n\right)'.$$
Actually computing the derivative we obtain
$$[z^{n-1}] \frac{1}{1-z}
\left(\frac{1}{(1-z)^2} (1+z)^n
+ \frac{z}{1-z} \times n \times (1+z)^{n-1}\right)$$
which is
$$[z^{n-1}]
\frac{1}{(1-z)^3} (1+z)^n
+ n [z^{n-2}] \frac{1}{(1-z)^2} (1+z)^{n-1}.$$
This is
$$\frac{1}{2} 
\sum_{q=0}^{n-1} {n\choose q} (n-1-q+1)(n-1-q+2)
+ n \sum_{q=0}^{n-2} {n-1\choose q} (n-2-q+1)$$
which is
$$\frac{1}{2} 
\sum_{q=0}^{n-1} {n\choose q} (n-q)(n-q+1)
+ n \sum_{q=0}^{n-2} {n-1\choose q} (n-q-1)
\\ = \frac{1}{2} \times n \times 2 + 
\frac{1}{2} 
\sum_{q=0}^{n-2} {n\choose q} (n-q)(n-q+1)
+ n \sum_{q=0}^{n-2} {n-1\choose q} (n-q-1)$$
which finally simplifies to
$$n + 
\frac{1}{2} 
\sum_{q=0}^{n-2} {n\choose q} (n-q)(n-q+1)
+ \sum_{q=0}^{n-2} {n\choose q} (n-q-1) (n-q)
\\ = n + \frac{3}{2}
\sum_{q=0}^{n-2} {n\choose q} (n-q)^2 
- \frac{1}{2} \sum_{q=0}^{n-2} {n\choose q} (n-q)
\\ = n - \frac{3}{2} n + \frac{1}{2} n
+ \frac{3}{2} \sum_{q=0}^n {n\choose q} (n-q)^2 
- \frac{1}{2} \sum_{q=0}^n {n\choose q} (n-q)
\\ = \frac{3}{2} \sum_{q=0}^n {n\choose q} (n-q)^2 
- \frac{1}{2} \sum_{q=0}^n {n\choose q} (n-q).$$
Recall the well-known identities (not difficult to prove)
$$\sum_{q=0}^n q {n\choose q} = n 2^{n-1} 
\quad\text{and}\quad
\sum_{q=0}^n q^2 {n\choose q} = n(n+1) 2^{n-2}$$
to finally obtain
$$\frac{3}{2}  n(n+1) 2^{n-2}
-\frac{1}{2}  n 2^{n-1}
=  n (3n+3) 2^{n-3}
- 2n 2^{n-3} = n(3n+1) 2^{n-3}.$$
There is more on annihilated coefficient extractors at this MSE link. 
Addendum.  These  last  two  identities  can be  proved  with  the
operator given by $z\frac{d}{dz}.$ For the first identity we have
$$\left.\left(z\frac{d}{dz}\right)
(1+z)^n\right|_{z=1} =
\left.nz(1+z)^{n-1}\right|_{z=1} = n2^{n-1}
=\sum_{q=0}^n q {n\choose q}$$
and for the second one
$$\left.\left(z\frac{d}{dz}\right)^2
(1+z)^n\right|_{z=1} =
\left.\left(z\frac{d}{dz}\right)
nz(1+z)^{n-1}\right|_{z=1}
\\= \left.zn(1+z)^{n-1} + n(n-1)z^2(1+z)^{n-2}\right|_{z=1}
= n2^{n-1} + n(n-1) 2^{n-2} 
\\= n(n+1) 2^{n-2}
= \sum_{q=0}^n q^2 {n\choose q}.$$
