Hockey Stick Identity

Math Probability

Statement

For $n\ge r$, $n,r\in \mathbb{N}$:

$$\sum _{i=r}^n\left(\genfrac{}{}{0ex}{}{i}{r}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{r+1}\right)$$

Proof

Let us have a base case $n=r$:

$$\left(\genfrac{}{}{0ex}{}{r}{r}\right)=\left(\genfrac{}{}{0ex}{}{r+1}{r+1}\right)=1$$

Now suppose ${\sum }_{i=r}^n\left(\genfrac{}{}{0ex}{}{i}{r}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{r+1}\right)$ for a certain $n$:

$$\begin{gathered} \sum _{i=r}^n\left(\genfrac{}{}{0ex}{}{i}{r}\right)+\left(\genfrac{}{}{0ex}{}{n+1}{r}\right) \\ =\left(\genfrac{}{}{0ex}{}{n+1}{r+1}\right)+\left(\genfrac{}{}{0ex}{}{n+1}{r}\right) \\ =\left(\genfrac{}{}{0ex}{}{n+2}{r+1}\right) \end{gathered}$$

Since $n=r$ is true, and if a case is true for $n$, it is true for $n+1$, this statement is true for all $n\ge r$.