Prove $\sum\limits_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k}$ (a.k.a. Hockey-Stick Identity) [duplicate]

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

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.

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*}

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