Question

Use Exercise 33 to prove Theorem 4. (Hint: Count the number of paths with n steps of the type described in Exercise 33. Every such path must end at one of the points (n − k, k) for k = 0, 1, 2, . . . , n.)

Short answer

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

Step-by-step solution

Step 1: Considerations

Suppose we have to reach from \(\left( {0,0} \right){\rm{ }}to{\rm{ }}\left( {n - r,r + 1} \right)\) using one step at a time as described in 33. The number of upward steps is \(r + 1\) and the least of these steps can occur on overall step number \(r + 1,r + 2,r + 3,.......n + 1\).

If the location of the point when the last upward step is taken is \((k,r)\) then the number of ways to reach this location is

\(\left( {\begin{array}{*{20}{c}}{k + r}\\r\end{array}} \right),\;where\;0 \le k \le n - r\)

Final equation

For each of these ways, the rest of the steps are fixed, i.e. the next step is upward and then all the remaining steps are rightward. Hence the total number of steps needed to reach \(\left( {0,0} \right){\rm{ }}to{\rm{ }}\left( {n - r,r + 1} \right)\) is

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

Using the result of 33 we get

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