Proof by induction question - inductive step clarification?

**jstephenson** · December 29th 2010, 07:32 AM

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?

Thanks in advance,

James

**emakarov** · December 29th 2010, 07:41 AM

$ \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} $

**Archie Meade** · December 29th 2010, 08:38 AM

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?

Thanks in advance,

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

Math Help - Proof by induction question - inductive step clarification?

LinkBack

Thread Tools

Display

Proof by induction question - inductive step clarification?

Similar Math Help Forum Discussions

quick question about inductive proof

Inductive proof

Inductive Step...Confused when solving this equation?

Inductive proof

inductive proof question

Search Tags