Sum of combinations formula

Question

Is there an explicit formula for the sum $0\dbinom{n}{0}+1\dbinom{n}{1}+\dots+n\dbinom{n}{n} = \sum_{k=0}^nk\dbinom{n}{k}$?

Answer 1

Yes. You know that $(1+x)^n=\sum_{k=0}^nx^k\dbinom{n}{k}$. Just differentiate this expression. You will obtain $n(1+x)^{n-1} = \sum_{k=0}^n kx^{k-1}\dbinom{n}{k}$.

Answer 2

Yes. Look at $f(x) = (1+x)^n$ with the binomial expansion and take $f’(1)$, which coincides with your sum, that is $n2^{n-1}$.

Answer 3

Actually, I think I got it because I realized I forgot to show what work I have already done in the question but as I was trying to refine my work I realized what I need to do: $$0\dbinom{n}{0}+1\dbinom{n}{1}+\dots+n\dbinom{n}{n}=$$ $$1\dbinom{n}{1}+2\dbinom{n}{2}+\dots+n\dbinom{n}{n}=$$ $$1\cdot\dfrac{n!}{1!\cdot (n-1)!}+2\cdot\dfrac{n!}{2!\cdot (n-2)!}+\dots+n\cdot\dfrac{n!}{n!\cdot 0!}=$$ $$n\left(1\cdot\dfrac{(n-1)!}{1!\cdot (n-1)!}+2\cdot\dfrac{(n-1)!}{2!\cdot (n-2)!}+\dots+n\cdot\dfrac{(n-1)!}{n!\cdot 0!}\right)=$$ $$n\left(\dfrac{(n-1)!}{0!\cdot (n-1)!}+\dfrac{(n-1)!}{1!\cdot (n-2)!}+\dots+\dfrac{(n-1)!}{(n-1)!\cdot 0!}\right)=$$ $$n\left(\dbinom{n-1}{0}+\dbinom{n-1}{1}+\dots+\dbinom{n-1}{n-1}\right)=$$ $$n\left(2^{n-1}\right)=\boxed{n \cdot 2^{n-1}}$$

---

Based on Lucas Henrique and Lucas De Souza's answers, this is what I came up with:

$$f(x)=(x+1)^n=\dbinom{n}{0}x^n+\dbinom{n}{1}x^{n-1}+\dots+\dbinom{n}{n}x^0$$ Taking the derivative of $f(x)$, we get $$f'(x)=n\cdot(x+1)^{n-1}=n\dbinom{n}{0}x^{n-1}+(n-1)\dbinom{n}{1}x^{n-2}+\dots+0\dbinom{n}{n}$$ This can also be written as $$f'(x)=n\dbinom{n}{n}x^{n-1}+(n-1)\dbinom{n}{n-1}x^{n-2}+\dots+0\dbinom{n}{0}$$ because $\binom{n}{k}=\binom{n}{n-k}$. Plugging in $1$ for $x$, we get $$f'(1)=n\dbinom{n}{n}+(n-1)\dbinom{n}{n-1}+\dots+0\dbinom{n}{0}$$ as desired. Thus, our sum can be represented by $f'(1)$, which can be calculated as $n\cdot(1+1)^{n-1}=\boxed{n\cdot2^{n-1}}$.

Answer 4

You can also prove the identity combinatorially as follows. Both sides count the number of ways to select a committee and chairperson from $n$ people. The sum counts according to committee size $k$, and the right hand side selects the chairperson ($n$ choices) and then the rest of the committee ($2^{n-1}$ subsets of the remaining $n-1$ people).

Answer 5

We can also use the binomial identity $\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$.

We obtain \begin{align*} \color{blue}{\sum_{k=1}^nk\binom{n}{k}}&=n\sum_{k=1}^n\binom{n-1}{k-1}\tag{1}\\ &=n\sum_{k=0}^{n-1}\binom{n-1}{k}\tag{2}\\ &\,\,\color{blue}{=n2^{n-1}}\tag{3} \end{align*}

Comment:

• In (1) we apply the binomial identity.

• In (2) we shift the index to start with $k=0$.

• In (3) we apply the binomial theorem.