6
$\begingroup$

Find the value of $\sum_{k=1}^{n}k\binom{n}{k}$ ?


I know that $\sum_{k=0}^{n}\binom{n}{k}= 2^{n}$ and so, $\sum_{k=1}^{n}\binom{n}{k}= 2^{n}-1$ but how to deal with $k$ ?

$\endgroup$
7
$\begingroup$

From the binomial theorem, we have

$$(1+x)^n=\sum_{k=0}^n\binom{n}{k}x^k\tag 1$$

Differentiating $(1)$ reveals

$$n(1+x)^{n-1}=\sum_{k=0}^n\binom{n}{k}kx^{k-1}\tag2$$

Setting $x=1$ in $(2)$ yields

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

And we are done!


Interestingly, I showed in THIS ANSWER, that for $m<n$, we have $$\sum_{k=0}^n\binom{n}{k}(-1)^k k^m=0$$

$\endgroup$
  • $\begingroup$ Nice Method !! Thanks :) $\endgroup$ – Jon Garrick Mar 10 '17 at 5:07
  • $\begingroup$ @JonGarrick You're quite welcome. My pleasure. -Mark $\endgroup$ – Mark Viola Mar 10 '17 at 5:08
5
$\begingroup$

There is also a combinatorial argument:

Suppose you have a room of $n$ people and want to select a committee of $k$ of them, where one member is the chairperson. There are $k\binom{n}{k}$ ways to do this. Your sum represents the total number of ways to select such a committee of any size (from $1$ to $n$) with a chairperson.

How else can we think of this? Instead, first pick the committee chairperson. There are $n$ ways to do this. Then, go to each of the remaining $n-1$ people and decide if they should be in the committee. There are $2^{n-1}$ ways to do this. Note that we can create any committee/chairperson team this way, as before. Hence your sum is equal to $n 2^{n-1}$.

$\endgroup$
  • 1
    $\begingroup$ My favourite kind of answer :) $\endgroup$ – Patrick Stevens Mar 10 '17 at 19:51
  • 1
    $\begingroup$ Agreed, nothing beats a combinatorial proof. $\endgroup$ – Alex B. Mar 11 '17 at 2:04
5
$\begingroup$

We have \begin{align*} \sum_{k=0}^nk{n\choose k} &=\sum_{k=1}^nk{n\choose k}\\ &=n\sum_{k=1}^n\frac{(n-1)!}{(k-1)!(n-k)!}\\ &=n\sum_{\ell=0}^{n-1}\frac{(n-1)!}{\ell!((n-1)-\ell)!} \tag{by taking $\ell=k-1$}\\ &=n\sum_{\ell=0}^{n-1}{n-1\choose\ell}\\ &=n2^{n-1}. \end{align*}

$\endgroup$
3
$\begingroup$

Proof without derivatives:

$$\sum_{k=1}^nk\binom{n}{k}=\sum_{k=1}^n k\frac{n!}{(n-k)!k!} =\sum_{k=1}^n \frac{n!}{(n-k)!(k-1)!} \\ = \sum_{k=1}^n \frac{n(n-1)!}{(n-k)!(k-1)!} = \sum_{k=1}^n n\binom{n-1}{k-1} \\ = n \sum_{k=0}^{n-1}\binom{n-1}{k}= n2^{n-1}$$

Alternate proof via probability theory:

Toss a fair coin $n$ times, find the expected no of heads. Let $N$ be the random variable denoting the number of heads. Then $E[N] = n/2$ because $N$ is the sum of $n$ bernoulli random variables with probability $1/2$. But we also know that $N$ has a binomial distribution. Hence $$E[N] =\sum_{k=1}^nk\binom{n}{k}2^{-n} $$

Rearrange to get your answer.

$\endgroup$
2
$\begingroup$

"And so $\sum_{k=1}^n\binom nk=2^{n-1}$". Nope: $2^n-1$.

Sketch: Notice that $$\sum_{k=1}^n k\binom nk x^{k-1}$$ is the derivative of $\sum_{k=0}^n\binom nk x^k$.

$\endgroup$
  • 1
    $\begingroup$ Sorry, That was a type !! Fixed now :) $\endgroup$ – Jon Garrick Mar 10 '17 at 4:52
2
$\begingroup$

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \mc{I} & \equiv \sum_{k = 1}^{n}k{n \choose k} = \sum_{k = 0}^{n}\pars{n - k}{n \choose n - k} = n\sum_{k = 0}^{n}{n \choose k} - \sum_{k = 0}^{n}k{n \choose k} = n\ 2^{n} - \sum_{k = 1}^{n}k{n \choose k} \\[5mm] & = 2^{n}\,n - \mc{I} \implies \bbx{\ds{\mc{I} \equiv \sum_{k = 1}^{n}k{n \choose k} = 2^{n - 1}\,n}} \end{align}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.