Solution: 2015 Fall Midterm - 6
Author: Michiel SmidQuestion
What does
$$
\sum_{k=1}^{m} {m \choose k}
$$
count?
(a)
The number of subsets of a set of size $m$.
(b)
The number of bitstrings of length $m$ having exactly $k$ many 1s.
(c)
None of the above.
(d)
The number of non-empty subsets of a set of size $m$.
Solution
Let’s just write out the first couple I guess
- We choose 1 element from m elements = $\binom{m}{1}$
- We choose 2 elements from m elements = $\binom{m}{2}$
- ...
- We choose m elements from m elements = $\binom{m}{m}$
Thus, $\sum_{k=1}^{m} {\binom{m}{k}}$ counts the number of ways to choose k elements from m elements for all k from 1 to m