# How to prove the equation $\sum^{N-r}_{x=0}\begin{pmatrix} N-x \\ r \end{pmatrix}=\begin{pmatrix} N+1 \\ r+1 \end{pmatrix}$ [duplicate]

I was trying to solve a probabilistic problem and I found I had to use the equality $\displaystyle\sum^{N-r}_{x=0}\begin{pmatrix} N-x \\ r \end{pmatrix}=\begin{pmatrix} N+1 \\ r+1 \end{pmatrix}$ in an intermediate step. I verified it with Wolfram Alpha, but I really can't come up with a proof (I tried expanding everything out but find no clue in the end). I hope I can find a proof here and it is even more delighting if someone is willing to teach me some typical ways of proving equations involving combinations and permutations, which seem to be unmentioned in the textbook I am currently using.

## marked as duplicate by angryavian, Thomas Andrews, Robert Z, Community♦Mar 16 '18 at 17:50

$$\sum^n_{i=r}{i\choose r}={n+1\choose r+1} \qquad \text{ for } n,r\in\mathbb{N}, \quad n>r$$