Brief Note --
Proofs Involving Inequalities

Students sometimes get tangled up when working proofs with inequalities. This is mostly due to lack of practice; the basic technicques of working the proof are unchanged.

Indeed, in many ways, inequalities simplify the proof process.We are rarely concerned with how much greater or less one quantity is when compared with another; only that it is greater or less. This lets us make any number of simplifying assumptions. As long as our assumptions maintain the validity of the inequality, they may be made in any convenient manner.

Here's an example.

PROVE: 2n < n! for all n > 3.
The proof is by induction on n.
BASIS: For n = 4, 2n = 16; n! = 24; 2n < n!.
INDUCTION: Suppose 2n < n! for some n.
Here's where we start to have some fun. All we need to show is that 2n+1 < (n+1)!. We don't need to show anything about how much the difference is, or how the amount of difference may change, or anything else--just that the difference holds.

Here's the basic approach: Find an expression for some number x -- any number at all, found by any convenient method -- such that 2n+1 < x and that x < (n+1)!. We can then use the transitive property of the inequality relation (if a < b and b < c, then a < c) to show that 2n+1 < (n+1)!

Well, what do we know starting out? We know that  2n < n! for some n. We can also use whatever properties of the integers apply. For example, for all integers greater than 1, n2 > n. For all integers, (n + 1) > n. And so on.

Let's start with what we know:

2n < n!
And multiply both sides by (n + 1):
(2n ) (n + 1) < (n+1) (n!)
Noting that the right side of this inequality is the definition of (n+1)!.

OK, we've now found some number x that is less than (n+1)!. Now we need to show that 2n+1 is less than x. Well, it's easy enough to do. Since we know that n is at least 4, we know that n + 1 is at least 5, so

2 < (n + 1).
Now multiply both sides of this inequality by 2n:
2 * 2n < 2n (n + 1)
Noting that the left side of this inequality is the definition of 2n+1.

So now we know that

2 * 2n < (2n ) (n + 1)
and
(2n ) (n + 1) < (n+1) (n!)
Combining these inequalities gives
2 * 2n < 2n (n + 1) < (n+1) (n!)
Or, simplifying the terms,
2n+1 < 2n (n + 1) < (n+1)!

We now invoke the transitive property of the inequality relation and reduce the expression to

2n+1 <  (n+1)!
And the proof is complete. Rather simple once you see the trick, isn't it?

Sometimes it's easier to use the definition of various functions in order to show something is true. Here's an example:

PROVE: nn > n! for all integers n > 1.

We'll use the definition of the factorial function. n! is defined as the product of n terms:

(n)(n-1)(n-2)....(3)(2)(1)
Compare this with the product of n terms constructed as follows:
(n)(n)(n)...(n)(n)(n)
which is the definition of nn.

The second product must be larger, since both are the products of n positive integers, and all but one of the factors in the second expression are all larger than the corresponding terms in the first. The result follows quickly:

n > n- p, where p is any positive nonzero integer.
Therefore
(n * n) > n * (n-1)
(n * n * n) > (n) (n-1) (n - 2)
(n*n*n*n....*n) > (n) (n-1) (n - 2) (n - 3) (n - 4) .... (n - [n-1])




It is also possible to use induction to prove this:
ALTERNATE (INDUCTIVE) PROOF:

Pf:
The basis case is 2 (verify that the basis case is valid), and the induction uses the following steps:

nn > n! for some n.
Multiply both sides by (n+1) to obtain
(n+1)(nn) > (n+1) (n!)
In this case, (n+1)(nn) is the x we were discussing above. So we somehow need to develop an expression for (n+1)n+1 and show that it is greater than (n+1)(nn).  Now, since
n + 1 > n,
it must be true that
(n + 1)n > nn
Multiplying both sides by (n + 1) gives us
(n+1)(n+1)n > (n+1)(nn)
which is the expression we're looking for. Therefore we can combine the inequalities to get
(n+1)(n+1)n > (n+1)(nn) > (n+1) (n!)
(n+1)n+1 > (n+1)(nn) > (n+1)!
(n+1)n+1 > (n+1)!
and the proof is complete.

SI - CS 191 Homepage

Strategies for Working Proofs

Strategies for inductive proofs

Quick Review -- Laws of Exponents

Email me
 

Last modified 10/15/1999.
This page copyleft 1999 Brian K. Hare