Question

Use Exercise 33 to prove Pascal’s identity. (Hint: Show that a path of the type described in Exercise 33 from (0, 0) to (n + 1 − k, k) passes through either (n + 1 − k, k − 1) or (n − k, k), but not through both.)

Short answer

\(\left( {\begin{array}{*{20}{c}}{n - k + 1}\\k\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{n - k}\\k\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{n - k + 1}\\{k - 1}\end{array}} \right)\)

Step-by-step solution

Considerations

If we have to move from\(\left( {0,0} \right){\rm{ }}to{\rm{ }}\left( {n - k + 1,k} \right)\)the last step can be either rightward or upward, i.e. the last step must start from one of \(\left( {n - k + 1,k} \right)\;or\;\left( {n - k + 1,k - 1} \right)\). Also observe that only one of these two points can be crossed during one particular path, not both.

Step 2: Further simplification

So the number of ways to reach \(\left( {n - k + 1,k} \right)\) is simply the sum of the number of ways to reach\(\left( {n - k + 1,k} \right)\)and \(\left( {n - k + 1,k - 1} \right)\)separately.

This implies according to 33

\(\left( {\begin{array}{*{20}{c}}{n - k + 1}\\k\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{n - k}\\k\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{n - k + 1}\\{k - 1}\end{array}} \right)\)