Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By johnsomeone

Math Help - Proof by Induction

  1. #1
    Newbie
    Joined
    Oct 2012
    From
    London
    Posts
    3

    Proof by Induction

    Hi, can someone help me prove this inequality by Induction

    The inequality is: n! ≥ 2n-1 for all natural numbers n

    Thank You
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    Re: Proof by Induction

    1) Define the statement that you'll prove by induction holds for every n:

    \text{Statement(n) is }"n! \ge 2^{n-1}".

    2) Show Statement(1) is true.

    3) ASSUME Statement(k) is true for some k >=1. From that algebracially manipulate it so that you can show that Statment(k+1) must also be true.

    It should look like this:

    \text{ASSUME } k! \ge 2^{k-1} \text { for some integer } k \ge 1.

    \text{Then ... (insert your algebra here - look at the final result you're trying to get to)... }

    \text{Therefore }(k+1)! \ge 2^{k}.

    4) 1-3 completes the proof by induction:
    You've shown Statement(1) is true by #2,
    and, by #3, you've shown that if Statement(k) is true, then Statement(k+1) is true.
    Therefore, you've proven Statement(n) is true for all n>=1.
    Last edited by johnsomeone; October 29th 2012 at 11:46 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2012
    From
    London
    Posts
    3

    Re: Proof by Induction

    Can you please show me the algebra that occurs at step
    "Then ... (insert your algebra here - look at the final result you're trying to get to)

    Thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    Re: Proof by Induction

    I'll give you a huge hint.

    You have k! \ge 2^{k-1} \text{ for some } k \ge 1.

    You want to manipulate that to show that you also have that (k+1)! \ge 2^{k}.

    What do you have to do to each side of the original inequality to get to this desired outcome?

    You'll use that, since k \ge 1, \text{ you know that } k+1 \ge 2.
    Thanks from edexcelgce
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 9th 2010, 05:32 PM
  2. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  3. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM
  4. Induction Proof.........
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 14th 2008, 09:48 PM
  5. Induction proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 14th 2008, 04:55 PM

Search Tags


/mathhelpforum @mathhelpforum