Intermediate Example of the Principle of Weak Mathematical Induction

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$.