# Prove that $\binom{n}{0} + 2\binom{n}{1} + …(n+1)\binom{n}{n} = (n + 2)2^{n-1}$.

How can I prove the following identity?

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

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

and then evaluating it at $$x = 1$$, but I didn't get to my desired result. I just kept finding that $$\displaystyle\sum_{k = 0}^n k \binom{n}{k} = n2^{n-1}$$.

• Well, what happens if you add $2^n=\sum_{k=0}^n{n\choose k}$ to both sides of that identity? – Mastrem Feb 24 '20 at 22:10
• ... start with $x(1+x)^n$ and differentiate... – dan_fulea Feb 24 '20 at 22:42

You were almost there. Differentiating $$(1+x)^n=\sum_{k=0}^n{n\choose k}x^k$$ gets you $$n(1+x)^{n-1}=\sum_{k=1}^{n}k{n\choose k}x^{k-1}.$$ Plugging in $$x=1$$ then yields $$\sum_{k=0}^{n}k{n\choose k} = n2^{n-1},$$ which is as far as you got. However, if we add $$\sum_{k=0}^{n}{n\choose k}=2^n=2\cdot 2^{n-1}$$ to both sides, the result is $$\sum_{k=0}^n(k+1){n\choose k} = (n+2)2^{n-1},$$ as desired.

Here's an alternative proof that does not depend on derivatives: \begin{align} \sum_k (k+1) \binom{n}{k} &= \sum_k k\binom{n}{k} + \sum_k \binom{n}{k} \\ &= \sum_k n\binom{n-1}{k-1} + \sum_k \binom{n}{k} \\ &= n 2^{n-1} + 2^n \\ &= (n+2) 2^{n-1} \end{align}

Another way.

Multiply $$(1+x)^n=\sum_{k=0}^n{n\choose k}x^k$$ by $$x$$ to get $$x(1+x)^{n}=\sum_{k=0}^n{n\choose k}x^{k+1}$$.

Now when you differentiate you get

$$\begin{array}\\ \sum_{k=0}^n(k+1){n\choose k}x^{k} &=(x(1+x)^{n})'\\ &=(1+x)^n+xn(1+x)^{n-1}\\ &=(1+x)^{n-1}(1+x+nx))\\ &=(1+x)^{n-1}(1+x(n+1))\\ \end{array}$$

Setting $$x=1$$ gives $$\sum_{k=0}^n(k+1){n\choose k} =(n+2)2^{n-1}$$.

More generally, Multiply $$(1+x)^n=\sum_{k=0}^n{n\choose k}x^k$$ by $$x^m$$ to get $$x^m(1+x)^{n}=\sum_{k=0}^n{n\choose k}x^{k+m}$$.

Now when you differentiate you get

$$\begin{array}\\ \sum_{k=0}^n(k+m){n\choose k}x^{k+m-1} &=(x^m(1+x)^{n})'\\ &=mx^{m-1}(1+x)^n+x^mn(1+x)^{n-1}\\ &=x^{m-1}(1+x)^{n-1}(m(1+x)+xn))\\ &=x^{m-1}(1+x)^{n-1}(m+x(n+m))\\ \end{array}$$

Setting $$x=1$$ gives $$\sum_{k=0}^n(k+m){n\choose k} =2^{n-1}(2m+n)$$.

This, of course, can be gotten by adding earlier results.