Exercise 4.10: Pascal's Rule

chapter 4

We want to pick \(k\) from a total of \(n\) balls. Putting one particular ball aside, we can either select all \(k\) balls from the remaining \(n-1\), or take the ball we put aside, and select the remaining \(k-1\) balls from the \(n-1\). The sum equals the total number of ways to pick \(k\) out of \(n\) balls.

Alternative solution

\begin{align} { n-1 \choose k } + {n-1 \choose k-1} &= \frac{(n - 1) \cdots (n-k+1) (n - k)}{k \cdot (k-1)!} + \frac{(n - 1) \cdots (n-k+1)}{(k - 1)!} \newline &= \frac{(n-1) \cdots (n-k+1)}{k!} (n - k + k) = {n \choose k} \, . \end{align}