If you find any mistakes, please make a comment! Thank you.

## Using the principle of mathematical induction to show inequalities II

Solution:

### Part a

If $n=1$, $2^1=2$ and $1^2=1$. True!
If $n=2$, $2^2=4$ and $2^2=4$. False!
If $n=3$, $2^3=8$ and $3^2=9$. False!
If $n=4$, $2^4=16$ and $4^2=16$. False!
If $n=5$, $2^5=32$ and $5^2=25$. True!
If $n=6$, $2^6=64$ and $6^2=36$. True!

We probably should guess that $2^n>n^2$ is true for all integers $n\ge 5$.

### Part b

The $n$-th proposition is
$$P_n: \quad 2^n> n^2.$$ Clearly, $P_5$ is true as we checked in Part a. We have the induction basis.

Now we assume $P_n$ is true (here we assume that $n\ge 5$), that is $2^n> n^2$. We would like to show $P_{n+1}$ is true based on $P_n$. Note that $n\ge 5$, we have
\label{eq:1-9-1}
n^2\ge 5n>3n\ge 2n+1.
Therefore
\begin{align*}
2^{n+1}=&\ 2\cdot 2^n> 2\cdot n^2\\
=&\ n^2+n^2>n^2+2n+1=(n+1)^2.
\end{align*} Here in the last inequality we used \eqref{eq:1-9-1}. Therefore $P_{n+1}$ is true if $P_n$ is true. By the principle of mathematical induction, we make the conclusion that $P_n$ is true for all positive integers $n$.