Prove $\sum\limits_{i=0}^n\binom{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?
 A: How many solutions are there to $a_1+\cdots+a_k\leq n$ in nonnegative integers?
On the one hand, this is
$$\begin{align*}&\sum_{i=0}^n\#\{(a_1,\ldots,a_k)\mid a_1+\cdots+a_k=i\}\\
=& \sum_{i=0}^n\binom{i+k-1}{k-1}\end{align*}$$
On the other had, every solution to $a_1+\cdots+a_k\leq n$ corresponds to a unique solution of $a_1+\cdots+a_k+t=n$ by setting $t=n-(a_1+\cdots+a_k)$.
Hence $$\sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}k.$$
A: 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}$.
A: I'm sure there are some clever combinatorial arguments. I've never been very clever, so I'll induct on $n$.
An easy computation shows that the base case $n=0$ holds.
Now, suppose inductively that
$$\sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k}$$
Then
\begin{align*}
\sum_{i=0}^{n+1}\binom{i+k-1}{k-1}
&= \sum_{i=0}^n\binom{i+k-1}{k-1}+\binom{(n+1)+k-1}{k-1} \\
&= \binom{n+k}{k}+\binom{n+k}{k-1} \\
&\overset{\circledast}{=} \binom{(n+1)+k}{k}
\end{align*}
where the equality marked $\circledast$ uses the recursive formula for binomial coefficients. This completes the induction.
A: Generating function can do the job quite easily:
\begin{align*}
  \frac{1}{(1-x)^k} &= \sum_{i\ge 0} \binom{i+k-1}{k-1}\, x^i
\end{align*}
Using convolution of generating functions,
\begin{align*}
  \frac{1}{(1-x)}\cdot \frac{1}{(1-x)^k} &= \sum_{n\ge 0} \left(\sum_{i=0}^n \binom{i+k-1}{k-1}\right) x^n \\
   \frac{1}{(1-x)^{k+1}} &=  \sum_{n\ge 0} \binom{n+k}{k} x^n \\
\implies \sum_{i=0}^n \binom{i+k-1}{k-1} &= \binom{n+k}{k}
\end{align*}
