0

I am running into trouble for proving the inductive conclusion for the proof of the following statement:

For all non-negative integers $n$, $$\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)$$ So yeah, this is where I'm stuck. Any help?

Anson Pang
  • 589
  • While you can probably finish this argument in some way, here's a shorter one: First prove that $r \dbinom{n}{r} = n \dbinom{n-1}{r-1}$. Now what do you know about $\sum\limits_{r=0}^n \dbinom{n-1}{r-1}$ ? – darij grinberg Oct 26 '18 at 05:20
  • You will need to write $\binom{k+1}r$ in terms of $\binom{k}{{\rm something}}$. What does Pascal's triangle tell you about this? – David Oct 26 '18 at 05:24

0 Answers0