Question

Use induction to prove that every set of n elements has 2ⁿ distinct subsets, for all n ? 0.

Hint for the inductive case: fix some element of the set and consider whether it belongs to the subset or not. In either case, reduce to the inductive hypothesis.

Answer 1

every set of n elements has 2ⁿ distinct subsets, for all n ? 0.

Proof:

Assume every k-element set has 2^k subsets.

We can prove the above statement by showing every (k+1)-element set has 2(k+1) subsets.
Now let A = {a1, a2, a3,..., ak, b}
so that A has (k+1) elements.
We partition P(A) into two subcollections
where the first contains subsets of A
which don’t have b in them and the second contains subsets of A which do have b in them.
Hence,
First Sub-collection
{}
{a1}
{a1, a2}
{a1, a2, ..., ak}

Clearly, the first collection is made up of all the
subsets from the k-element set {a1, a2, ..., ak} so it has 2k entries.

and Second Sub-collection
{b}
{a1, b}
{a1, a2, b}
{a1, a2, ..., ak, b}

By construction, the second collection will have the same number of entries as the first one, so it too must have 2^k entries.

Since the collection of all subsets of A has been partitioned into these two sub-collections, we seethat A must have
2^k + 2^k = 2^(k+1) subsets.

Hence Proved.