Results 1 to 13 of 13

Math Help - Induction

  1. #1
    Super Member
    Joined
    Jun 2008
    Posts
    829

    Induction

    How can I prove by induction that:

    n^2 > 3n for all n>=4

    I do:
    n=k
    P(k) = k^2 > 3k
    P(k+1) = (k+1)^2 > 3(k+1)

    How to solve
    P(k) --> P(k+1) to prove that P(n) is truth ???
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    (k+1)^2 = k^2 + 2k + 1 > 3k + 2k + 1 = 5k + 1

    Also, writing P(k) = k^2 > 3k is syntactically wrong -- P(k) is a proposition, not a number.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jun 2008
    Posts
    829
    Why (k+1)^2 > 3k+2k+1 ??
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Use the induction hypothesis - k^2 > 3k
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Jun 2008
    Posts
    829
    OK. But I not understand why
    K^2 > 3k
    (k+1)^2 > 3(k+1) ---Why you used 3k+2k+1 ???
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    (k+1)^2 = k^2 + 2k + 1
    k^2 > 3k \Rightarrow k^2 + 2k + 1 > 3k + 2k + 1
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Jun 2008
    Posts
    829
    I not understand why 3k+2k+1 if 3(k+1) = 3k+3 not 3k+2k+1
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    It's an intermediate step..
    Do you understand why k^2 + 2k + 1 > 3k + 2k + 1?
    If yes, then my argument is

    k^2 > 3k \Rightarrow (k+1)^2 =k^2 + 2k + 1 > 3k + 2k + 1 \overbrace{ > }^{k > 1} 3k + 2 + 1 = 3k + 3 = 3(k+1).
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Jun 2008
    Posts
    829
    I know that k^2+2k+1 > 3k+2k+1


    From where did 3k+2k+1 ?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Why does it matter? I don't really understand what's your difficulty. Can you tell me what part you don't understand of my last line in the last post?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    Jun 2008
    Posts
    829
    What you did was take an any expression to prove that (k+1)^2 > 3k + 3 ?

    For example

    Prove that 2^{2n} -1 is divisible by 3

    I do:
    2^{2k} - 1 = 3m
    2^{2k} = 3m + 1
    2^{2k+2} = 12m+4
    2^{2k+2} -1 = 3(4m+1)

    4m + 1 is divisible by 3 then 2^{2n} - 1 also divisible by 3

    Correct ?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by Apprentice123 View Post
    What you did was take an any expression to prove that (k+1)^2 > 3k + 3 ?
    I don't understand your question. Can you rephrase?

    For example

    Prove that 2^{2n} -1 is divisible by 3

    I do:
    2^{2k} - 1 = 3m
    2^{2k} = 3m + 1
    2^{2k+2} = 12m+4
    2^{2k+2} -1 = 3(4m+1)

    4m + 1 is divisible by 3 then 2^{2n} - 1 also divisible by 3

    Correct ?
    That is correct, but you might want to say where you're using the induction hypothesis.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member
    Joined
    Jun 2008
    Posts
    829
    OK. Thank you
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  2. Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 11th 2010, 02:08 AM
  3. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 19th 2008, 05:12 PM

Search Tags


/mathhelpforum @mathhelpforum