Question: 2018 Fall Final - 5
Let $n \geq 2$ be an integer and consider the set $S = \{1,2,\dots,n\}$. What does
$$
\sum_{k=2}^{n} {n \choose k}
$$ count?
(a)
The number of subsets of $S$ that contain at least two elements.
(b)
The number of bitstrings of length $n$ that contain at least one 0.
(c)
The number of bitstrings of length $n$ that contain at least three 0's.
(d)
The number of subsets of $S$ that are non-empty.