I'm having trouble understanding the solution to this question from chapter 3 of the book "Essentials of Discrete Mathematics".
I just can't seem to see the relation between the mutually exclusive cases and the argument that $\mathcal{P}(X)$ has twice as many elements as $\mathcal{P}(X').$
$\mathbf{Example\; 3.5\;}$ Let $X$ be a finite set with $n$ elements. Find a recurrence relation $C(n)$ for the number of elements in the power set $\mathcal{P}(X)$.
$Solution:$ The base case is when $n = 0$ and $X$ is the empty set, in which case $\mathcal{P}(X) = \{\emptyset\}$, so $C(0) = 1.$ Now suppose $|X| = n$ for some $n > 0.$ Choose some element $x\in X$ and let $X' = X\;\backslash\;\{x\}.$ Then $X'$ has $n-1$ elements, so $|\mathcal{P}(X')|=C(n - 1).$ Furthermore, every subset of $X$ is either a subset of $X'$, or a subset of the form $U\cup\{x\}$, where $U \subseteq X'$, and these two cases are mutually exclusive. Therefore $\mathcal{P}(X)$ has twice as many elements as $\mathcal{P}(X').$ So $$ C(n) = \begin{cases} 1 & \text{ if $n = 0$ } \\ 2 \cdot C(n-1) & \text{ if $n>0$} \end{cases} $$
Every subset of X' is still a subset of X, so P(X) contains all the sets in P(X'). However, to each of these sets you can also add the element x, and the resulting sets will also be subsets of X, i.e. be in P(X), but are of course not in P(X'). So, you have twice as many subsets of X than of X'.
Example: suppose $X=\{1,2,3\}$ and we take out $3$, so $X' =\{1,2\}$
The subsets of X' are:
$\{\}$
$\{1\}$
$\{2\}$
$\{1,2\}$
These are all subsets of $X$ as well, but we can also add $3$ to each of them:
$\{3 \}$
$\{1,3\}$
$\{2,3\}$
$\{1,2,3\}$
So, exactly twice as many!