# Proof by Induction

1. Sep 8, 2011

### major_maths

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

2. Relevant equations
None.

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

Assume K$\in$Z (the set of integers) and P(K) is true.
Then (1+h)K$\geq$1+Kh+$\frac{K(K-1)}{2}$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+$\frac{(K+1)(K+1-1)}{2}$h2.

2. Sep 8, 2011

### daveb

You have that (1+h)K+1=(1+h)K(1+h) = P(K)(1+h), so see where that goes.

3. Sep 8, 2011

### stihl29

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.

4. Sep 8, 2011

### micromass

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

$$(1+h)^2=1+2h+h^2$$

and not

$$(1+h)^2=1+2h+3h^2$$