Results 1 to 4 of 4

Math Help - difficulty following proof by induction

  1. #1
    Member Jskid's Avatar
    Joined
    Jul 2010
    Posts
    160

    difficulty following proof by induction

    This is given as an example of proof by induction. Prove that n! > 2^n for all n >= 4

    n_0=4 and 4!=24>16=2^4. Thus n_0 is true. Now suppose that k >= 4 and the statement is true for n=k. Thus we suppose k! > 2^k We must prove that the statement is true for n=k+1; that is, we must prove that (k+1)! > 2^{k+1}. Now
    (k+1)!=(k+1)k!>(k+1)2^k
    using the induction hpothesis. Since k >= 4 certainly k+1 > 2 so (k+1)2^k>2 x 2^k = 2^{k+1}. We conclude that (k+1)! > 2^{k+1} as desired. By the principle of mathematical induction we conclude that n!>2^n for all integers n>=4

    I don't get the part after "certainly k+1>2". What happened to the factorial?
    Last edited by Jskid; November 17th 2011 at 08:12 PM. Reason: fixed typos
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2

    Re: difficulty following proof by induction

    It doesn't say that. It says k+1>2 which it is because k is at least 4. In fact, k+1>4, but all that's needed for the proof is k+1>2.

    Also you have a typo. That minus sign towards the end should be an equal sign.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Jskid's Avatar
    Joined
    Jul 2010
    Posts
    160

    Re: difficulty following proof by induction

    Ok but how does that show anything about (k+1)!?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    10,969
    Thanks
    1011

    Re: difficulty following proof by induction

    Quote Originally Posted by Jskid View Post
    Ok but how does that show anything about (k+1)!?
    You know \displaystyle (k + 1)! = (k + 1)k! > (k + 1)2^k and you have shown \displaystyle (k + 1)2^k > 2^{k + 1}.

    Therefore \displaystyle (k + 1)! > 2^{k + 1}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction (n^4 - 4n^2)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 18th 2011, 10:01 PM
  2. Replies: 6
    Last Post: June 6th 2010, 08:15 AM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. Induction Proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 17th 2009, 11:20 AM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum