How many subsets are there in 5 elements?
32
If a set has n members, the number of subsets is 2^n.
0 members→1 subset
1 members→2 subsets
2 members→4 subsets
3 members→8 subsets
Proof by induction:
Base-case: S has zero members.
In that case, the empty set S is a subset of S, and it is S’s only subset.
Inductive case: S has n members and 2^n subsets.
Let S* be just like S except that S* has a member x that S does not have.
In that case, each subset of S is also a subset of S*; but for each subset s of S that is a subset of S*, there is an additional subset s* that contains x but is otherwise just like s. Consequently, the number of subsets of S* is exactly double that of S. Therefore, the number of subsets of S* is 2^(n+1).
10 views0 comments