Thread: Proof by induction question - inductive step clarification?

Hi,

I'm doing some revision, and am asked to prove by induction:

$\displaystyle n^n > 2^{n+1} \text{ for all } n \geqslant 3$

The provided solution has the obvious base step (n = 3), the following hypothesis:

$\displaystyle \text{Let } n \geqslant 3 \text{ such that } n^n > 2^{n+1}$

and the following step:

$\displaystyle (n + 1)^{n+1} > n^n \cdot n >_{IH} 2^{n+1} \cdot n > 2^{n+2}$

Regrettably I can't see how the inductive step leads to prove the hypothesis, and so am wondering if someone would be kind enough to break it down for me?

Thanks in advance,

James

$\displaystyle
\begin{aligned}
(n + 1)^{n+1} &= (n + 1)^n(n+1)\\
&> n^n \cdot n\\
&> 2^{n+1} \cdot n&&\text{because by IH, $n^n>2^{n+1}$}\\
&> 2^{n+2}&&\text{because $n>2$}
\end{aligned}
$

Originally Posted by jstephenson

Hi,

I'm doing some revision, and am asked to prove by induction:

$\displaystyle n^n > 2^{n+1} \text{ for all } n \geqslant 3$

The provided solution has the obvious base step (n = 3), the following hypothesis:

$\displaystyle \text{Let } n \geqslant 3 \text{ such that } n^n > 2^{n+1}$

and the following step:

$\displaystyle (n + 1)^{n+1} > n^n \cdot n >_{IH} 2^{n+1} \cdot n > 2^{n+2}$

Regrettably I can't see how the inductive step leads to prove the hypothesis, and so am wondering if someone would be kind enough to break it down for me?

Thanks in advance,

James

Or

$\displaystyle (n+1)^{n+1}>2^{n+2}\;\;if\;\;n^n>2^{n+1}\;\;?$

Proof

$\displaystyle n^n>2^{n+1}\Rightarrow\ (n)n^n>(2)2^{n+1}$

since $\displaystyle n\ \ge\ 3$

$\displaystyle \Rightarrow\ n^{n+1}>2^{n+2}\Rightarrow\ (n+1)^{n+1}>2^{n+2}$