Results 1 to 6 of 6

Math Help - Proof by Induction

  1. #1
    Newbie
    Joined
    Mar 2010
    Posts
    2

    Proof by Induction

    Can somebody help me prove n! > 2n^3 where n>=7 by induction

    thanks!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    Check the base case first. Then find out how both sides (i.e., n! and 2n^3) change when n grows by 1. I.e., compare (n+1)! - n! and 2(n+1)^3 - 2n^3 and try proving that the first change is greater than the second.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2010
    Posts
    2
    I am at the point to prove

    2(k^3)(k+1) > 2(k+1)^3

    but no idea what to do now

    can someone help pls
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    2(k^3)(k+1) > 2(k+1)^3
    OK. I.e., you need to show that k^4+k^3>k^3+3k^2+3k+1, i.e., k^4-3k^2-3k-1>0 for k\ge 7.

    As a general idea, in a polynomial, a higher degree trumps all lower ones, regardless of coefficients, when k is large. So, eventually k^4 will dominate 3k^2+3k+1. A usual way to show this is to find an upper bound of 3k^2+3k+1 and to show that k^4 will dominate even this upper bound. To obtain an upper bound, note again that k^2 will dominate k and 1. So replace 3k by 3k^2 and 1 by k^2: 3k^2+3k+1<3k^2+3k^2+k^2=7k^2. (You need to show that this is true for k\ge 7.)

    Where did we get so far? We can show that k^4>7k^2: indeed, k^4-7k^2=k^2(k^2-7)>0 for k\ge7. In turn, we showed that 7k^2>3k^2+3k+1 for k\ge 7. Therefore, k^4-3k^2-3k-1>0 for k\ge 7, which is what we need.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by Ali93 View Post
    Can somebody help me prove n! > 2n^3 where n>=7 by induction

    thanks!!
    Prove the following for n\ge\ 7

    n!>2n^3

    If this causes the following to be true

    (n+1)!>2(n+1)^3

    then we only need test for n=7 to discover if the hypothesis is true or not.

    Proof

    (n+1)!=(n+1)n!

    (n+1)n!>2(n+1)^3 ? n\ge\ 7

    n!>2(n+1)^2 ? n\ge\ 7

    If n!>2n^3 then if 2n^3>2(n+1)^2 then n!>2(n+1)^2\ \Rightarrow\ (n+1)!>2(n+1)^3

    2n^3>2(n+1)^2 ? n\ge\ 7

    n^3>(n+1)^2 ? n\ge\ 7

    n^3\ge\ 7n^2,\ n\ge\ 7

    7n^2\ge\ n^2+2n^2+4n^2

    Since (n+1)^2=n^2+2n+1

    n^2+2n^2+4n^2\ge\ n^2+2n+1,\ n\ge\ 7
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Sep 2009
    Posts
    502
    I am skipping the basis step, but jumping straight to the inductive step.

    Here we go:

    Assume k! \geq 2k^3 for every integer k\geq 7. We show that (k+1)! \geq  2(k+1)^3. So we must begin with

    k! \geq 2k^3

    Multiplying through by (k+1), we obatain

    (k+1)n! \geq 2k^3(k+1).

    Observe that


    (k+1)!\geq 2(k^4+k^3)=2(k^2 \cdot k^2+k^3)\geq 2(k^3+7^2 \dot k^2)=2(k^3+3k^2+46k^2)

    = 2(k^3+3k^2+46k \cdot k)\geq 2(k^3+3k^2+46\cdot 7 \cdot k)=2(k^3+3k^2+3 \cdot k+319k)

    \geq 2(k^3+3k^2+319\cdot 7)>2(k^3+3k^2+3k+1)=2k(k+1)^3

    Therefore, by induction n! \geq 2n^3 for every integer n \geq 7
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by induction
    Posted in the Algebra Forum
    Replies: 13
    Last Post: January 31st 2011, 05:41 PM
  2. proof by induction ...
    Posted in the Calculus Forum
    Replies: 2
    Last Post: August 8th 2009, 03:07 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM
  5. Proof by Induction?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: September 24th 2007, 08:57 AM

Search Tags


/mathhelpforum @mathhelpforum