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!

Homework Help: 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