# Question about answer given to grid walking problem

Can anyone provide insight to the following question along with the following answer:

In Lemuria, the marketplace is laid out in a four by five grid. Vendors at each of twenty locations in the grid are followed by the vendor immediately north of them and the vendor immediately west of them (if either exist). Whenever a vendor receives a sample, that vendor sends its own (different) samples to each vendor (if any) following it. If the southeasternmost vendor sends a sample to each of the vendors following it, then how many samples will be passed around in total?

Answer:

$$-1+\sum_{i=1}^{4}\sum_{j=1}^5\binom{i+j}{j}=-1 + \binom {5+6}{5}-1=460$$

How is the double sigma notation so quickly reduced to the result on the RHS of the equation? Also, is this an application of the hockey stick identity? If someone could explain this answer in more detail that would be great. The answer given is what is posted above without further explanation and assumes some ideas that it seems are not familiar to me.

## 1 Answer

The answer is wrong. I’ll ignore the leading $-1$ and just evaluate the double sum.

\begin{align*} \sum_{i=1}^4\sum_{j=1}^5\binom{i+j}j&=\sum_{i=1}^4\sum_{j=1}^5\binom{i+j}i&(i+j)-j=i\\ &=\sum_{i=1}^4\left(\sum_{j=0}^5\binom{i+j}i-\binom{i}i\right)\\ &=\sum_{i=1}^4\left(\binom{i+6}{i+1}-1\right)&\text{hockey stick}\\ &=\sum_{i=1}^4\binom{i+6}{5}-4&(i+6)-(i+1)=5\\ &=\sum_{i=7}^{10}\binom{i}5-4\\ &=\sum_{i=5}^{10}\binom{i}5-\binom65-\binom55-4\\ &=\binom{11}6-6-1-4&\text{hockey stick}\\ &=\binom{11}6-11\\ &=451 \end{align*}

• Thanks. How did the $-1$ become a $-4$ after the first application of the hockey stick identity? – ClownInTheMoon Oct 23 '16 at 22:03
• @ClownInTheMoon: $$\sum_{i=1}^4\left(\binom{i+6}5-1\right)= \sum_{i=1}^4\binom{i+6}5-\sum_{i=1}^41 =\sum_{i=1}^4\binom{i+6}5-4\;.$$ – Brian M. Scott Oct 23 '16 at 22:06