1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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...