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!

Prove that 2n ≤ 2^n by induction.

  1. Jun 24, 2011 #1
    1. The problem statement, all variables and given/known data
    Prove and show that 2n ≤ 2^n holds for all positive integers n.


    2. Relevant equations
    n = 1
    n = k
    n = k + 1


    3. The attempt at a solution
    First the basis step (n = 1):
    2 (1) ≤ 2^(1) => 2 = 2.
    Ergo, 1 ϵ S.

    Now to see if k ϵ S:
    2 (k) ≤ 2^k
    But, k ϵ S implies k + 1 ϵ S:
    2(k + 1) ≤ 2^(k + 1)
    2k + 2 ≤ 2^k · 2^1

    Now, where do I go from here to prove this formally and that k + 1 ϵ S, thus proving that 2n ≤ 2^n holds for all positive integers n?
     
  2. jcsd
  3. Jun 24, 2011 #2
    Your wording puzzles me. In the induction step, you assume the result for n = k (i.e., assume [itex]2k \leq 2^k [/itex]), and try to show that this implies the result for n = k+1. So you need to show [itex] 2(k+1) \leq 2^{k+1}[/itex], using the assumption that [itex]2k \leq 2^k [/itex].

    I think the key is rewriting [itex] 2^{k+1} = 2^k \cdot 2[/itex] using addition. Can you see how to use the inductive assumption with this?
     
  4. Jun 24, 2011 #3
    That is exactly what I am struggling with. How would I apply the inductive process at this stage?
     
  5. Jun 24, 2011 #4

    Mentallic

    User Avatar
    Homework Helper

    So you have [tex]2(k+1)\leq 2\cdot 2^k[/tex]

    Divide through by 2 now and notice that if a<c and if you want to show that b<c, then all you need to do is show b<a.
     
  6. Jun 24, 2011 #5
    So, that leaves us with [tex] k + 1\leq 2^{k}[/tex]

    So, now I would have to prove [tex] k + 1\leq 2(k + 1)[/tex] correct?
     
  7. Jun 24, 2011 #6
    I would rewrite [itex]2^k \cdot 2[/itex] as [itex] 2^k + 2^k[/itex]. So now you're trying to show
    [tex]
    2k +2 \leq 2^k + 2^k
    [/tex]

    which should follow from the inductive assumption without too much trouble.
     
  8. Jun 24, 2011 #7

    Mentallic

    User Avatar
    Homework Helper

    Not quite.

    We have to show [tex]k+1\leq 2^k[/tex] and we know that [tex]2k\leq 2^k[/tex] by our assumption. Take the assumption as being [tex]a<c[/tex] and what we have to show is true as being [tex]b<c[/tex] and now show that [tex]b<a[/tex] therefore, [tex]b<a<c[/tex] thus [tex]b<c[/tex] so we have proven it true.

    You might even find spamiam's method to be simpler.

    p.s. I don't like that tex now makes new lines every time. I liked it the way it was before...
     
  9. Jun 25, 2011 #8
    But, this is exactly what was done in my book:
    From that step, that is, rewriting [tex]2^k \cdot 2[/tex] as [itex] 2^k + 2^k[/itex], they infer that [tex] k \geq 1[/tex] and write "this places k + 1 in S" and then proceed to rewrite it back as [tex]2\cdot 2^k[/tex] and then [tex]2^{k+1}[/tex]. But, if they came back to where they began then how did they formally prove it to begin with?
     
  10. Jun 25, 2011 #9
    So:
    [tex] k+1\leq 2k [/tex] and therefore [tex] k+1\leq 2k \leq 2^{k}[/tex] thus [tex] k+1\leq 2^{k}[/tex]

    So now it has been formally proven that k + 1 holds for all positive integers n? I actually prefer to learn both methods, as the more ways I have to approach a problem, the better. I agree about the LaTeX.
     
  11. Jun 25, 2011 #10
    They're just leaving out some steps. Since [itex] k \geq 1 [/itex], then [itex] 2 \leq 2^k [/itex]. By the inductive assumption, [itex] 2k \leq 2^k [/itex]. Putting these two facts together, what can you say about [itex] 2k+2 [/itex] and [itex] 2^k + 2^k [/itex]?

    And Mentallic, try using itex rather than tex if you want to make in-line math environment.
     
  12. Jun 25, 2011 #11

    Mentallic

    User Avatar
    Homework Helper

    Yep that's right :smile: You may want to throw one more line of working in, to show without a doubt that [itex]k+1\leq 2k[/itex] just by algebraic manipulation and referring back to the "for all positive integers n" in the question.

    Your book is saying that since [itex]2k\leq 2^k[/itex] then [itex]2k+2\leq 2k+2k\leq 2^k+2^k[/itex] by our inductive hypothesis. They just turn it back into what was needed to be proved, [itex]2(k+1)\leq 2^{k+1}[/itex]

    By the way, thanks for that spamiam. I thought itex was lost since I tried it at one point and it wasn't working.
     
  13. Jun 25, 2011 #12
    You need to use the fact that:
    [tex]
    k \ge 1
    [/tex]
    [tex]
    k + k \ge k + 1
    [/tex]
    [tex]
    2 k \ge k + 1
    [/tex]
     
  14. Jun 25, 2011 #13

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Do you realize that you haven't defined "S"?
    I take it you mean S to be the set of all positive integers, n, such that [itex]2n\le 2^n[/itex] but you need to say that.

    If S is as I said, no it doesn't. That's what you want to prove!

    Which is why you can say, above, that kϵ implies k+1ϵ S.

    [tex]2(k+1)= 2k+ 2\le 2^k+ 2[/tex].

    What I would do is a separate induction, as a lemma, to prove that [itex]2^n+1\le 2^{n+1}[/tex]
     
  15. Jun 25, 2011 #14
    Why can't you use calculus to prove this
     
  16. Jun 25, 2011 #15

    Mentallic

    User Avatar
    Homework Helper

    You could, but a proof by induction is simpler and also it is somewhat implied which technique you should be using by the part "holds for all positive integers n". It was also posted in the precalculus section.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prove that 2n ≤ 2^n by induction.
Loading...