Base Case (n = 1): We must show that the inequality \(2^n\) ≥ \(n^2\) is true when n=1. When n=1, the left hand side of the inequality is \(2^1\), which equals 2. When n=1, the right hand side of the inequality is \(1^2\), which equals 1. Since the left hand side is larger than the right hand size, the base case holds.
Inductive Case (n ≥ 2): Let us assume that the inequality is true for n, i.e., that \(2^{\color{Red}n}\) ≥ \({\color{Red}n}^2\) holds (this is our inductive assumption!) and we will prove that the inequality is true for n+1, i.e., that \(2^{\color{Red}{n+1}}\) ≥ \(({\color{Red}{n+1}})^2\). Here, we will start with the expression \(2^{n+1}\) and, step by step, we will establish that \(2^{n+1}\) is greater than or equal to \((n+1)^2\):
\(\begin{array}{rll} 2^{n+1}&= 2 \cdot 2^n & \hspace{20pt}{\color{Blue}{\text{by algebra}}}\\ &\geq 2 \cdot n^2 & \hspace{20pt}{\color{Blue}{\text{by inductive assumption}}}\\ &= n^2 + n^2 & \hspace{20pt}{\color{Blue}{\text{by algebra}}}\\ &\geq n^2 + (2n + 1) & \hspace{20pt}{\color{Blue}{\text{since } n^2 ≥ (2n + 1)}}\\ &= (n + 1)^2 & \hspace{20pt}{\color{Blue}{\text{by algebra}}}\\ \end{array}\)
Thus, \(2^{n+1}\) ≥ \((n+1)^2\), and the inductive case holds. ■