Help with proof by induction please - see below!

Question

The power set of a finite set A, denoted P(A), is defined to be the set of all subsets
of A. For instance, if A = {1, 2}, then P(A) = {∅, {1}, {2}, {1, 2}}. Note that P(A) is
a set which contains sets as elements, and that the empty set, ∅, is a subset of all
sets.
Given that A contains n elements, conjecture a formula for the number of elements
in P(A) and prove it by induction.

Answer 1

By trying a few small sets, we see the following:

 

|A| = 0 ---> |P(A)| = 1

 

|A| = 1 ---> |P(A)| = 2

 

|A| = 2 ---> |P(A)| = 4

 

|A| = 3 ---> |P(A)| = 8

 

This evidence suggests that maybe, for a set with n elements, the power set will have 2ⁿ elements. We prove this by induction.

 

The base case is established by the observations above. Now, consider a set A with n elements, and add a single new element: call it z. Let's denote A ∪ {z} as set B, which has n+1 elements. We can enumerate the subsets of B, in pairs, as follows: any subset of A is a subset of B, and any subset of A, with z added, is a different subset of B. For every subset of A, we obtain precisely two subsets of B in this way, and every subset of B is accounted for in this enumeration. Thus, the number of subsets of B is precisely twice the number of subsets of A. So:

 

|P(B)| = (2)|P(A)| = (2)(2ⁿ) = 2ⁿ⁺¹,

 

as desired.