Results 1 to 5 of 5

Math Help - Proof by Induction

  1. #1
    Member
    Joined
    Apr 2008
    Posts
    123

    Proof by Induction

    Prove by induction that n! > (n/3)^n
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    Posts
    461
    Sorry, I made a mistake: the following doesn't help much.

    Quote Originally Posted by h2osprey View Post
    Prove by induction that n! > (n/3)^n
    n = 1:

    1! = 1 > (1/3)^1

    n -> n+1

    (n+1)! = (n+1)*n!   > (n+1)(n/3)^n > n (n/3)^n > n/3 * (n/3)^n = (n/3)^{n+1}
    Last edited by Rapha; January 8th 2009 at 08:08 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Apr 2008
    Posts
    123
    Quote Originally Posted by Rapha View Post
    n = 1:

    1! = 1 > (1/3)^1

    n -> n+1

    (n+1)! = (n+1)*n!   > (n+1)(n/3)^n > n (n/3)^n > n/3 * (n/3)^n = (n/3)^{n+1}
    Shouldn't it be ((n+1)/3)^{n+1}?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by h2osprey View Post

    Prove by induction that n! > (n/3)^n
    to complete your induction use the identity: (n+1) \left(\frac{n}{3} \right)^n=\frac{3}{(1+\frac{1}{n})^n}\left(\frac{n  +1}{3} \right)^{n+1} and this fact that: \left(1+ \frac{1}{n} \right)^n < e < 3.

    note that the solution is actually suggesting a stronger inequality, i.e. \forall n \in \mathbb{N}: \ n! > \left(\frac{n}{e} \right)^n.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Here is a non-induction proof:
    e^n = \sum_{k=0}^{\infty} \frac{n^k}{k!} > \frac{n^n}{n!}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2011, 07:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 12:09 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 by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 03:55 PM
  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