"Prove ${{n+1}\choose{m+1}} = \sum_{k=m}^{n}{k \choose m}$ by repeatedly using the Pascal Identity ${{n+1} \choose {m+1}}={{n} \> \choose {m+1}} + {n \choose m}$"
I don't know how to start this problem. I know the version of Pascal's Identity has a 1 added to the identity. Am I just supposed to plug ${k \choose m}$ in the identity and repeat using the result?
You can use repeatedly the Pascal identity, having in mind that $n=(n-1)+1$. We have:
\begin{align*} \binom{n+1}{m+1}&=\binom{n}{m}+\binom{n}{m+1}=\binom{n}{m}+\binom{[n-1]+1}{m}\\ &=\binom{n}{m}+\binom{n-1}{m}+\binom{n-1}{m+1}=\binom{n}{m}+\binom{n-1}{m}+\binom{[n-2]+1}{m+1}\\ &\\ &=\vdots\\ &\\ &=\binom{n}{m}+\binom{n-1}{m}+\binom{n-2}{m}+\cdots+\binom{m+2}{m}+\binom{m+1}{m}+\underbrace{\binom{m+1}{m+1}}_{=1}\\ &=\binom{n}{m}+\binom{n-1}{m}+\binom{n-2}{m}+\cdots+\binom{m+2}{m}+\binom{m+1}{m}+\underbrace{\binom{m}{m}}_{=1}\\ &=\sum_{k=m}^n \binom{k}{m} \end{align*}