How many subsets of \(\{1, 2, . . . , n\}\) are there of even size?
In how many ways can \(\{1, . . . , n\}\) be written as the union of two sets? Here, for example, \(\{1, 2, 3, 4\}\cup\{4, 5\}\) and \(\{4, 5\}\cup\{1, 2, 3, 4\}\) count as the same way of writing \(\{1, 2, 3, 4, 5\}\) as a union.
Prove for any natural number \(n\) that \((n + 1)(n + 2). . .(2n)\) is divisible by \(2^n\).