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 example

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

    We'll show that, if x => -1, then (1 + x)^n => 1 + nx for all positive integers n.

    Solution ...
    The text goes on to explain that if n = 1 is true, we assume n = k is true, and n = k + 1 is true.

    I understand everything until this part:

    Since

    (1 + x)^k+1 = (1 + x)^k(1 + x) => (1 + kx)(1 + x)

    How does 1 + nx where n = (k+1) become (1 + kx)(1 + x)?


    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. Sep 25, 2009 #2

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    "The text goes on to explain that if n = 1 is true, we assume n = k is true, and n = k + 1 is true."

    That shows a confused understanding of what your text is doing. You don't "assume n = k is true". You assume the proposition you are trying to prove is true for n = k. Then what you are trying to prove is that the proposition is true for k + 1.

    So your assumption is: (1 + x)k ≥ 1 + kx

    What you are trying to prove is: (1 + x)k+1 ≥ 1 + (k+1)x

    So you might start by multiplying both sides of your assumption by (1 + x). That will get you the left side of what you are trying to prove and it is your job to show what you have satisfies the right side.
     
  4. Sep 25, 2009 #3
    So I need to show that

    (1 + kx)(1 + x) = 1 + (k+1)x
     
  5. Sep 25, 2009 #4

    VietDao29

    User Avatar
    Homework Helper

    Well,

    (1 + x)k + 1 = (1 + x)k(1 + x), right?

    And from your Induction Hypothesis, we have: (1 + x)k >= 1 + kx, right? So, in conclusion:

    (1 + x)k + 1 = (1 + x)k(1 + x) >= (1 + kx)(1 + x).
     
  6. Sep 25, 2009 #5

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You can't show that because those aren't equal. But wouldn't ≥ do? Can you show that? Then write the full inequality up nice.
     
  7. Sep 25, 2009 #6
    Assume:
    (1 + x)^k >= (1 + kx)
    Then:
    (1 + x)^k+1 which equals to (1 + x)^k(1 + x) >= (1 + kx)(1 + x)
    since I multiplied (1 + x) to (1 + x)^k to make (1 + x)^k+1, I have to do the same to the other side.

    So I have to show that
    (1 + kx)(1 + x) >= 1 + (k+1)x

    1 + x + kx + kx^2 >= 1 + (k+1)x
    1 + (1 + k)x + kx^2 >= 1 + (k+1)x

    So the left side is +kx^2 more than the right side
     
  8. Sep 25, 2009 #7

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes. You now have the argument down and understand the steps. And you have what I would call a good "scratch paper" writeup. Having that all figured out, a nice writeup of the induction step argument you have would be to write:

    Assume (1 + x)k ≥ 1 + kx

    Then:

    (1 + x)(k+1) = (1 + x)k(1+x) ≥ (1 + kx)(1 + x)

    = 1 + x + kx + x2 = 1 +(k + 1)x + kx2

    ≥ 1 + (k + 1)x

    And you might want to note why it is important x > -1.
     
  9. Sep 25, 2009 #8
    Ok thanks for the help.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof by induction example
  1. Proof by Example? (Replies: 2)

  2. Proof by induction (Replies: 9)

  3. Proof by induction (Replies: 32)

  4. Induction Proof (Replies: 14)

  5. Proof by Induction (Replies: 6)

Loading...