4
$\begingroup$

This question already has an answer here:

$$\sum\limits_{k=1}^{n} (k+1) \binom{n}{k} = 2^{n-1} \cdot (n+2)-1$$

Maybe it's simple to prove this equation but I'm not sure how to get along with the induction. Any hints for this? Or may I use another method?

Thanks a lot!

$\endgroup$

marked as duplicate by Martin Sleziak, Watson, drhab probability Oct 26 '16 at 20:01

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ I believe the final $-1$ isn't actually there, for instance when $n = 1$ LHS is $\binom{1}{0} + 2 \binom{1}{1} = 3$, which equals $2^{0} (1 + 2)$, no $-1$. $\endgroup$ – Andreas Caranti Oct 25 '16 at 13:50
  • $\begingroup$ Even with $n=0$, $1\ne1-1$. $\endgroup$ – Yves Daoust Oct 25 '16 at 14:20
  • 2
    $\begingroup$ Have a look at this post and other posts linked there. (Perhaps this is close enough to be considered a duplicate?) $\endgroup$ – Martin Sleziak Oct 25 '16 at 18:26
  • $\begingroup$ This post is rather similar, too: How can I solve $\sum\limits_{i = 1}^k i \binom{k}{i-1}$ $\endgroup$ – Martin Sleziak Oct 25 '16 at 19:38
6
$\begingroup$

It isn’t quite right as stated. Try $n=1$, for instance: the lefthand side is

$$1\binom10+2\binom11=3=2^0\cdot3\;,$$

not $2^0\cdot3-1$. You can get the correct identity easily from the identity $k\binom{n}k=n\binom{n-1}{k-1}$:

$$\begin{align*} \sum_{k=0}^n(k+1)\binom{n}k&=\sum_{k=0}^nk\binom{n}k+\sum_{k=0}^n\binom{n}k\\ &=n\sum_{k=0}^n\binom{n-1}{k-1}+2^n\\ &=n\sum_{k=0}^{n-1}\binom{n-1}k+2^n\\ &=2^{n-1}n+2^n\\ &=2^{n-1}(n+2)\;. \end{align*}$$

Added: A combinatorial proof is also possible. You have a pool of $n$ men and a woman. From this pool you are to form a committee of any size, except that it must include the woman, and to appoint one member of the committee to be chair. If the committee has $k$ men, where $0\le k\le n$, there are $\binom{n}k$ ways to choose them, and there are then $k+1$ ways to choose the chair of the committee. Summing over the possible values of $k$, we see that there are

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

ways to form the committee and choose its chair.

Alternatively, we can pick the chair first. If we pick one of the $n$ men to be chair, we can then select any subset of the remaining $n-1$ men and form the committee from these men and the woman; this can be done in $n2^{n-1}$ ways. If we pick the woman to be chair, we can fill out the committee with any of the $2^n$ subsets of the pool of men. Thus, there are $n2^{n-1}+2^n$ ways to form the committee and choose its chair, and the result follows.

Added2: Since the $k=0$ term on the lefthand side is $1$, the identity could also be corrected to

$$\sum_{k=1}^n(k+1)\binom{n}k=2^{n-1}(n+2)-1\;.$$

$\endgroup$
  • $\begingroup$ I see but I get this in my probability lecture. Maybe a writing mistake.. $\endgroup$ – jacmeird Oct 25 '16 at 13:57
  • $\begingroup$ @jacmeird: It’s definitely a mistake. Either the righthand side should be $n2^{n-1}+2^n$, or the summation on the lefthand side should start at $k=1$: the $k=0$ term is $(0+1)\binom{n}0=1\cdot1=1$, so leaving it out would reduce the total by $1$. $\endgroup$ – Brian M. Scott Oct 25 '16 at 14:07
  • 1
    $\begingroup$ @BrianM.Scott Thank you! If I start the summation with $k=1$, I have to do an index offset in your proof, right? $\endgroup$ – jacmeird Oct 25 '16 at 15:10
  • 2
    $\begingroup$ @jacmeird: You’re welcome! I would be inclined to start $$\sum_{k=1}^n(k+1)\binom{n}k=\sum_{k=0}^n(k+1)\binom{n}k-1$$ and just go on from there exactly as I did, with the $-1$ tagging along for the ride. $\endgroup$ – Brian M. Scott Oct 25 '16 at 15:12
11
$\begingroup$

Start with $$ (1 + x)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^{k}. $$ Multiply by $x$ to get $$ x (1 + x)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^{k+1}. $$ Differentiate to get $$ (1 + x)^{n} + n x (1 + x)^{n-1} = \sum_{k=0}^{n} (k + 1) \binom{n}{k} x^{k}. $$ Set $x = 1$ to get $$ 2^{n} + n 2^{n-1} = \sum_{k=0}^{n} (k + 1) \binom{n}{k}, $$ which is precisely your identity, except for the final $-1$ which I believe to be incorrect.

$\endgroup$
3
$\begingroup$

Another proof (without calculus). $$\sum\limits_{k=0}^{n} (k+1) \binom{n}{k} = \sum\limits_{k=0}^{n} k\binom{n}{k}+\sum\limits_{k=0}^{n} \binom{n}{k}\\ =\sum\limits_{k=1}^{n} n\binom{n-1}{k-1}+2^n =n2^{n-1}+2^n=2^{n-1} \cdot (n+2)$$ which is a bit different from your formula.

$\endgroup$
2
$\begingroup$

$$\sum_{k=0}^{n} (k+1) \binom{n}{k} =\sum_{k=0}^{n}k\binom{n}{k}+\sum_{k=0}^{n} \binom{n}{k}=\sum_{k=0}^{n}k\cdot\frac{n}{k}\binom{n-1}{k-1}+\sum_{k=0}^{n} \binom{n}{k}=$$ $$=n\sum_{k=0}^{n}\binom{n-1}{k-1}+\sum_{k=0}^{n}\binom{n}{k}=$$ $$=n\sum_{k=1}^{n}\binom{n-1}{k-1}+\sum_{k=0}^{n}\binom{n}{k}=n2^{n-1}+2^n $$

$\endgroup$
1
$\begingroup$

$$k\binom nk=k\frac{n!}{k!(n-k)!}=\frac{n(n-1)!}{(k-1)!((n-1)-(k-1))!}=n\binom{n-1}{k-1}.$$

Then the original summation will yield terms $n2^{n-1}$ and $2^n$, or $2^{n-1}(n+2)$.

Note that the original sum has $n+1$ terms, while the transformed one has only $n$. But this makes no difference as the first term is with $k=0$.

$\endgroup$
1
$\begingroup$

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{{#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} \sum_{k = 1}^{n}\pars{k + 1}{n \choose k} & = -1 + \sum_{k = 0}^{n}\pars{k + 1}{n \choose k} \\[5mm] & = -1 + {1 \over 2}\sum_{k = 0}^{n}\bracks{% \pars{k + 1}{n \choose k} + \pars{n - k + 1}{n \choose n - k}} \\[5mm] & = -1 + {1 \over 2}\pars{n + 2}\sum_{k = 0}^{n}{n \choose k} = -1 + {1 \over 2}\pars{n + 2}\,2^{n} = \bbx{\ds{2^{n - 1}\pars{n + 2} - 1}} \end{align}

$\endgroup$

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