How to mathematically prove: $\sum_{x = r}^{n} C(x , r) = C(n+1 , r+1)$.

47 Views Asked by At

The RHS is equal to the number of ways of selecting $r+1$ out of $n+1$ objects. If I sum the number of selections when the $(r+1)$th (i.e. the last) selection is the at the $(x+1)$th position, I get the RHS.

I verified it with some values but couldn't prove it mathematically.

1

There are 1 best solutions below

0
On

The usual notation is $\sum_{x=r}^n\binom{x}{r}=\binom{n+1}{r+1}$. Since $\binom{x}{r}=\binom{x+1}{r+1}-\binom{x}{r+1}$, the sum telescopes to $\binom{n+1}{r+1}-\binom{r}{r+1}$. But the last term is, of course, $0$.