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

    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:


    (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
    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


    and not

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook