Question

nCr+n-1Cr+n-2Cr+n-3Cr...+rCr?

Answer 1

We will prove this by induction.

$S_n={}^rC_r+{}^{r+1}C_r+{}^{r+2}C_r+ .... +{}^{n-2}C_r+{}^{n-1}C_r+{}^nC_r,\ \ r<=n\\\\.\ \ \ =\Sigma_{k=0}^{n-r}\ {}^{r+k}C_r={}^{n+1}C_{r+1},\ \ or,\ \ {}^{n+1}C_{n-r},\ r<=n\\We\ want\ to\ prove\ this.\\\\S_r={}^rC_r=1.\ \ RHS={}^{r+1}C_{r+1}=1,\ \ as\ n=r\\\\S_{r+1}={}^rC_r+{}^{r+1}C_r=1+r+1=r+2\\RHS\ with\ n=r+1={}^{r+1+1}C_{r+1}=r+2.\\\\Let\ S_p={}^{p+1}C_{r+1}\\\\S_{p+1}={}^{p+1}C_{r+1}+{}^{p+1}C_{r}=\frac{(p+1)!}{(r+1)!(p-r)!}+\frac{(p+1)!}{r!(p+1-r)!}$

$.\ \ \ =\frac{(p+1)!}{r!(p-r)!}* [\frac{1}{r+1}+\frac{1}{p+1-r} ] =\frac{(p+1)!}{r!(p-r)!}* \frac{p+2}{(r+1)(p+1-r)}\\\\.\ \ \ =\frac{(p+2)!}{(r+1)!(p+1-r)!}={}^{p+2}C_{r+1}=R.H.S.\\\\Hence,\ proved.$