Induction based on combinations and binomial theorem: ${}^nC_0+{}^{n+1}C_1+{}^{n+2}C_2+\dots+{}^{n+p}C_p={}^{n+p+1}C_p$

Question

I was looking at some questions in a Cambridge text and I reached this question however I am at it for 1 hr and can't seem to get the proof right. Any help ?

Answer 1

Assume it true for $p-1$, i.e. $${}^nC_0+{}^{n+1}C_1+{}^{n+2}C_2+\dots+{}^{n+p-1}C_{p-1}={}^{n+p}C_{p-1}$$ Let's prove it for $p$, i.e. $${}^nC_0+{}^{n+1}C_1+{}^{n+2}C_2+\dots+{}^{n+p}C_p={}^{n+p+1}C_p$$ So the left hand side is composed of the assumption in the first equation plus ${}^{n+p}C_p$, i.e. $${}^nC_0+{}^{n+1}C_1+{}^{n+2}C_2+\dots+{}^{n+p-1}C_{p-1}+{}^{n+p}C_p = {}^{n+p}C_{p-1} + {}^{n+p}C_{p}$$ By the addition property of combinations on the right hand side above, we get $${}^nC_0+{}^{n+1}C_1+{}^{n+2}C_2+\dots+{}^{n+p-1}C_{p-1}+{}^{n+p}C_p ={}^{n+p+1}C_p$$