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?

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.
