Chapter 9.5, Problem 52E

Solution

To prove : Using mathematical induction the statement $2^n\ge n^2$ for all $n\ge 4$ .

Given information :

The statement $2^n\ge n^2$ for all $n\ge 4$ .

Formula used :

Follow the steps to prove that the statement is true for any positive integer.

Anchor step: Prove that any statement $P_n$ is true for $n=1$ .

Inductive hypothesis: Assume $P_n$ is true for $n=k$ .

Inductive Step: Prove that $P_n$ is true for $n=k+1$ .

Proof :

Conjecture:

Take $P_n$ to be statement $P_n:2^n\ge n^2$ for all $n\ge 4$ .

Anchor step:

Prove that $P_n$ is true for $n=4$ .

  $\begin{array}{l}{2}^4\stackrel{?}{\ge }{4}^2\\ 16\ge 16\end{array}$

Inductive hypothesis:

Assume $P_n$ is true for $n=k$ . Replace $n$ with $k$ in $P_n$ .

  $P_k:2^k\ge k^2$

Inductive Step:

Prove that $P_n$ is true for $n=k+1$ . This means it is needed to be proved that $P_{k+1}$ must be true.

To prove that $P_{k+1}:a^{k+1}-1$ is divisible by $a-1$ , $a$ is positive integer.

Proceed with the inductive hypothesis.

  $P_k:2^k\ge k^2$

Multiply 2 on both sides

Now,

  $\begin{array}{c}2\cdot 2^k\ge 2k^2\\ 2^{k+1}\ge 2k^2\end{array}$

It is needed to prove $P_{k+1}$ , prove the following.

  $\begin{array}{c}2k^2\ge {\left(k+1\right)}^2\\ 2k^2\ge k^2+2k+1\\ k^2\ge 2k+1\end{array}$

To prove $k^2\ge 2k+1$ ,

For $k\ge 4$ ,

  $\begin{array}{c}{k}^2=k\cdot k\cdot 4k\\ =2k+2k\\ >2k+1\end{array}$

By mathematical induction, $P_n:2^n\ge n^2$ is true for all positive integers $n$ .