Question

Prove that ${}^n$C${}_r$ + ${}^{n-1}$C${}_r$ + ${}^{n-2}$C${}_r$ + ${}^{n-2}$C${}_r$ +....................+ ${}^r$C${}_r$ = ${}^{n+1}$C${}_{r+1}$

Answer 1

To prove :

$n_{C_r}+{n-1}_{C_r}+{n-2}_{C_r}+......+n_{C_r}={n+1}_{C_{r+1}}$

We will prove this by induction

$S_n=r_{C_r}+{r+1}_{C_r}+{r+2}_{C_r}+......+{n-2}_{C_r}+{n-1}_{C_r}+n_{C_r},r\le n$

$={\sum }_{K=0}^{n-r}{r+K}_{C_r}={n+1}_{C_{r+1}}$ or ${n+1}_{C_{n-r}},r\le n$

We are tying to prove the above statement

Now,

$S_{n=r}=S_r=n_{C_r}=1$

and,

RHS $={r+1}_{C_{r+1}}=1$ as $n=r$

Also, $S_{r+1}={r+1}_{C_r}+{r+1}_{C_r}=1+r+1=r+2;$ RHS with $n=r+1$ is equal to ${r+1+1}_{C_{r+1}}=r+2$

Say $S_P={P+1}_{C_{r+1}}$

Then $S_{PH}={P+1}_{C_{r+1}}+{P+1}_{C_r}=\frac{\left(PH\right)!}{(r+1)!(p-r)!}+\frac{(P+1)!}{r!(p-r+1)!}$

$=\frac{(P+1)!}{r!(p-r)!}[\frac{1}{r+1}+\frac{1}{\left(PH\right)-r}]=\frac{(P+1)!}{r!(p-r)!}\times \frac{P+2}{(r+1)(pH-r)}$

$=\frac{(P+2)!}{(r+1)!(p+1-r)!}={P+2}_{C_{r+1}}=RHS$

So it $S_p$ is true the $S_{p+1}$ is true for all $P$.

Hence proved.