Identity
Sum of binomial coefficients:
Algebra • Binomial Theorem
Formula
For every whole number , . So a set with elements has subsets in all.
How to use it
- 1Why it works: to build a subset, decide for each element whether it is in or out. That is choices, times, so subsets. Counting the same subsets by size gives .
- 2The same result is with .
Worked example
How many subsets does a set with elements have, and how many of them have at least one element?
Step-by-step
- 1subsets
Why: Each element is in or out.
- 2
Why: Remove the empty set.
Answer
subsets, of them non-empty