Having problems proving $ \sum_{r=0}^{n}(r+1) \binom{n}{r} = (n+2)2^{n-1} $

Question

I'm trying to prove the following

$$ \sum_{r=0}^{n}(r+1) \binom{n}{r} = (n+2)2^{n-1} $$

using the identity $$ \sum_{r=0}^{n} \binom{n}{r} = 2^{n} $$

but I'm not able to. This is what I did so far,

$$ \sum_{r=0}^{n}(r+1) \binom{n}{r} = (1) \binom{n}{0} + (2) \binom{n}{1} + ... + (n+1) \binom{n}{n} $$

Answer 1

Hint: Use $\binom{n}{r}=\binom{n}{n-r}$ and add $\sum_{r=0}^{n}(r+1) \binom{n}{r}$ to itself in a clever way.

So if:

$$S=(1) \binom{n}{0} + (2) \binom{n}{1} + \cdots + (n+1) \binom{n}{n}$$

then:

$$S=(n+1)\binom{n}{0}+n\binom{n}{1}+\cdots + 1\binom{n}{n}$$

Add these two together to get a formula for $2S$.

Answer 2

Hint: you also know that $$ \sum_{r=0}^n \binom nr x^r = (1+x)^n $$ Try to write the derivative after multiplication by $x$.

solution:

$$ \sum_{r=0}^n \binom nr x^{r+1} = (1+x)^n x \\ \implies \sum_{r=0}^n (r+1)\binom nr x^{r} = (1+x)^n + nx(1+x)^{n-1} $$

Now set $x=1$:

$$ \sum_{r=0}^n (r+1)\binom nr = 2^n + n2^{n-1} = (n+2)2^{n-1} $$

Answer 3

Starting with the binomials expansion \begin{align} \sum_{r=0}^{n} \binom{n}{r} t^{r} = (1+t)^{n} \end{align} it can be seen by differentiation that \begin{align} \sum_{r=0}^{n} \binom{n}{r} r t^{r} = n t (1+t)^{n-1} = n \left[ (1+t)^{n} - (1+t)^{n-1} \right]. \end{align} Now by adding the original series to this result then \begin{align} \sum_{r=0}^{n} \binom{n}{r} (r+1) t^{r} = (n+1) (1+t)^{n} - n (1+t)^{n-1}. \end{align} Now let $t=1$ to obtain \begin{align} \sum_{r=0}^{n} \binom{n}{r} (r+1) &= 2^{n} (n+1) - 2^{n-1} n \\ &= 2^{n-1} (n+2) \end{align}

Answer 4

Opening up the binomial expressions, we get $$ r\binom{n}{r} = n\binom{n-1}{r-1}. $$ Therefore $$ \sum_{r=0}^n (r+1)\binom{n}{r} = \sum_{r=0}^n \binom{n}{r} + n\sum_{r=1}^n \binom{n-1}{r-1} = 2^n + n2^{n-1} = (n+2)2^{n-1}. $$

The "correct" proof of the related identity $\sum_{r=0}^n r\binom{n}{r} = n2^{n-1}$ is combinatorial: both sides count the number of ways to choose an element of $\{1,\ldots,n\}$ and a subset of $\{1,\ldots,n\}$ containing it. Similarly, the identity $\sum_{r=0}^n (r+1)\binom{n}{r} = n2^{n-1} + 2^n$ counts in two ways the number of ways of choosing a subset of $\{1,\ldots,n\}$ and, optionally, an element contained in it.