Results 1 to 3 of 3

Math Help - Induction Proof n

  1. #1
    Junior Member
    Joined
    Jul 2011
    Posts
    34

    Induction Proof n

    Hi, so I need to prove that 2^n > n for all positive numbers. I'm not sure if this is the right place to post this (couldnt find anywhere for basic proofs, but this is for my college linear algebra/intro proof class).

    My attempt:

    2^(n+1) > n + 1
    Step 1:Since 2^(n+1) > n + 1 if 2^(n + 1) > 2(n+1) then 2^(n+1) > n + 1
    Step 2: 2^(n+1) > 2(n+1)
    Step 3: 2^n * 2 >2(n+1)
    Step 4: 2^n > n + 1
    Step 5: Since 2^n > n + 1. 2^n will be greater than n.

    Is this a good way to prove this?? I Feel like it's wrong/terrible verbose. Any suggestions or better ways to do so (without having to to do all the replacements)?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,319
    Thanks
    1238

    Re: Induction Proof n

    I expect you need to use induction for this. You are trying to prove \displaystyle \begin{align*} 2^n > n \end{align*} for all

    Base step:

    \displaystyle \begin{align*} n&= 1 \\ \\  2^1 &= 2 \\ \\ 2^1 &> 1  \end{align*}

    The statement is proved for the base step.

    Inductive step: Assume that \displaystyle \begin{align*} 2^k > k \end{align*}, then we have

    \displaystyle \begin{align*} 2^{k + 1} &= 2 \cdot 2^k \\ &> 2k \textrm{ since } 2^k > k \\ &> k + 1 \textrm{ since } 2k > k + 1 \textrm{ for all } k > 1 \end{align*}

    So the inductive step is proven. Therefore we have now proven \displaystyle \begin{align*} 2^n > n \end{align*} for all integer \displaystyle \begin{align*} n > 0 \end{align*}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2011
    Posts
    34

    Re: Induction Proof n

    Thanks for the prompt reply. Didn't even think of that.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by induction A u B = A + B - A n B
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 19th 2011, 06:19 PM
  2. proof by induction
    Posted in the Calculus Forum
    Replies: 2
    Last Post: May 9th 2009, 07:35 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  5. proof by induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: October 5th 2006, 06:54 AM

Search Tags


/mathhelpforum @mathhelpforum