Exercise 14.
In Example 1.4.5 we established that the sum of any row in Pascal's triangle is a power of two. Specifically,
\begin{equation*}
{n\choose 0} + {n \choose 1} + {n\choose 2} + \cdots + {n \choose n} = 2^n\text{.}
\end{equation*}
The argument given there used the counting question, “how many pizzas can you build using any number of \(n\) different toppings?” To practice, give new proofs of this identity using different questions.
Use a question about counting subsets.
Use a question about counting bit strings.
Use a question about counting lattice paths.