Intermediate Example of the Principle of Weak Mathematical Induction

We will now look at an intermediate example of the principle of weak mathematical induction.

Example 1

Prove that $n^2 < 2^n$ for each positive integer $n \geq 5$.

Let $P(n)$ be the statement that $n^2 < 2^n$.

Base Step: The statement $P(5)$ says that $5^2 = 25 < 2^5 = 32$ which is true.

Induction Step: Suppose that for some $k \geq 5$, $P(k)$ is true, that is, $k^2 < 2^k$. We want to show that $P(k+1)$ is true, i.e., $(k+1)^2 < 2^{k+1}$. We have that:

(1)

\begin{align} \quad (k+1)^2 = k^2 + 2k + 1 \overset{I.H.} < 2^k + (2k + 1) \quad (*) \end{align}

To complete this proof we need to do another induction. Let $S(n)$ be the statement that $2n + 1 < 2^n$ for each $n \geq 5$ (this is actually true for each $n \geq 3$ but this is not needed in the proof above).

Base Step: The statement $S(5)$ says that $2(5) + 1 = 11 < 2^5 = 32$ which is true.

Induction Step: Suppose that for some $k \geq 5$, $S(k)$ is true, that is, $2k + 1 < 2^k$. We want to show that $P(k + 1)$ is true, i.e., $2(k + 1) + 1 < 2^{k+1}$. We have that:

(2)

\begin{align} \quad 2(k + 1) + 1 = 2k +1 + 2 \overset{I.H.}< 2k + 2 < 2^k + 2^k = 2^{k+1} \end{align}

So by the principle of mathematical induction, $S(n)$ is true for all $n \geq 5$.

Going back up to $(*)$ we have that:

(3)

\begin{align} \quad (k+1)^2 < 2^k + 2^k = 2^{k+1} \end{align}

So by the principle of mathematical induction, $P(n)$ is true for all $n \geq 5$.