Combinatorial proof of the identity ${n+1\choose k+1}={k\choose k}+{k+1\choose k}+...+{n-1\choose k}+{n\choose k}$ [duplicate]
We are choosing $k+1$ numbers from the numbers $1,2,3,\dots,n+1$. There are $\binom{n+1}{k+1}$ ways to do this. Let us count the number of choices in another way.
Maybe $1$ is the smallest number chosen. Then there are $\binom{n}{k}$ ways to choose the remaining $k$.
Maybe $2$ is the smallest number chosen. Then there are $\binom{n-1}{k}$ ways to choose the remaining $k$.
Maybe $3$ is the smallest number chosen. Then there are $\binom{n-2}{k}$ ways to choose the remaining $k$.
And so on. Add up. We get our sum (backwards).