Associated Topics || Dr. Math Home || Search Dr. Math

### 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.

```

```
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.

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/
```
Associated Topics:
College Logic
College Number Theory
High School Logic
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search