Proof by induction that a set containing $n$ elements has $2^n$ subsets

Question

Consider a set with $n$ elements; $A=\left\{x_1,x_2,...,x_n \right\}$

Collecting data:

$S_1=A\setminus \left\{\right\}$ : there's $C(n,0)$ way to form subset $S_1$

$S_2=A\setminus \left\{x_i\right\}$ : there's $C(n,1)$ ways to form subset $S_2$

$S_3=A\setminus \left\{x_i, x_j\right\}=A\setminus \left\{x_j, x_i \right\}$ : there's $C(n,2)$ ways to form subset $S_3$

$S_4=A\setminus \left\{x_i, x_j, x_k\right\}=\cdots=A\setminus \left\{x_k, x_j, x_i\right\}$ : $C(n,3)$ ways to form subset $S_4$

$\vdots$

$S_{n+1}=A\setminus\left\{x_1, x_2,..., x_n\right\}=\cdots=A\setminus\left\{x_n,..., x_2,x_1\right\}=$ $C(n,n) $ way...

Suspecting that the sum of all ways to form subsets, according to above, is:

$$\sum_{k=0}^{n}C(n,k)=\sum_{k=0}^{n}\binom{n}{k}=2^n \quad (*)$$

How does one go on with proving that (*) is true by induction?

I mean, how could one verify that it holds for a set containing $n+1$ elements?

Answer 1

Induction step:

Let it be that set $A$ has $n$ elements and has $2^n$ subsets.

Let it be that $B=A\cup\{x\}$ and $x\notin A$, hence has $n+1$ elements.

Then a subset of $B$ is a subset of $A$ (there are $2^n$) or is a set of the form $S\cup\{x\}$ where $S$ is a subset of $A$ (so again there are $2^n$ such sets).

We conclude that $B$ has $2\times 2^n=2^{n+1}$ subsets.