5
$\begingroup$

How can I prove the following identity?

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

I thought about differentiating this:

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

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

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.

$\endgroup$
2
$\begingroup$

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}

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy