I have a algorithm and from the post its time complexity is: $\sum_{k=1}^{n}k\binom nk= n 2^{n-1}$

Question

I have a algorithm and from the post its time complexity is:

$$\sum_{k=1}^{n}k\binom nk= n 2^{n-1}$$

My question is, how to get the result $n2^{n-1}$ need some help . thanks

Answer 1

By definition of the binomial coefficients, $$(1+x)^n=\sum_{k=0}^n{n\choose k}x^k $$ Taking the derivative of both sides, we obtain $$n(1+x)^{n-1}=\sum_{k=0}^n{n\choose k}kx^k $$ Now let $x=1$.

Answer 2

$$\sum_{k=1}^{n}k\binom nk=n\sum_{k=1}^{n}\binom {n-1}{k-1}=n2^{n-1} $$

Answer 3

Another option is to use the "absorption identity"

$$ k \binom n k = n \binom {n-1} {k-1},$$

which is valid for all integer $k$. This gives

$$\begin{aligned} \sum_{k=1}^n k \binom n k &= n\sum_{k=1}^n \binom{n-1}{k-1} \\ &= n \sum_{k=0}^{n-1} \binom {n-1} k \\ &= n2^{n-1}. \end{aligned}$$