# Another Hockey Stick Identity

I know this question has been asked before and has been answered here and here.

I have a slightly different formulation of the Hockey Stick Identity and would like some help with a combinatorial argument to prove it. First I have this statement to prove: $$\sum_{i=0}^r\binom{n+i-1}{i}=\binom{n+r}{r}.$$ I already have an algebraic solution here using the Pascal Identity: \begin{align*} \binom{n+r}{r}&=\binom{n+r-1}{r}+\binom{n+r-1}{r-1}\\ &=\binom{n+r-1}{r}+\left[\binom{n+(r-1)-1}{(r-1)}+\binom{n+(r-1)-1}{r-2}\right]\\ &=\binom{n+r-1}{r}+\binom{n+(r-1)-1}{(r-1)}+\left[\binom{n+(r-2)-1}{r-2}+\binom{n+(r-2)-1}{(r-2)-1}\right]\\ &\,\,\,\vdots\\ &=\binom{n+r-1}{r}+\binom{n+(r-1)-1}{(r-1)}+\binom{n+(r-2)-1}{(r-2)-1}+\binom{n+(r-3)-1}{r-3}+\cdots+\left[\binom{n+1-1}{1}+\binom{n+1-1}{0}\right]\\ &=\binom{n+r-1}{r}+\binom{n+(r-1)-1}{(r-1)}+\binom{n+(r-2)-1}{(r-2)-1}+\binom{n+(r-3)-1}{r-3}+\cdots+\binom{n+1-1}{1}+\binom{n-1}{0}\\ &=\sum_{i=0}^r\binom{n+i-1}{i}. \end{align*}

I have read both combinatorial proofs in the referenced answers above, but I cannot figure out how to alter the combinatorial arguments to suit my formulation of the Hockey Stick Identity. Basically, this formulation gives the "other" hockey stick. Any ideas out there?

## 2 Answers

Note that $\binom{n+r}{r}=\binom{n+r}{n}$ is the number of subsets of $\{1,2,\ldots,n+r\}$ of size $n$. On the other hand, for $i=0,1,2,\ldots,r$, $\binom{n+i-1}{i}=\binom{n+i-1}{n-1}$ is the number of subsets of $\{1,2,\ldots,n+r\}$ of size $n$ whose largest element is $n+i$.

• This is exactly what I was hoping for. Thanks. – Laars Helenius May 14 '16 at 12:47

Suppose that the Diophantine inequality $x_1 + x_2 + ... + x_n \le r$ has $A(n, r)$ non-negative integer solutions. (Or one has to disturb at most $r$ objects into $n$ bins and this task is possible in $A(n, r)$ ways. Note that one distinguishes the bins but one does not wish to distinguish the objects)

We will calculate $A(n, r)$ in two ways.

$$x_1 + x_2 + ... + x_n \le r \\ \Rightarrow \exists x_{n+1} \in \mathbb{Z^+}\cup\{0\}: x_1 + x_2 + ... + x_n + x_{n+1} = r$$

According to stars and bars problem,

$$A(n, r) = \left(\!\!{n + 1 \choose r}\!\!\right) = {n + r \choose r} \qquad \mathcal{\color{navy}{(I)}}$$

Hence wee seek integer solutions (and $r$ is also an integer), by the rule of sum, $A(n, r)$ would be the sum of non-negative integer solutions to these equations:

$$x_1 + x_2 + \cdots + x_n = 0\\or\\ x_1 + x_2 + \cdots + x_n = 1\\or\\ x_1 + x_2 + \cdots + x_n = 2\\or\\ \vdots\\or\\ x_1 + x_2 + \cdots + x_n = r$$

For all $0 \le i \le r$, the equation $x_1 + x_2 + ... + x_n = i$ would have $\left(\!\!{n \choose i}\!\!\right) = {n + r - 1 \choose r}$ non-negative integer solutions. Hence,

$$A(n, r) = \sum_{i=0}^r\left(\!\!{n \choose i}\!\!\right) = \sum_{i=0}^r{n+i-1 \choose i} \qquad \mathcal{\color{navy}{(II)}} \\ {\color{navy}{(I)}}, {\color{navy}{(II)}} \Rightarrow {n + r \choose r} = \sum_{i=0}^r\left(\!\!{n \choose i}\!\!\right) = \sum_{i=0}^r{n+i-1 \choose i}$$

• Thank you for your help. This is an original way of looking at it from what I've seen. – Laars Helenius May 14 '16 at 12:49