# 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:

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:

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

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

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