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!

Proof by Induction

  1. Sep 8, 2011 #1
    1. The problem statement, all variables and given/known data
    Prove that for any positive h and any integer n[itex]\geq[/itex]0, (1+h)n[itex]\geq[/itex]1+nh+[itex]\frac{n(n+1)}{2}[/itex]h2.


    2. Relevant equations
    None.


    3. The attempt at a solution
    I proved that P(0) is true (1[itex]\geq[/itex]1). The rest of the proof goes as follows:

    Assume K[itex]\in[/itex]Z (the set of integers) and P(K) is true.
    Then (1+h)K[itex]\geq[/itex]1+Kh+[itex]\frac{K(K-1)}{2}[/itex]h2.
    Then (1+h)(K+1) = (1+h)K+(1+h)1...

    I can't figure out how to relate that part to the final part of P(K+1), which is 1+(K+1)h+[itex]\frac{(K+1)(K+1-1)}{2}[/itex]h2.
     
  2. jcsd
  3. Sep 8, 2011 #2
    You have that (1+h)K+1=(1+h)K(1+h) = P(K)(1+h), so see where that goes.
     
  4. Sep 8, 2011 #3
    I'm working on the same problem, to show P(k+1) I set it up the same way

    but then we can use our inductive hypothesis

    (1+x)^(k+1) >= (1+kx+(1/2)*k(k-1)*x^2)(1+x)

    My question is, i've wrestled with the algebra for a little while now and for some reason in my notes i had P(K) set to:

    1+kx+(1/2)*k(k+1)*x^2

    (where the 1 in k(k+1) is positive instead of negative) I think my professor did the problem with k+1 instead of k-1. But i thought from teh inductive hypothesis the term is k(k-1) NOT k(k+1) because k+1 is what we get from P(k+1) that is what we get from the substitution???

    I know there will be left over terms but i keep getting k(k-1)/2 instead of k(k+1)/2.
     
  5. Sep 8, 2011 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    I believe you are correct. It has to be n(n-1) instead of n(n+1).

    This is seen by picking n=2, then

    [tex](1+h)^2=1+2h+h^2[/tex]

    and not

    [tex](1+h)^2=1+2h+3h^2[/tex]
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof by Induction
  1. Proof by induction (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...