Results 1 to 6 of 6

Thread: 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,577
    Thanks
    790
    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,577
    Thanks
    790
    2(k^3)(k+1) > 2(k+1)^3
    OK. I.e., you need to show that $\displaystyle k^4+k^3>k^3+3k^2+3k+1$, i.e., $\displaystyle k^4-3k^2-3k-1>0$ for $\displaystyle k\ge 7$.

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

    Where did we get so far? We can show that $\displaystyle k^4>7k^2$: indeed, $\displaystyle k^4-7k^2=k^2(k^2-7)>0$ for $\displaystyle k\ge7$. In turn, we showed that $\displaystyle 7k^2>3k^2+3k+1$ for $\displaystyle k\ge 7$. Therefore, $\displaystyle k^4-3k^2-3k-1>0$ for $\displaystyle 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
    4
    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 $\displaystyle n\ge\ 7$

    $\displaystyle n!>2n^3$

    If this causes the following to be true

    $\displaystyle (n+1)!>2(n+1)^3$

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

    Proof

    $\displaystyle (n+1)!=(n+1)n!$

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

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

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

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

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

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

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

    Since $\displaystyle (n+1)^2=n^2+2n+1$

    $\displaystyle 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 $\displaystyle k! \geq 2k^3$ for every integer $\displaystyle k\geq 7$. We show that $\displaystyle (k+1)! \geq 2(k+1)^3$. So we must begin with

    $\displaystyle k! \geq 2k^3$

    Multiplying through by $\displaystyle (k+1)$, we obatain

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

    Observe that


    $\displaystyle (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)$

    $\displaystyle = 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)$

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

    Therefore, by induction $\displaystyle n! \geq 2n^3$ for every integer $\displaystyle 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: Jan 31st 2011, 04:41 PM
  2. proof by induction ...
    Posted in the Calculus Forum
    Replies: 2
    Last Post: Aug 8th 2009, 02:07 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2009, 09:33 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 8th 2008, 01:20 PM
  5. Proof by Induction?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Sep 24th 2007, 07:57 AM

Search Tags


/mathhelpforum @mathhelpforum