blog POST

How many subsets are there in 5 elements?


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

© 2020 - Philosophypedia| All Rights Reserved | Designed With ❤ Wibitech