1

Prove that for all non-negative integers $n$, $$\sum_{r=0}^n r\binom{n}{r}=n2^{n-1}$$ My attempt and reasoning went as follows: $$n2^{n-1}=\frac{1}{2}n2^n=\frac{1}{2}n(1+1)^n$$ By the binomial theorem where $a=1$ and $b=1$: $$\frac{1}{2}n(1+1)^n=\frac{1}{2}n\sum_{r=0}^n \binom{n}{r}$$ So now we have to prove that $$\sum_{r=0}^n r\binom{n}{r}=\frac{1}{2}n\sum_{r=0}^n \binom{n}{r}$$ Induction on n

Base case $(n=0)$: $$\sum_{r=0}^0 r\binom{0}{r}=0\qquad\frac{1}{2}(0)\sum_{r=0}^0 \binom{0}{r}1=0\qquad 0=0$$ Therefore true when $(n=0)$

Inductive hypothesis: Assume $$\sum_{r=0}^k r\binom{k}{r}=\frac{1}{2}k\sum_{r=0}^k\binom{k}{r}$$ for some $k\in\mathbb{Z}$ where $k\ge 0$

Inductive conclusion: Want to prove $$\sum_{r=0}^{k+1}r\binom{k+1}{r}=\frac{1}{2}(k+1)\sum_{r=0}^{k+1}\binom{k+1}{r}$$ So $$\sum_{r=0}^{k+1} r\binom{k+1}{r}=\sum_{r=0}^{k} r\binom{k+1}{r}+(k+1)\binom{k+1}{k+1}=\sum_{r=0}^{k} r\binom{k+1}{r}+(k+1)$$ And this is where I'm stuck. How do I proceed from here? I think I'm almost there

Anson Pang
  • 589

2 Answers2

2

Proof by induction is an interesting exercise, but a direct proof is probably simpler:

$\sum_{r=0}^n r\binom{n}{r}=\sum_{r=1}^n \frac{n!}{(r-1)!(n-r)!} \quad \text{ (we can remove the r=0 term)}\\=n\sum_{r=1}^n \frac{(n-1)!}{(r-1)!(n-r)!} \quad\text{(n! = n(n-1)!)}\\=n\sum_{s=0}^{n-1} \frac{(n-1)!}{s!(n-1-s)!} \quad \text{(reindex with s=r-1)}\\=n\sum_{s=0}^{n-1}\binom{n-1}{s}\\=n2^{n-1}$

gandalf61
  • 15,326
1

Induction step:

$$\sum_{r=0}^{n+1} r\binom{n+1}{r}=$$

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

$$\sum_{r=1}^{n} r\binom{n+1}{r}+n+1=$$

$$\sum_{r=1}^{n} r\binom{n}{r}+\sum_{r=1}^{n} r\binom{n}{r-1}+n+1=$$

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

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

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

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

$$n2^{n-1}+n2^{n-1}-n+2^n-1+n+1=$$

$$2n2^{n-1}+2^n=$$

$$(n+1)2^n$$

Done.

The proof uses a well know fact that:

$$\sum_{k=0}^{n}\binom{n}{k}=2^n$$

EDIT: A simple direct proof:

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

$$f'(x)=n(1+x)^{n-1}=\sum_{k=1}^n k\binom{n}{k}x^{k-1}$$

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

Saša
  • 15,906