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?
Best Answer
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.