Chapter 9, Problem 73RE

Solution

To prove: The given statement is true or not for any positive integer using mathematical induction.

Given information :

The given statement is $2^{n-1}\le n!$ .

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

Explanation :

Conjecture:

Take $P_n$ to be statement $2^{n-1}\le n!$ .

Anchor step:

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

For $n=1$ ,

  $\begin{array}{r}{2}^{1-1}\stackrel{?}{=}1!\\ 1=1\end{array}$

Inductive hypothesis:

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

  $P_k:2^{k-1}\le k!$

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.

Proceed with the inductive hypothesis.

  $P_k:2^{k-1}\le k!$

Multiply both sides by 2,

  $\begin{array}{c}2\cdot 2^{k-1}\le 2k!\\ 2^k\le 2k!\end{array}$

Since $1\le k$ ,

  $\begin{array}{l}1\le k\\ 1+1\le k+1k!\\ 2\le k+1\\ 2^k\le 2k!\le \left(k+1\right)\cdot k!=\left(k+1\right)!\end{array}$

The statement is same as the statement $P_{k+1}$ , so $P_{k+1}$ is true.

So, if $P_n$ is true for $n=k$ , then it is also true for $n=k+1$ .

Conclusion:

As $P_n$ is true for $n=1$ and $P_k$ further implies $P_{k+1}$ , this means $P_n$ is true for $n=2$ , $n=3$ and so on.

By mathematical induction, $2^{n-1}\le n!$ is true for all positive integers $n$ .