2

We have :

$\sum_{l=0}^{n}l\binom{n}{l}=n2^{n-1}$

So first step, base of induction. If we take $n=1$ we get $1=1$.

Assuming that his equality $\sum_{l=0}^{n}l\binom{n}{l}=n2^{n-1}$ is true, we need to prove

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

I assume we should use pascal identity in this step but i have no idea how to solve it.

Tars Nolan
  • 387
  • Do you really want to do it by induction? Otherwise via the binomial theorem we have $(x+1)^n = \sum_{l=0}^{n} \binom{n}{l} x^{l}$ and hence $\frac{d}{dx} (x+1)^n = n(x+1)^{n-1} = \frac{d}{dx} \sum_{l=0}^{n} \binom{n}{l} x^{l} = \sum_{l=0}^{n} \binom{n}{l} lx^{l-1}$. Therefore $n2^{n-1} = \sum_{l=0}^{n} \binom{n}{l} l$ – Nex Oct 10 '16 at 21:05

1 Answers1

4

As you suggested, Pascal's identity gives $$\sum_{l=0}^{n+1} l\binom{n+1}{l}=\sum_{l=0}^{n+1}l\binom{n}{l}+\sum_{l=0}^{n+1}l\binom{n}{l-1}$$ Since the term for $l=n+1$ in the first sum is zero, the first sum equals $$\sum_{l=0}^{n}l\binom{n}{l}=n2^{n-1}$$ by the induction hypothesis. For the second sum, we re-index $k=l-1$ and get $$\sum_{k=0}^{n}(k+1)\binom{n}{k}=\sum_{k=0}^{n}k\binom{n}{k}+\sum_{k=0}^{n}\binom{n}{k}.$$ In the latter expression, the first sum is $n2^{n-1}$ by the induction hypothesis, and it is a well-known fact that $$\sum_{k=0}^{n}\binom{n}{k}=2^{n}.$$ Alltogether, we obtain $$\sum_{l=0}^{n+1} l\binom{n+1}{l}=n2^{n-1}+n2^{n-1}+2^{n}=n2^{n}+2^{n}=(n+1)2^{n}.$$

studiosus
  • 4,147