hockey-stick identity stars and bars proof

Topics

• hockey-stick identity

The Hockey Stick Identity: ${\sum }_{k=r}^n\left(\genfrac{}{}{0ex}{}{k}{r}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{r+1}\right)$ can be proven using a combinatorial argument based on distributing candies to children. Consider the following scenario:

We have n indistinguishable candies to distribute among k distinguishable children. This distribution can be counted in two different ways:

1. Direct Counting: Using the stars and bars method, we know there are $\left(\genfrac{}{}{0ex}{}{n+k-1}{k-1}\right)$ ways to distribute n indistinguishable objects into k distinguishable groups.
2. Alternative Counting: We can also count this by first deciding how many candies (call it i) to give to the first child:
   • For each choice of i candies (where $0\le i\le n$) given to the first child
   • We then distribute the remaining n-i candies to k-1 children
   • By stars and bars, this gives $\left(\genfrac{}{}{0ex}{}{n+k-2-i}{k-2}\right)$ ways for each i
   • Summing over all possible i gives us: ${\sum }_{i=0}^n\left(\genfrac{}{}{0ex}{}{n+k-2-i}{k-2}\right)$

By the principle of double counting, these must be equal:

$$\left(\genfrac{}{}{0ex}{}{n+k-1}{k-1}\right)=\sum _{i=0}^n\left(\genfrac{}{}{0ex}{}{n+k-2-i}{k-2}\right)$$

To transform this into our Hockey Stick Identity, we make the substitutions:

• Let $n^{\prime }=n+k-2$
• Let $r=k-2$

Noting that $n^{\prime }-n=k-2=r$, we get:

$\left(\genfrac{}{}{0ex}{}{n^{\prime }+1}{r+1}\right)={\sum }_{i=0}^{n^{\prime }-r}\left(\genfrac{}{}{0ex}{}{n^{\prime }-i}{r}\right)={\sum }_{i=r}^{n^{\prime }}\left(\genfrac{}{}{0ex}{}{i}{r}\right)$

Finally, renaming $n^{\prime }$ as $n$ and $i$ as $k$, gives us the identity:

$$\left(\genfrac{}{}{0ex}{}{n+1}{r+1}\right)=\sum _{k=r}^n\left(\genfrac{}{}{0ex}{}{k}{r}\right)$$

Related

• hockey-stick identity committee building proof