Q:

Prove; Powerset Cardinality is $2^n$ - I have trouble understanding the prove.

I have trouble to understand the Induction step of the following prove. 
Can someone explain to me what happens in the Induction step 3. and 4.?
I don't really get the idea which is used, or it is simply not understandable enough written for me. 
Prove source: https://proofwiki.org/wiki/Cardinality_of_Power_Set
Prove:
For all $n \in \mathbb{N}$, let $P(n)$ be the proposition: $$|S| = n \implies |\mathcal{P}(S)| = 2^n $$ where $\mathcal{P}(S)$ is the powerset of $S$
Basis for the Induction:

 It holds $ S = \emptyset \Longleftrightarrow |S| = 0 $.
         Then  $\mathcal{P}(S) = \{\emptyset\}$, such that $|\mathcal{P}(S)| = 1 = 2^0$.
         From (1.) and (2.) it follows that proposition $P(0)$ holds.
    
Induction Hypothesis:
We need to show that, if $P(k)$ is true,  where $k \geq 2$, then it logically follows that $P(k+1)$ is true.
    So if this is our Induction Hypothesis: $$ |S| = k  \implies |\mathcal{P}(S)| = 2^k $$
    We need to show that: $$ |S| = k+1  \implies |\mathcal{P}(S)| = 2^{k+1} $$
Induction Step:

 Let $|S| = k+1$ and let $x \in S$.
  Consider the sets $S' = S \backslash \{x\}$, where $x$ is some element of $S$. We see that $|S'| = k$
         We now adjoin $x$ to all the subsets of $S'$. Counting the subsets of $S$, we have: all the subsets of $S'$
        and all the subsets of $S'$ with $x$ adjoined to them.
         From the Induction Hypothesis, there are $2^k$ subsets of $S'$.
        Adding $x$ to each of these, does not change their number, so there are another $2^k$ subsets of $S$, consisting of all the subsets $S'$ with $x$ adjoined to them.
         In total that makes $2^k + 2^k = 2 \cdot 2^k = 2^{k+1}$ subsets of $S$. 
        So $P(k) \implies P(k+1)$ and the result follows by the principle of mathematical induction.
         Therefore: $\forall n \in \mathbb{N} : |S| = n \implies |\mathcal{P}(S)| = 2^n$
    

A:

I'll illustrate with an example. Let's say we have a four element set $S = \lbrace 1, 2, 3, 4 \rbrace$. We know that, given any three element set, it has $2^3 = 8$ subsets.
Let's take out our $x$ from $S$ to form a three element set $S'$. I'm going to choose $x = 2$, for no particular reason, so $S' = \lbrace 1, 3, 4 \rbrace$. Under the induction hypothesis, we assume $S'$ has $8$ subsets, which are the following:
$$\lbrace \rbrace, \lbrace 1 \rbrace, \lbrace 3 \rbrace, \lbrace 4 \rbrace, \lbrace 1, 3 \rbrace, \lbrace 3, 4 \rbrace, \lbrace 1, 4\rbrace, \lbrace 1, 3, 4 \rbrace.$$
Note that the above list are all subsets of $S$; the fact that none of them contain $x = 2$ doesn't change this. In fact these are all the sets we can form without choosing $x = 2$. We can get the rest of the sets by adding in $x = 2$ into each of the sets, to get another $8$ subsets:
$$\lbrace 2 \rbrace, \lbrace 1, 2 \rbrace, \lbrace 2, 3 \rbrace, \lbrace 2, 4 \rbrace, \lbrace 1, 2, 3 \rbrace, \lbrace 2, 3, 4 \rbrace, \lbrace 1, 2, 4\rbrace, \lbrace 1, 2, 3, 4 \rbrace.$$
Try to convince yourself that the two collections of subsets form all subsets of $S'$. Every subset of $S$ that doesn't contain $2$ corresponds uniquely with a subset of $S$ that does contain $2$. We know there are $2^3$ of the former, and due to this relationship, there must also be $2^3$ of the latter. So, in total, we have $2^3 + 2^3 = 2 \cdot 2^3 = 2^4$ subsets.

