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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ try with "common properties of Pascal's Triangle" $\endgroup$ – Exodd Mar 16 '18 at 17:28

That's known as the Hockey-stick identity (from Pascal's Triangle trick)

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

  • $\begingroup$ Oh, thank you very much. I never heard about that identity before, so I couldn't know what to search on the Internet. $\endgroup$ – ZhangTianrong Mar 16 '18 at 17:47
  • $\begingroup$ @ZhangTianrong You are welcome! Bye $\endgroup$ – gimusi Mar 16 '18 at 17:49

Not the answer you're looking for? Browse other questions tagged or ask your own question.