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

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

• 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

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