Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Mathematical induction

  1. Feb 23, 2008 #1
    1. The problem statement, all variables and given/known data

    [tex]2^n>n , n\geq 1[/tex]


    2. Relevant equations



    3. The attempt at a solution

    [tex]n=1[/tex]

    [tex]2^1>1[/tex]

    [tex]2>1[/tex]

    [tex]n=k[/tex]

    [tex]2^k>k[/tex]

    [tex]n=k+1[/tex]

    [tex]2^k^+^1=2^k*2>2k=k+k>k+1[/tex]

    [tex]2^k^+^1>k+1[/tex]

    Ok, I don't understand the part k+k>k+1
    If I get k=1 (from the [tex]k\geq 1[/tex])
    1+1>1+1
    2>2 which is not actually correct. Any help?
     
  2. jcsd
  3. Feb 23, 2008 #2

    mjsd

    User Avatar
    Homework Helper

    what you should have is
    [tex]k+k\geq k+1, \quad k\geq 1[/tex]
    then your first ">" will give you the desire relationship
     
  4. Feb 23, 2008 #3
    It looked to me like you were on your way to solving this correctly, so my guess is that you've just misunderstood either what you're supposed to do (which happens a lot when people learn induction) or that you haven't recognized what you've done.

    Let's spell out what you've done:
    Okay, that's step 1: show that what you're trying to prove is true for one specific case (n=1). Now you go to step 2, i.e. show that if it's true for some value of n, say, n=k, then it must also be true for the next value, n=k+1.
    Okay, we've assumed that it's true for n=k ...
    Now here's where you lost me. You're attempting to show that for n=k+1 you get
    [tex]2^{k+1}>k+1[/tex],
    given your assumption that [tex]2^k>k[/tex].

    You've got that
    [tex]2^k^+^1=2^k*2[/tex]
    and since by assumption
    [tex]2^k>k[/tex]
    you know that
    [tex]2^k*2>k*2[/tex],
    which means (combining these expressions)
    [tex]2^k^+^1>k*2[/tex].
    So, the question boils down to this: is [tex]k*2>k+1[/tex], which would give you what you're trying to prove?

    Is it?

    (I still don't understand your question about the n=1 case, but maybe it's moot now...)
     
  5. Feb 23, 2008 #4
    Oh! Now I see what you were asking! You're not sure if you can make the final jump for the case k=1.

    Keep in mind that what you're really trying to show is that [tex]2^{k+1}>k*2[/tex] ... will that still be true in this case?
     
  6. Feb 23, 2008 #5
    This is standard principle for solving tasks like this. So, yes, will it be still true? As far as I know, it wouldn't be true. So it must be, [tex]k+k\geq k+1, \quad k\geq 1[/tex], which is not what my "book result" says. Maybe its their typo fault.
     
  7. Feb 23, 2008 #6
    I'm not sure I understand. The problem states that the relation should be true for [tex]n\geq1[/tex], so finding that the inductive relation works for [tex]k\geq1[/tex] is consistent with that, isn't it? In other words, you've shown that:
    1. The relation is true for n = 1.
    2. If the relation holds for some value of [tex]n=k[/tex], [tex]k\geq1[/tex], then it also hold for [tex]n=k+1[/tex].

    Doesn't that do what you want?
     
  8. Feb 24, 2008 #7
    Do you look the part k+k>k+1 ?? Try to do k=1, you'll get 1+1>1+1, which is not actually correct.
     
  9. Feb 24, 2008 #8

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    What I would do is use a separate induction:
    if n>1 then n+n> n+1.

    If n= 2 then n+n= 2+ 2= 4> 3= 2+ 1= n+1

    Assume that, for a fixed k> 1, k+ k> k+1

    Then (k+1)+ (k+1)= k+ k+ 2> (k+1)+ 2> (k+ 1)+ 1 because 2> 1.

    (k+ k[itex]\ge[/itex] k+ 1 is true for all positive integers.)
     
  10. Feb 24, 2008 #9
    Is it correct, like I wrote on the first post?
    Is it correct, if I write k+ k[itex]\ge[/itex] k+ 1?
     
  11. Feb 24, 2008 #10
    But shouldn't it be [tex]k\geq1[/tex], so [tex]k+k\geq[/tex] [tex]k+1[/tex] ?
     
  12. Feb 24, 2008 #11

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    That's what I said, isn't it? That k+ k[itex]\ge[/itex] k+ 1 for all positive integers?
     
  13. Feb 28, 2008 #12
    If we take, [tex]k+k\geq[/tex] [tex]k+1[/tex]
    Than it should be:
    [tex]2^k^+^1 \geq k+1[/tex]
    from:
    [tex]2^k^+^1=2^k*2>2k=k+k \geq k+1[/tex]
    which is not completely true.
    Because also
    [tex]2^k^+^1 > k+1[/tex] is correct.
     
  14. Mar 2, 2008 #13
    Any help?
     
  15. Mar 2, 2008 #14

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    If it is true that A> B then it is certainly true that A[itex]\ge[/itex] B!
     
  16. Mar 2, 2008 #15
    But we need to prove that A>B and not A[itex]\ge[/itex]B.
     
  17. Mar 2, 2008 #16

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Now, I understand. It was a typo error on my part.

    I had stated at the beginning that you could do a separate induction to prove "if n>1 then n+n> n+1" which has ">" and that was what I proved. Unfortunately, I then wrote "[itex]\ge[/itex]" in the last line when I didn't mean to.
     
  18. Mar 2, 2008 #17
    So, in my book, is not correct at all, right?
     
  19. Mar 2, 2008 #18

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    What are you referring to? It is true that for n any positive integer, 2n> n. What I have been talking about was the "part" of that I proved: If n> 1, then 2n= n+ n> n+ 1. In fact, what I started to prove, and then confused myself about, was that if n is any integer, 2n[itex]\ge[/itex] n+ 1.

    To prove THAT: If n= 1, 2n= 2= n+1 so it is true.

    If it is true for any k, then 2(k+ 1)= 2k+ 2> (2k+1)+ 1> 2k so 2(k+1)[itex]\ge[/itex](k+1)+ 1 and we are done.


    Now for your original problem (which has been going on long enough!):
    If n= 1, then 21= 2> 1.

    Assume that 2k> k for some k. Then 2k+1= 2(2k)> 2k [itex]ge[/itex] k+1 and we are done.
     
  20. Mar 3, 2008 #19
    But if we say that 2k+1= 2(2k)> 2k [itex]\ge[/itex] k+1
    then 2k+1 [itex]\ge[/itex] k+1,
    and what the original problem is 2k+1 > k+1
    Do you understand what I mean?
     
  21. Mar 6, 2008 #20
    Any help, please?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Mathematical induction
  1. Mathematical Induction (Replies: 17)

  2. Mathematical Induction (Replies: 3)

  3. Mathematical Induction (Replies: 15)

  4. Mathematical induction (Replies: 0)

Loading...