elementary set theory - Prove that cardinality of power set of X is equal to $2^n$, $left | mathcal{P}(X) right | = 2^n$, using the principle of mathematical induction

I have this,

Having a set $X$ with $n$ objects. The power set of $X$ has $2^n$ elements, i.e. the number of subsets of $X$ is $2^n$.

We can consider the following statement:

$$P(n) : \left | \mathcal{P}(X) \right | = 2^{n}$$

i) P(0) is true, in fact $\left | \mathcal{P}(X) \right | = 1$ i.e. it contains the empty set as unique element.

ii) Assuming true for $P(n-1)$, we have to prove for $n$. We can consider the set X with $n$ objects as the union of two sets : $Y = \left \{ a_1, a_2, \ldots, a_{n-1} \right \}$ and $\left \{ a_{n}\right \}$, hence,

$$X = \left \{ a_1, a_2, \ldots, a_{n-1} \right \} \cup \left \{ a_{n}\right \}$$

For inductive hypothesis the numbers of subsets of $Y$ is $2^{n-1}$, so it is true, but, I have problems in proving the truth for $2^n$.

Please, can you help me? Many thanks!

Answer

All the elements of $P(X)$ either contain $a_n$ or they do not.

1) There are $2^{n-1}$ elements of $P(X)$ that do not contain $a_n$ by the induction hypothesis.

2) Take any of the elements that do not contain $a_n$ and add $a_n$ to it. You get a new unique subset. There are $2^{n-1}$ elements that can be created this way, again by the induction hypothesis. These are all the elements of $P(X)$ that contain $a_n$.

In total there are thus $2^{n-1}+2^{n-1}=2^n$ elements in $P(X)$, which proves the statement.