Let
\(P(n)\) be the statement, “every set containing
\(n\) elements has
\(2^n\) different subsets.” We will show
\(P(n)\) is true for all
\(n \ge 1\text{.}\) Base case: Any set with 1 element
\(\{a\}\) has exactly 2 subsets: the empty set and the set itself. Thus the number of subsets is
\(2= 2^1\text{.}\) Thus
\(P(1)\) is true. Inductive case: Suppose
\(P(k)\) is true for some arbitrary
\(k \ge 1\text{.}\) Thus every set containing exactly
\(k\) elements has
\(2^k\) different subsets. Now consider a set containing
\(k+1\) elements:
\(A = \{a_1, a_2, \ldots, a_k, a_{k+1}\}\text{.}\) Any subset of
\(A\) must either contain
\(a_{k+1}\) or not. In other words, a subset of
\(A\) is just a subset of
\(\{a_1, a_2,\ldots,
a_k\}\) with or without
\(a_{k+1}\text{.}\) Thus there are
\(2^k\) subsets of
\(A\) which contain
\(a_{k+1}\) and another
\(2^{k+1}\) subsets of
\(A\) which do not contain
\(a^{k+1}\text{.}\) This gives a total of
\(2^k + 2^k = 2\cdot 2^k = 2^{k+1}\) subsets of
\(A\text{.}\) But our choice of
\(A\) was arbitrary, so this works for any subset containing
\(k+1\) elements, so
\(P(k+1)\) is true. Therefore, by the principle of mathematical induction,
\(P(n)\) is true for all
\(n \ge 1\text{.}\)
