Exponential versus linear growth
An Introduction to Real Analysis
2025-09-28
Prove by induction that \(2^n > n\) for all \(n \in \symbb{N}\).
Informally, doubling leads to faster growth than adding one. Formalizing this idea requires two lemmata.
Lemma 1 For all \(n \in \symbb{N}\), \(2^n > 1\).
Proof. By induction. Since \(2^1 = 2 > 1\), the statement \(P(1)\) is true.
Next assume that \(P(n)\) is true, so \(2^n > 1\). By Proposition 1.1.2 from Katznelson and Katznelson (2024, 2) the inequality is preserved when both sides are multiplied by \(2\): \[\begin{align*} 2^{n + 1} &= 2 \cdot 2^n\\[0.75em] &> 2 \cdot 1\\[0.75em] &= 2\\[0.75em] &> 1. \end{align*}\] By transitivity of the linear order, \(2^{n + 1} > 2\) and \(2 > 1\) together imply that \(2^{n + 1} > 1\), so \(P(n + 1)\) is true. \(\blacksquare\)
Lemma 2 For \(a, b, c, d \in \symbb{N}\), if \(a > c\) and \(b > d\) then \(a + b > c + d\).
Proof. By the definition of the linear order on \(\symbb{N}\) given in Section 1.1.2 from Katznelson and Katznelson (2024), \(a = c + k\) and \(b = d + l\) for some \(k, l \in \symbb{N}\). Using associativity and commutativity of addition, \[\begin{align*} a + b &= (c + k) + (d + l)\\[0.75em] &= (c + d) + (k + l), \end{align*}\] whence \(a + b > c + d\). \(\blacksquare\)
Consistent with intuition, the proof for the exercise will involve doubling the left-hand side of \(2^n > n\) and adding \(1\) to the right-hand side, and observing that the inequality still holds.
Proof (Exercise 1.1.2). Since \(2^1 = 2 > 1\), the statement \(P(1)\) is true.
Next assume that \(P(n)\) is true, so \(2^n > n\). By Lemma 1, \(2^n > 1\). By Lemma 2, \[\begin{align*} 2^{n + 1} &= 2 \cdot 2^n\\[0.75em] &= 2^n + 2^n\\[0.75em] &> n + 1, \end{align*}\] so \(P(n + 1)\) is true. \(\blacksquare\)
This exercise is related to the O-notation that is used to characterize the behavior of functions as their arguments grow. Given functions \(f \colon \symbb{N}\to \symbb{R}\) and \(g \colon \symbb{N}\to \symbb{R}\), Aho and Ullman (1995, 97) write that \(f(n)\) is \(\symup{O}(g(n))\) if there exist \(n_0 \in \symbb{N}\) and \(c > 0\) such that for all \(n \geq n_0\), \(f(n) \leq cg(n)\). Because \(n < 2^n\) for all \(n \in \symbb{N}\), taking \(n_0 = c = 1\) shows that \(n\) is \(\symup{O}(2^n)\).