3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.