Sunday, September 9, 2018

combinatorics - 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?


Answer



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


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...