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?
 A: 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.
A: Here are two combinatorial non-inductive proofs.
Suppose $S = \{a_1, \ldots, a_n\}$, where $a_1, \ldots, a_n$ are distinct.  The goal is to count the number of all the subsets of $S$.  In other words, to count the number of ways of constructing a subset of $S$.
Proof 1 (Apply the Rule of Sum principle).  This is based on the observation that a subset of $S$ can contain $i$ elements ($0 \leq i \leq n$), which are mutually exclusive. The number of subsets that contain $i$ elements is $\binom{n}{i}$, which is the number of ways of choosing $i$ elements from a pool of $n$ elements.    Therefore, by the rule of sum principle, the number of distinct subsets is given by:
\begin{align}
\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^n,
\end{align}
by Newton's binomial identity.
Proof 2 (Apply the Rule of Product principle).  This is based on the observation that constructing a subset is equivalent to assigning a binary label "on/off" to each of $\{a_1, \ldots, a_n\}$ such that a subset contains elements that are assigned with the "on" label.  Therefore, the number of subsets is equal to the number of ways of forming an $n$-long "on-off" sequence. As each element can either be "on" or "off" (i.e., $2$ ways of labeling one element) and there are $n$ elements in total, by the rule of product principle, there are
\begin{align}
\underbrace{2 \times 2 \times \cdots \times 2}_{n \text{ times}} = 2^n
\end{align}
ways of forming an $n$-long "on-off" sequence, i.e., there are $2^n$ subsets in total.
