0
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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$$

$\endgroup$
2
  • $\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$ Mar 16, 2018 at 17:47
  • $\begingroup$ @ZhangTianrong You are welcome! Bye $\endgroup$
    – user
    Mar 16, 2018 at 17:49

Not the answer you're looking for? Browse other questions tagged .