Results 1 to 3 of 3

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

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    7

    Question 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?

    Thanks in advance,

    James
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    <br />
\begin{aligned}<br />
(n + 1)^{n+1} &= (n + 1)^n(n+1)\\<br />
&> n^n \cdot n\\<br />
&> 2^{n+1} \cdot n&&\text{because by IH, $n^n>2^{n+1}$}\\<br />
&> 2^{n+2}&&\text{because $n>2$}<br />
\end{aligned}<br />
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by jstephenson View Post
    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}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. quick question about inductive proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 17th 2009, 02:30 AM
  2. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: October 7th 2009, 01:09 PM
  3. Inductive Step...Confused when solving this equation?
    Posted in the Discrete Math Forum
    Replies: 15
    Last Post: March 2nd 2009, 06:59 PM
  4. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 28th 2008, 06:24 PM
  5. inductive proof question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 15th 2007, 05:22 AM

Search Tags


/mathhelpforum @mathhelpforum