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 k_{1} and k_{2} such that
b = a k_{1} and c = b k_{2}.
Consequently,
c = b k_{2} = a k_{1} k_{2}.
Let k = k_{1} k_{2}. 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 a^{2} 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}  a^{2}.
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 3n1 zeros where n is an integer larger then 0) is composite.
Proof. We can rewrite our number as 100...01 = 10^{3n} + 1 where n is an integer larger than 0. Now use the identity a^{3} + b^{3} = (a+b)(a^{2}  a b + b^{2}) with a = 10^{n} and b = 1, to get
(10^{n})^{3} + 1 = (10^{n} + 1)(10^{2n}  10^{n} + 1).
We will be done once we have shown that both factors (10^{n} + 1) and (10^{2n}  10^{n} + 1) are greater than 1. In the first case, this is clear since 10^{n} > 0 when n > 0. In the second case, 10^{2n}  10^{n} = 10^{n} (10^{n}  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.
OnetoOne Functions
A function f:X>Y is called onetoone 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 onetoone functions can be composed then their composition is onetoone.
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 onetoone we may conclude that f(a) = f(b). Finally, since f is onetoone, a = b.
q
Roots of Polynomials
A number r is called a root of the polynomial p(x) if p(r) = 0.
Theorem. If r_{1} and r_{2} are distinct roots of the polynomial p(x) = x^{2} + b x + c, then r_{1} + r_{2} =  b and r_{1} r_{2} = c.
Proof. It follows from our assumptions that p(x) will factor
p(x) = (x  r_{1}) (x  r_{2})
If we expand the right hand side we get
p(x) = x^{2}  (r_{1} + r_{2}) x + r_{1} r_{2}.
Compare the coefficients above with those of p(x) = x^{2} + b x + c to get
r_{1} + r_{2} =  b and r_{1} r_{2} = c.
q
Exercises
Prove each of the following.

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

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

If a and b are real numbers, then a^{2} + b^{2} >= 2 a b.
 The sum of two rational numbers is a rational number.
 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. )
 If r_{1}, r_{2}, r_{3} are three distinct (no two the same)
roots of the polynomial p(x) = x^{3} + b x^{2} + c x+ d,
then r_{1} r_{2} + r_{1} r_{3} + r_{2} r_{3} = c.
Next==>Proof by Contradiction
<==Back To Introduction
Back to Proofs