Solution: 2018 Fall Final - 5
Author: Michiel SmidQuestion
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 bitstrings of length $n$ that contain at least one 0.
(b)
The number of subsets of $S$ that contain at least two elements.
(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.
Solution
Let’s break down which ones are right and which ones are wrong
- The number of subsets of $S$ that are non-empty.
This phrase takes into account subsets of size 1 but the equation starts at 2. This is wrong. - The number of subsets of $S$ that contain at least two elements.
So this one looks right. We start off at subsets of size at least 2 and go all the way up to subsets of size $n$. This is correct. - The number of bitstrings of length $n$ that contain at least one 0.
So this one is wrong because it doesn't contain bitstrings that contain one 0 - The number of bitstrings of length $n$ that contain at least three 0's.
This one is wrong because it doesn't contain bitstrings that contain at two 0's