Results 1 to 13 of 13
Like Tree1Thanks
  • 1 Post By Prove It

Math Help - Proof By Induction, n^3>2n+1

  1. #1
    Newbie
    Joined
    Oct 2012
    From
    South Dakota
    Posts
    15

    Proof By Induction, n^3>2n+1

    Hey all

    Having an issue with a proof by induction. Here is the question:
    n3>2n+1

    I got through the basis step, induction hypothesis step, but really struggled with understanding how to prove it. Have looked around at similar answers, but I believe I am just missing the key part of knowing what to do.

    (k+1)3>2(k+1)+1 - this is as far as I got.

    Any help would be greatly appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,318
    Thanks
    1238

    Re: Proof By Induction, n^3>2n+1

    Well first off, you don't write \displaystyle \begin{align*} ( k + 1) ^3 > 2(k + 1) + 1 \end{align*}, you write down ONE side of this and go through a series of steps to arrive at the other side.

    What you need to do is make the assumption that P(k) is true, i.e. that \displaystyle \begin{align*} k^3 > 2k + 1 \end{align*}. Then

    \displaystyle \begin{align*} (k + 1)^3 &= k^3 + 3k^2 + 3k + 1 \\ &> 2k + 1 + 3k^2 + 3k + 1 \\ &= 2k + 2 + 3k^2 + 3k \\ &= 2(k + 1) + 3k( k + 1) \\ &> 2(k + 1) + 1 \textrm{ since } k > 1 \implies 3k(k + 1) > 1 \end{align*}
    Thanks from RadMabbit
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2012
    From
    South Dakota
    Posts
    15

    Re: Proof By Induction, n^3>2n+1

    ^
    |
    |

    this guy....
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,318
    Thanks
    1238

    Re: Proof By Induction, n^3>2n+1

    Quote Originally Posted by RadMabbit View Post
    ^
    |
    |

    this guy....
    What value of n did you use in your base step?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2012
    From
    South Dakota
    Posts
    15

    Re: Proof By Induction, n^3>2n+1

    Quote Originally Posted by Prove It View Post
    What value of n did you use in your base step?
    Ah sorry, forgot to write it was for all integers n>=2, so I used 2.

    23>2*3+1
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,318
    Thanks
    1238

    Re: Proof By Induction, n^3>2n+1

    Quote Originally Posted by RadMabbit View Post
    Ah sorry, forgot to write it was for all integers n>=2, so I used 2.

    23>2*3+1
    Yes, that's fine. I realised at the last minute that it didn't hold for n = 1, so I thought I'd better ask.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Oct 2012
    From
    South Dakota
    Posts
    15

    Re: Proof By Induction, n^3>2n+1

    just got a little confused... where did the k^3 go?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,318
    Thanks
    1238

    Re: Proof By Induction, n^3>2n+1

    Quote Originally Posted by RadMabbit View Post
    just got a little confused... where did the k^3 go?
    In the inductive step you assume \displaystyle \begin{align*} k^3 > 2k + 1 \end{align*}.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Oct 2012
    From
    South Dakota
    Posts
    15

    Re: Proof By Induction, n^3>2n+1

    ok, you kinda lost me with your process. I feel like you just moved everything from one side to the other for no real reason....
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,318
    Thanks
    1238

    Re: Proof By Induction, n^3>2n+1

    Quote Originally Posted by RadMabbit View Post
    ok, you kinda lost me with your process. I feel like you just moved everything from one side to the other for no real reason....
    If \displaystyle \begin{align*} k^3 > 2k + 1 \end{align*} then \displaystyle \begin{align*} k^3 + 3k^2 + 3k + 1 > 2k + 1 + 3k^2 + 3k + 1 \end{align*}.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Oct 2012
    From
    South Dakota
    Posts
    15

    Re: Proof By Induction, n^3>2n+1

    Quote Originally Posted by Prove It View Post
    If \displaystyle \begin{align*} k^3 > 2k + 1 \end{align*} then \displaystyle \begin{align*} k^3 + 3k^2 + 3k + 1 > 2k + 1 + 3k^2 + 3k + 1 \end{align*}.
    Shouldnt it just be

    \displaystyle \begin{align*} k^3 + 3k^2 + 3k + 1 > 2k + 1 \end{align*}.

    Im confused about where you got all the other stuff, as I already incorporiated the k+1 into the 2n+1 at the start.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,318
    Thanks
    1238

    Re: Proof By Induction, n^3>2n+1

    Quote Originally Posted by RadMabbit View Post
    Shouldnt it just be

    \displaystyle \begin{align*} k^3 + 3k^2 + 3k + 1 > 2k + 1 \end{align*}.

    Im confused about where you got all the other stuff, as I already incorporiated the k+1 into the 2n+1 at the start.
    Even though that is a correct inequality, it won't help you out in this case. The reason why mine is correct is...

    \displaystyle \begin{align*} k^3 &> 2k + 1 \\ k^3 + 3k^2 &> 2k + 1 + 3k^2 \\ k^3 + 3k^2 + 3k &> 2k + 1 + 3k^2 + 3k \\ k^3 + 3k^2 + 3k + 1 &> 2k + 1 + 3k^2 + 3k + 1 \end{align*}

    This is the whole principle of mathematical induction. You make an assumption, then SUBSTITUTE THAT ASSUMPTION and do some algebraic manipulation to get what you need.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,279
    Thanks
    671

    Re: Proof By Induction, n^3>2n+1

    just so it's 100% clear.

    the "general shape" of an induction proof is:

    P(n0) is true. (here, n0 represents the "base case").

    if P(k) is true, then P(k+1) is true (no matter "what" natural number k is).

    therefore, P(n) is true for all natural numbers n ≥ n0.

    ********

    here, P(n) means: n3 > 2n+1

    since P(1) translates to: 1 > 3 (which is false), we cannot use n0 = 1.

    P(2) translates to: 8 > 5, which IS true, so perhaps n0 = 2 is a reasonable place to start.

    now for the "P(k) implies P(k+1)" step.

    if P(k) was true (that is: assume for the time being that it is), then:

    k3 > 2k+1.

    therefore:

    (k+1)3 = k3 + 3k2 + 3k + 1 > (2k+1) + 3k2 + 3k + 1.

    what we WANT to show is:

    (k+1)3 > 2(k+1) + 1 = 2k + 3.

    if we knew that 3k2 + 3k - 1 > 0, then we would have:

    (k+1)3 > (2k+1) + 3k2 + 3k + 1 = 2k + 3 + 3k2 + 3k - 1 > 2k + 3 + 0 = 2k + 3, by transitivity of ">".

    now 3k2 + 3k - 1 > 0 is the same as:

    3k2 + 3k > 1, or:

    (3k)(k+1) > 1. now, we know that we are only considering k > 1, so (3k)(k+1) > (3k)(2) > (3)(2) = 6 > 1.

    so since for any k > 1, (3k)(k+1) > 1, 3k2 + 3k - 1 > 0.

    (if we really wanted to punish ourselves, we could prove THIS by induction as well. we'd probably have to use more letters to avoid confusion).

    so IF k3 > 2k + 1, THEN it follows that (k+1)3 = 2k + 3 + (3k2 + 3k - 1) > 2k + 3 = 2(k+1) + 1.

    thus we can now apply to principle of induction to conclude that for ALL n ≥ 2:

    n3 > 2n + 1.

    *************

    as one might guess, one really doesn't "need" induction to prove this:

    suppose n ≥ 2.

    then n3 = n(n2) ≥ 2(n2) = 2(n)(n) = n2 + n2 > n2 + n

    (since n ≥ 2, so n > 1, so n2 = (n)(n) > (n)(1) = n),

    ≥ n2 + 2 > n2 + 1 = (n)(n) + 1 ≥ 2n + 1.
    Last edited by Deveno; October 4th 2012 at 09:41 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Induction proof?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 4th 2009, 08:26 AM
  2. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  3. Proof by Induction
    Posted in the Algebra Forum
    Replies: 4
    Last Post: August 27th 2008, 10:09 AM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  5. Proof By Induction #2
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 19th 2007, 03:08 PM

Search Tags


/mathhelpforum @mathhelpforum