# Combinatorial identity

## Hockey-Stick Identity

For $n,r\in\mathbb{N}, n>r,\sum^n_{i=r}{i\choose r}={n+1\choose r+1}$.

This identity is known as the hockey-stick identity because, on Pascal's triangle, when the addends represented in the summation and the sum itself are highlighted, a hockey-stick shape is revealed.

An image is supposed to go here. You can help us out by creating one and editing it in. Thanks.

### Proof

This identity can be proven by induction on $n$.

Base case Let $n=r$.

$\sum^n_{i=r}{i\choose r}=\sum^r_{i=r}{i\choose r}={r\choose r}=1={r+1\choose r+1}$.

Inductive step Suppose, for some $k\in\mathbb{N}, k>r$, $\sum^k_{i=r}{i\choose r}={k+1\choose r+1}$. Then $\sum^{k+1}_{i=r}{i\choose r}=\left(\sum^k_{i=r}{i\choose r}\right)+{k+1\choose r}={k+1\choose r+1}+{k+1\choose r}={k+2\choose r+1}$.

It can also be proven algebraicly with pascal's identity $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ Look at $\binom{r}{r}+\binom{r+1}{r}+\binom{r+2}{r}...+\binom{r+a}{r}$ It can be rewritten as $\binom{r+1}{r+1}+\binom{r+1}{r}+\binom{r+2}{r}+...+\binom{r+a}{r}$ Using pascals identity, we get $\binom{r+2}{r+1}+\binom{r+2}{r}+...\binom{r+a}{r}$ We can continuously apply pascals identity until we get to $\binom{r+a}{r-1}+\binom{r+a}{r}=\binom{r+a+1}{r+1}$