Direct Proofs

Let's start with an example.

Example: Divisibility is Transitive

If a and b are two natural numbers, we say that a divides b if there is another natural number k such that b = a k. For example, 2917 divides 522143 because there is a natural number k (namely k = 179) such that 522143 = 2917 k.

Theorem. If a divides b and b divides c then a divides c.

Proof. By our assumptions, and the definition of divisibility, there are natural numbers k1 and k2 such that

b = a k1 and c = b k2.

Consequently,

c = b k2 = a k1 k2.

Let k = k1 k2. Now k is a natural number and c = a k, so by the definition of divisibility, a divides c.

q

If P, Then Q

Most theorems (homework or test problems) that you want to prove are either explicitly or implicity in the form "If P, Then Q". In the previous example, "P" was "If a divides b and b divides c" and "Q" was "a divides c". This is the standard form of a theorem (though it can be disguised). A direct proof should be thought of as a flow of implications beginning with "P" and ending with "Q".

P -> ... -> Q

Most proofs are (and should be) direct proofs. Always try direct proof first, unless you have a good reason not to.

It Seems Too Easy

If you find a simple proof, and you are convinced of its correctness, then don't be shy about. Many times proofs are simple and short.

In the theorem below, a perfect square is meant to be an integer in the form a2 where a itself is an integer and an odd integer is any integer in the form 2a+1 where a is an integer.

Theorem. Every odd integer is the difference of two perfect squares.

Proof. Suppose 2a+1 is an odd integer, then

2a+1 = (a+1)2 - a2.
q
Where's the proof? It's there. It's just very short.

Another Simple Example

Recall that a natural number is called composite if it is the product of other natural numbers all greater than 1. For example, the number 39481461 is composite since it is the product of 15489 and 2549.

Theorem. The number 100...01 (with 3n-1 zeros where n is an integer larger then 0) is composite.

Proof. We can rewrite our number as 100...01 = 103n + 1 where n is an integer larger than 0. Now use the identity a3 + b3 = (a+b)(a2 - a b + b2) with a = 10n and b = 1, to get

(10n)3 + 1 = (10n + 1)(102n - 10n + 1).

We will be done once we have shown that both factors (10n + 1) and (102n - 10n + 1) are greater than 1. In the first case, this is clear since 10n > 0 when n > 0. In the second case, 102n - 10n = 10n (10n - 1) > 0, when n > 0. This completes the proof.

q

Make sure you understand why it was neccessary to discuss the two cases at the end.

One-to-One Functions

A function f:X->Y is called one-to-one if for any pair a, b in X such that f(a) = f(b) then a = b. Also, if f:X->Y and g:Y->Z are two functions then the composition gf:X->Z is the function defined by gf(a) = g(f(a)) for every a in X. Note that the composition gf is only defined if the domain of f is contained in the range of g.

Theorem. If two one-to-one functions can be composed then their composition is one-to-one.

Proof. Let a and b be in X and assume gf(a) = gf(b). Thus, g(f(a)) = g(f(b)), and since g is one-to-one we may conclude that f(a) = f(b). Finally, since f is one-to-one, a = b.

q

Roots of Polynomials

A number r is called a root of the polynomial p(x) if p(r) = 0.

Theorem. If r1 and r2 are distinct roots of the polynomial p(x) = x2 + b x + c, then r1 + r2 = - b and r1 r2 = c.

Proof. It follows from our assumptions that p(x) will factor

p(x) = (x - r1) (x - r2)

If we expand the right hand side we get

p(x) = x2 - (r1 + r2) x + r1 r2.

Compare the coefficients above with those of p(x) = x2 + b x + c to get r1 + r2 = - b and r1 r2 = c.

q

Exercises

Prove each of the following.

  1. If a divides b and a divides c then a divides b + c. (Here a, b, and c are positive natural numbers and the definition of divisibility is given above.)

  2. If a is an integer, divisible by 4, then a is the difference of two perfect squares.

  3. If a and b are real numbers, then a2 + b2 >= 2 a b.

  4. The sum of two rational numbers is a rational number.

  5. If two onto functions can be composed then their composition is onto. (A function f:X->Y is called onto if for every b in Y there is an element a in X such that f(a) = b. )

  6. If r1, r2, r3 are three distinct (no two the same) roots of the polynomial p(x) = x3 + b x2 + c x+ d, then r1 r2 + r1 r3 + r2 r3 = c.

Next==>Proof by Contradiction

<==Back To Introduction

Back to Proofs