Paragraph

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{.}\)