Problem
COM-B2-M01-P004 All Subsets
#4
★★☆☆☆ Level 2 of 5
Give a combinatorial proof of \(\sum_{k=0}^{n}\binom nk=2^n\).
Count all subsets of an \(n\)-element set.
The right side \(2^n\) counts subsets by independent choices: each element is either included or not. The left side counts the same subsets by size: choose the size \(k\), then choose the \(k\)-element subset. These are the same objects, so the identity follows.
Even a basic identity should be explained through the object being counted.