 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2014/discrete-mathematics-continuous-mathematics-and-probability/2/c/solution

Partition the power set into disjoint classes according to subset size. The class of size-

i

(i n)

, while the whole power set has cardinality

2^{n}

. Counting every subset once gives

i = 0 \sum n (i n) = 2^{n} .

This is also the binomial theorem evaluated at

1 + 1

, but the counting proof follows directly from the earlier parts.

 New to topics? Read the docs here!