How to prove this $\sum_{l=0}^{n}l\binom{n}{l}=n2^{n-1}$ with induction?

69 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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