Induction Proof with Inequalities

Date: 07/03/2001 at 10:37:21
From: Jay Krueger
Subject: Math Induction

Hello,

I've been trying to solve a problem and just really don't know if my
solution is correct. I have a really hard time doing these induction
problems when inequalities are involved. I was hoping you could help
me solve this. 

The question is this:  

Prove by induction that (1 + x)^n >= (1 + nx), where n is a 
non-negative integer.

Thank you for your time.

Date: 07/03/2001 at 15:59:30
From: Doctor Ian
Subject: Re: Math Induction

Hi Jay,

Let's _assume_ that it holds for n = k. That is, for some k, it's true 
that 

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

What happens for the next value of n, i.e., n = (k+1)? 

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

              >= (1 + kx + x)

              >= (1 + kx) + x

So increasing the value of n by 1 adds s to the right side of the
inequality. What does it do to the left side?  

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

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

So increasing the value of n by 1 multiplies the left side of the 
equation by (1+x).  

Now there are two things left to do. The first is to show that (or
explain the conditions under which) something multiplied by (1+x) is 
greater than the same thing plus x:

  alpha * (1+x) >= alpha + x

Once you've done that, you need to show that the inequality holds for 
the smallest value of n (in this case, n = 1),

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

which should be pretty easy to do.

The general idea is to show that if it works for n = k, then it also 
works for n = k+1; and then to show that it works for n = 1. (Since it 
works for n = 1, it must also work for n = 2; and since it works for 
n = 2, it must also work for n = 3; and so on.)

And usually it works just the way it did here: You substitute k+1 for 
k in both sides, and then try to figure out what _change_ occurs as a 
result of the substitution, which you do by trying to recover the 
original form for k, with some extra stuff hanging off it:

  k              k+1
  ---------      ---------------
  (1+x)^k    ->  (1+x)^k * (1+x)

  (1+kx)     ->  (1+kx)  +  x

                   ^        ^
                   |        |
               original   extra
               form       stuff


Then you can forget about comparing the original forms, and 
concentrate on comparing the extra stuff, which is usually easier. 

Does this help? Write back if you'd like to talk about this some more, 
or if you have any other questions. 

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/   

Date: 07/03/2001 at 16:08:14
From: Doctor Rob
Subject: Re: Math Induction

Thanks for writing to Ask Dr. Math, Jay.

You will need a condition on x for this to work. It is false for
x = -11 and n = 3, for example. One condition under which this is
true for all nonnegative integers n is x >= -1.

The basis of the induction is n = 0, which you can verify directly is
true. Now assume it is true for some value of n. Now if (1+x) is
nonnegative, you can multiply both sides by (1+x) to get the left side
in the correct form. Expand the right-hand side, and rearrange it
into the form

   (1+x)^(n+1) >= 1 + (n+1)*x + n*x^2.

Observe that if you leave out the n*x^2 term, you get something equal 
or smaller, because n >= 0 and x^2 >= 0 for all real x.

I leave the rest to you.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/