How to calculate $\sum\limits_{k=0}^{n}{k\dbinom{n}{k}}$

Question

I derived this sum from a problem I have been working on. Somehow I don't know how to proceed. I only know some basics like $\sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n$. Meanwhile I am reading the related topics trying to derive a formula. But it's like shooting in the dark.

Answer 1

Consider differentiating $(1+x)^n=\sum_{k=0}^{n}\binom{n}{k}x^k$ with respect to x, then substituting in a suitable value of x.

Alternatively, consider having a group of n people and forming a committee of k people with 1 chairman:

We can do this first by choosing the k people out of the initial n, and from those people choosing a chairman. Adding up the committee sizes where k=1 and k=n, this evaluates to: $\sum_{k=1}^n k \binom{n}{k}=\sum_{k=0}^{n}k\binom{n}{k}$ (note that we are effectively adding 0 to the sum)

This can also be done by first choosing the chairman from the n people- n ways. We then have (n-1) people left, who can either be in the committee or not, so the total number of committees with a chairman formed is: $n2^{n-1}$.

Since they are just two different ways of counting the same thing:

$\sum^n_{k=0}k \binom{n}{k}=n2^{n-1}$

Answer 2

$k\dbinom{n}{k} = n\dbinom{n-1}{k-1}$ follows directly from the definition of $\dbinom{n}{k}$ for $k > 0$.

$\sum\limits_{k=0}^{n}{k\dbinom{n}{k}} = \sum\limits_{k=1}^{n}{k\dbinom{n}{k}} = \sum\limits_{k=1}^{n}{n\dbinom{n-1}{k-1}} = n\sum\limits_{k=0}^{n-1}{\dbinom{n-1}{k}} = n*2^{n-1}$.

Answer 3

The Binomial theorem tells us that $$(1+x)^n = \sum_{k=0}^n{n\choose k}x^k,$$ so that $$n(1+x)^{n-1}=\sum_{k=0}^nk{n\choose k}x^{k-1}.$$ Now let $x=1$. Then $$n2^{n-1}=\sum_{k=0}^nk{n\choose k}.$$