Number of subset from a sample space S is $2^n$? I am working my way through the statistical inference textbook and am stuck on this question:

*

*Suppose that a sample space $S$ has $n$ elements. Prove that the
number of subsets that can be formed from the elements of S is $2^n$
Taking examples for $n=2$:
$$n=2;\{\{\emptyset \}, \{a\}, \{b\}, \{a,b\}\};$$
And for $n=3$
$$n=3;\{\{\emptyset \}, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}\}$$
I do understand that any subset needs to be constructed by including and excluding elements of $n$ but I am not sure how to prove it. Just showing a few examples seems to not be enough.
What would be a formal proof of this simple fact?

Thanks everyone for the comments, so I tried to answer it myself.
Each element of $S$ can either be in the subet or not. For each elements we only have two options, all the subsets will therefore be represented by the multiplications of all the choices.
With the logic taken care of, here's the proof.
Proof by induction:

*

*Prove the base case:
$n=2$; possible subsets: $\{\{\emptyset\}, \{a\}, \{b\}, \{a,b\}\}$
$2.2=2^2=4$


*Assume that it's true for $k$:
$n=k$; possible subsets: $\{\{\emptyset\}, \{a\}, \{b\},..., \{a,b,....,k\}\}$
$2...2=2^k$


*Show that it's true for $k+1$:
$n=k+1$; possible subsets: $\{\{\emptyset\}, \{a\}, \{b\},..., \{a,b,....,k,k+1\}\}$
$2...2=2^k.2=2^{k+1}$
Which should be enough to prove the fact.
