combinatorics - Prove $sumlimits_{i=0}^nbinom{i+k-1}{k-1}=binom{n+k}{k}$ (a.k.a. Hockey-Stick Identity)

Let $n$ be a nonnegative integer, and $k$ a positive integer. Could someone explain to me why the identity

$$\sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k}$$
holds?

Answer

One way to interpret this identity is to consider the number of ways to choose $k$ integers from the set $\{1,2,3,\cdots,n+k\}$.

There are $\binom{n+k}{k}$ ways to do this, and we can also count the number of possibilities by considering the largest integer chosen. This can vary from $k$ up to $n+k$, and if the largest integer chosen is $l$, then there are $\binom{l-1}{k-1}$ ways to choose the remaining $k-1$ integers.

Therefore $\displaystyle\sum_{l=k}^{n+k}\binom{l-1}{k-1}=\binom{n+k}{k}$, and letting $i=l-k$ gives $\displaystyle\sum_{i=0}^{n}\binom{i+k-1}{k-1}=\binom{n+k}{k}$.