Question

Use Exercise 33 to prove the hockeystick identity from Exercise 27. (Hint: First, note that the number of paths from (0, 0) to (n + 1, r) equals \(\left( {\begin{array}{*{20}{c}}{n + 1 + r}\\r\end{array}} \right)\). Second, count the number of paths by summing the number of these paths that start by going k units upward for k = 0, 1, 2, . . . , r.)

Short answer

\(\sum\limits_{k = 0}^r {\left( {\begin{array}{*{20}{c}}{n + k}\\k\end{array}} \right)} = \left( {\begin{array}{*{20}{c}}{n + r + 1}\\r\end{array}} \right)\)

Step-by-step solution

Step 1: Considerations

The number of paths from\(\left( {0,0} \right){\rm{ }}to{\rm{ }}\left( {n + 1,r} \right)\;is\;\left( {\begin{array}{*{20}{c}}{n + r + 1}\\r\end{array}} \right)\). Let us now consider the paths where last k upward steps are taken after the first rightward step. Clearly n rightward steps are also to be taken after this step.

Step 2: Total number of upward steps

So the number of ways to reach the final point from from this step onwards is\(\left( {\begin{array}{*{20}{c}}{n + k}\\k\end{array}} \right)\) and this is true for all \(0 \le k \le r\), since the number of upward steps after first rightward step can be anything from zero to r. thus equating the number of ways from two different countings.

\(\sum\limits_{k = 0}^r {\left( {\begin{array}{*{20}{c}}{n + k}\\k\end{array}} \right)} = \left( {\begin{array}{*{20}{c}}{n + r + 1}\\r\end{array}} \right)\)