0

I am looking at the following problem and can not get any further.

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

Induction begin for $n = 0$

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

Shows $n$ holds, then $n + 1$ holds:

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

curiouscupcake
  • 231

1 Answers1

1

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

The last "=" is because $k \binom n k = \frac{k*n!}{k!(n-k)!} = n\frac{(n-1)!}{(n-k)!(k-1)!}$.

Because $\sum\limits_{k=0}^{n-1} \binom {n-1} k = 2^{n-1}$, $\sum\limits_{k=0}^n (k+1) \binom n k = 2^{n-1}(n+2)$.

Done.

Muses_China
  • 1,008
  • 5
  • 17