1. Limited time only! Sign up for a free 30min personal 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!

Induction Proof

  1. Oct 8, 2015 #1
    1. The problem statement, all variables and given/known data

    Show that the statement holds for all positive integers n

    2n ≤ 2^n

    2. Relevant equations

    Axiom of induction:
    1 ∈ S and
    k ∈ S ⇒ k + 1 ∈ S

    3. The attempt at a solution

    Let S be set of integers
    2(1) ≤ 2^1, so S contains 1

    kS,
    2k ≤ 2^k

    I want to show k + 1 ∈ S,
    2k + 2(k+1) ≤ 2^k * 2^(k+1)

    The left side seems to make sense since
    =2k+2k+2
    =4k+2
    =2(k+1)

    I showed k + 1 ∈ S

    The right side i get
    =2^(k(k+1))

    Does this show k + 1 ∈ S ? To me 2k*2(k+1) makes sense because the next value of k can be calculated ?
     
  2. jcsd
  3. Oct 8, 2015 #2

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Actually the left side doesn't make sense.

    You need the left side to be 2(k+1), but you have 4k + 2, which is 2(2k+1).

    To correct that, notice that 2(k+1) = 2k + 2. Then ask yourself, "what needs to be added to 2k to get 2(k+1)?"
    You did not show this.
    I suspect that your statement of the Axiom of Induction is missing some details, particularly as concerns the description of the set S, including the nature of its elements.
     
  4. Oct 8, 2015 #3

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    For each n, Let P(n) denote the statement ##2n\leq 2^n##. You want to prove the statement "for all n, P(n)". This is equivalent to proving all of the infinitely many statements P(1), P(2), P(3),... But if you try to prove them one at a time, you will never be finished. So you use induction. The idea is that you can prove all of these statements by proving only the following two statements:

    P(1)
    For all k, if P(k) then P(k+1)

    Here you have made it sound like the goal is to prove that 1 is an integer. Your goal at this point should be to prove the statement P(1).

    Your goal here should be to show that for all k, if P(k) then P(k+1).

    I'm not sure what you're doing here. At this point, k is an arbitrary integer, and you're working under the assumption that P(k) holds. You want to prove P(k+1). So you should start by rewriting some part of the statement P(k+1) in a way that makes it easy to use the assumption P(k).
     
  5. Oct 8, 2015 #4

    RUber

    User Avatar
    Homework Helper

    1 is in S.
    Assume k is in S, i.e.
    ##2k\leq 2^k ##
    Manipulate 2(k+1) and 2^(k+1) to put them in terms of 2k and 2^k.
    Use something that looks like
    If ##A \leq B## and ##C \leq D ## then ## A+C\leq B+D##
    Knowing that k is at least 1 will help you draw your final conclusion.
     
  6. Oct 8, 2015 #5
    This makes it easier to understand using P(n)

    P(1) works because 2(1) ≤ 2^(1) so,

    for all k, P(k) ⇒ P(k + 1)
    2(k) ≤ 2^(k) ⇒ 2(k+1) ≤ 2^(k+1)

    I'm stuck at this point, I tried
    2(2(k+1)) ≤ 2^(2^(k+1)) ... I'm pretty sure this is incorrect

    wouldn't I get the same results as I did before?
    2(k+1)+2k ≤ 2^(k+1) + 2^k
     
    Last edited: Oct 8, 2015
  7. Oct 8, 2015 #6

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    That's statement P(1) alright, but you should also explain how you know that it's a true statement. (Yes, it's pretty trivial, but you're doing this problem to practice your proof writing skills).

    Right, that's what you want to prove next. So you assume that the inequality on the left holds, and use it to prove that the inequality on the right holds too.

    Is there a way to rewrite ##2(k+1)## so that the symbols 2 and k appear right next to each other? That's all you have to do to be able to use the assumption ##2k\leq 2^k##.

    Did you just add P(k) to P(k+1)? That would be an attempt that uses P(k+1) as an assumption. You can't use the statement that you're trying to prove.
     
    Last edited: Oct 8, 2015
  8. Oct 8, 2015 #7

    RUber

    User Avatar
    Homework Helper

    It seems like perhaps you don't understand the notation.
    k doesn't change. Initially it could be 1...since you have already shown this.
    ##2(1) \leq 2^1 ## is true. Does this imply that k+1=1+1 satisfies the relation?
    ## 2(2) \leq 2^2##? So far so good. So 2 satisfies the relation, so k might be 2...what about 2+1?
    ##2(2+1) \leq 2^{2+1}##?
    So for any k, you should be able to show that ##2(k+1) \leq 2^{k+1}## using basic algebra and the assumption that ##2k \leq 2^{k}##.
     
  9. Oct 8, 2015 #8
    2k+2 ? Is this all I have to do?

    How about the other side of the inequality.
    2^k?
     
  10. Oct 8, 2015 #9

    RUber

    User Avatar
    Homework Helper

    Think about what you are trying to do...
    You are saying "I know that ##2k \leq 2^k##, what can I say about ##2(k+1)## and ##2^{k+1}##?"
    All you have to build this proof off of is ##2k \leq 2^k##, k>1, and algebra.
    That is all you need.

    *hint* ##a^{b+c} = a^b a^c##
     
  11. Oct 8, 2015 #10
    So you're saying that
    I have work with what i know, 2k ≤ 2^k

    do stuff with algebra, when k>1

    then it will show that 2(k+1) ≤ 2^(k+1) ?
     
  12. Oct 8, 2015 #11

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Yes.
     
  13. Oct 8, 2015 #12

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yes, the rewrite ##2(k+1)=2k+2## is a good way to make it extremely easy to use the assumption that ##2k\leq 2^k##. The next step is to actually use that assumption.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Induction Proof
  1. Induction proof (Replies: 1)

  2. Proof By Induction (Replies: 2)

  3. Proof by induction (Replies: 1)

  4. Induction Proofs (Replies: 3)

  5. Proof by induction (Replies: 7)

Loading...