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!

Proof by induction question

  1. Sep 25, 2009 #1
    1. The problem statement, all variables and given/known data

    Show that the statement holds for all positive integers n.

    1+2n <= 3^n


    2. Relevant equations



    3. The attempt at a solution

    n = 1
    1+2 <= 3

    n = k
    1+2k <= 3^k

    n = (k+1)

    1+2(k+1) <= 3^(k+1)
    2k + 3 <= (3)(3^k)

    Not sure what to do now

    2k/3 + 1 <= 3^k
     
  2. jcsd
  3. Sep 25, 2009 #2

    VietDao29

    User Avatar
    Homework Helper

    Hint:

    Use your Induction Hypothesis (i.e, 1 + 2k <= 3k) to move on.

    Remember that, you are trying to prove: 1 + 2(k+1) <= 3k + 1.

    So: 1 + 2(k+1) = 2k + 3 = 2k + 1 + 2 <= ...
     
  4. Sep 25, 2009 #3
    Assume:
    3^k >= 1 + 2(k+1)
    Then:
    3^(k+1) = 3^k(3) >= (1 + 2(k+1))(3)

    Then to proof it (1 + 2(k+1))(3) >= 1 + 2(k+1)

    (1 + 2k + 2)(3) >= 1 + 2k + 2
    6k + 9 >= 2k + 3
    3(2k + 3) >= 2k + 3

    Is that right??
     
  5. Sep 25, 2009 #4

    VietDao29

    User Avatar
    Homework Helper

    No, your assumption is incorrect. :( What you should have assumed is:

    3k >= 1 + 2k

    NOT

    3k >= 1 + 2(k + 1)

    Let's try to do it again then.
     
  6. Sep 25, 2009 #5
    Assume:
    3k >= 1 + 2k

    Then:
    3k+1 = 3k(3) >= (3)(1+2k)

    Proof that:
    3(1+2k) >= (1 + 2k)
     
  7. Sep 26, 2009 #6

    VietDao29

    User Avatar
    Homework Helper

    Yup. And what's left is just to prove that 3(1+2k) >= (1 + 2k). Note that we already have k >= 0.

    How can you go about proving the above inequality?
     
  8. Sep 26, 2009 #7
    If k >= 0 then (1 + 2k) is > 0.
    Let a be (1 + 2k)
    3a >= a
     
  9. May 25, 2011 #8
    can someone pls help to proof the following by induction:
    A^n=P D^n P^(-1)
     
  10. May 25, 2011 #9

    gb7nash

    User Avatar
    Homework Helper

    You might want to start your own thread.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof by induction question
  1. Induction proof (Replies: 1)

  2. Proof By Induction (Replies: 2)

  3. Proof by induction (Replies: 1)

  4. Proof by Induction (Replies: 3)

Loading...