# Proof of equation with binomial coefficients: $\sum\limits_{k=1}^{n} (k+1) \binom{n}{k} = 2^{n-1} \cdot (n+2)-1$ [duplicate]

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!

## marked as duplicate by Martin Sleziak, Watson, drhab probability StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); 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.

• 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$. – Andreas Caranti Oct 25 '16 at 13:50
• Even with $n=0$, $1\ne1-1$. – Yves Daoust Oct 25 '16 at 14:20
• Have a look at this post and other posts linked there. (Perhaps this is close enough to be considered a duplicate?) – Martin Sleziak Oct 25 '16 at 18:26
• This post is rather similar, too: How can I solve $\sum\limits_{i = 1}^k i \binom{k}{i-1}$ – Martin Sleziak Oct 25 '16 at 19:38

## 6 Answers

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\;.$$

• I see but I get this in my probability lecture. Maybe a writing mistake.. – jacmeird Oct 25 '16 at 13:57
• @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$. – Brian M. Scott Oct 25 '16 at 14:07
• @BrianM.Scott Thank you! If I start the summation with $k=1$, I have to do an index offset in your proof, right? – jacmeird Oct 25 '16 at 15:10
• @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. – Brian M. Scott Oct 25 '16 at 15:12

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.

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.

$$\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$$

$$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$.

$\newcommand{\bbx}{\,\bbox[8px,border:1px groove navy]{{#1}}\,} \newcommand{\braces}{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}{\displaystyle{#1}} \newcommand{\expo}{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}{\mathcal{#1}} \newcommand{\mrm}{\mathrm{#1}} \newcommand{\pars}{\left(\,{#1}\,\right)} \newcommand{\partiald}[]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}{\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}