Return to Answer

Although I am personally a fan of the answer laid out by @gunes (+1) for its simplicity, it is worth mentioning an alternative (and arguably more rigorous) method of proof.

The number of subsets of $S$ consisting of exactly $k$ elements is "n choose k", i.e.
$$\binom{n}{k} = \frac{n!}{k!(n-k)!}.$$

Thus the total number of subsets is given by

$$\begin{align*} |\mathcal B| &= \sum_{k=0}^n\binom{n}{k} \\[1.2ex] &= \sum_{k=0}^n\binom{n}{k}\times 1^k \times 1^{n-k} \\[1.2ex] &= (1+1)^n \\[1.2ex] &= 2^n \end{align*}$$ where the second to last equality is due to the binomial theorem.

Although I am personally a fan of the answer laid out by @gunes (+1) for its simplicity, it is worth mentioning an alternative method of proof.

The number of subsets of $S$ consisting of exactly $k$ elements is "n choose k", i.e.
$$\binom{n}{k} = \frac{n!}{k!(n-k)!}.$$

Thus the total number of subsets is given by

$$\begin{align*} |\mathcal B| &= \sum_{k=0}^n\binom{n}{k} \\[1.2ex] &= \sum_{k=0}^n\binom{n}{k}\times 1^k \times 1^{n-k} \\[1.2ex] &= (1+1)^n \\[1.2ex] &= 2^n \end{align*}$$ where the second to last equality is due to the binomial theorem.

Although I am personally a fan of the answer laid out by @gunes (+1) for its simplicity, it is worth mentioning an alternative (and arguably more rigorous) method of proof.

The number of subsets of $S$ consisting of exactly $k$ elements is "n choose k", i.e.
$$\binom{n}{k} = \frac{n!}{k!(n-k)!}.$$

Thus the total number of subsets is given by

$$\begin{align*} |S| &= \sum_{k=0}^n\binom{n}{k} \\[1.2ex] &= \sum_{k=0}^n\binom{n}{k}\times 1^k \times 1^{n-k} \\[1.2ex] &= (1+1)^n \\[1.2ex] &= 2^n \end{align*}$$ where the second to last equality is due to the binomial theorem.

Although I am personally a fan of the answer laid out by @gunes (+1) for its simplicity, it is worth mentioning an alternative (and arguably more rigorous) method of proof.

The number of subsets of $S$ consisting of exactly $k$ elements is "n choose k", i.e.
$$\binom{n}{k} = \frac{n!}{k!(n-k)!}.$$

Thus the total number of subsets is given by

$$\begin{align*} |\mathcal B| &= \sum_{k=0}^n\binom{n}{k} \\[1.2ex] &= \sum_{k=0}^n\binom{n}{k}\times 1^k \times 1^{n-k} \\[1.2ex] &= (1+1)^n \\[1.2ex] &= 2^n \end{align*}$$ where the second to last equality is due to the binomial theorem.

Although I am personally a fan of the answer laid out by @gunes (+1) for its simplicity, it is worth mentioning an alternative (and arguably more rigorous) method of proof.

The number of subsets of $S$ consisting of exactly $k$ elements is "n choose k", i.e.
$$\binom{n}{k} = \frac{n!}{k!(n-k)!}.$$

Thus the total number of subsets is given by

$$\begin{align*} |S| &= \sum_{k=0}^n\binom{k}{n} \\[1.2ex] &= \sum_{k=0}^n\binom{k}{n}\times 1^k \times 1^{n-k} \\[1.2ex] &= (1+1)^n \\[1.2ex] &= 2^n \end{align*}$$ where the second to last equality is due to the binomial theorem.

Although I am personally a fan of the answer laid out by @gunes (+1) for its simplicity, it is worth mentioning an alternative (and arguably more rigorous) method of proof.

The number of subsets of $S$ consisting of exactly $k$ elements is "n choose k", i.e.
$$\binom{n}{k} = \frac{n!}{k!(n-k)!}.$$

Thus the total number of subsets is given by

$$\begin{align*} |S| &= \sum_{k=0}^n\binom{n}{k} \\[1.2ex] &= \sum_{k=0}^n\binom{n}{k}\times 1^k \times 1^{n-k} \\[1.2ex] &= (1+1)^n \\[1.2ex] &= 2^n \end{align*}$$ where the second to last equality is due to the binomial theorem.