# Proof by induction question - inductive step clarification?

• Dec 29th 2010, 06:32 AM
jstephenson
Proof by induction question - inductive step clarification?
Hi,

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

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

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

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

and the following step:

$(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?

James
• Dec 29th 2010, 06:41 AM
emakarov

\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}
• Dec 29th 2010, 07:38 AM
Quote:

Originally Posted by jstephenson
Hi,

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

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

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

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

and the following step:

$(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?

James

Or

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

Proof

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

since $n\ \ge\ 3$

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