SOME EXAMPLES OF PROOF TECHNIQUES

 

 

A. DIRECT PROOF (Type I) This type of proof is characterized by a sequence of equalities, each of which is only slightly different than the previous equation. It necessarily uses the properties of equality (e.g. a = b Þ a + c = b + c).

 

THEOREM: (-1)(-1) = 1

PROOF:

-1 + 1 = 0                                Inverse property of addition

-1(-1 + 1) = (-1)0                    Multiplicative property of equality

(-1)(-1) + (-1)(1) = 0               Distributive property and multiplicative property of zero

(-1)(-1) + (-1) = 0                    Property of the multiplicative identity

(-1)(-1) – 1 = 0                        Definition of subtraction

(-1)(-1) – 1 + 1 = 0 + 1           Additive property of equality

 (-1)(-1) + 0 = 1                       Inverse property of addition

(-1)(-1) = 1                              Property of the additive identity     Q.E.D.   or    

 

B. DIRECT PROOF (Type II) Here there is also a sequence of equalities, but one side of the equality to be proven remains unchanged.  It is of the form a = b and b = c so a = c. It uses none of the properties of equality, simply changing the form of one side is sufficient.

 

THEOREM: sin2 q + cos2 q = 1

PROOF: sin q = y/r and cos q = x/r where |x| and |y| represent sides of a right triangle with hypotenuse r.  Thus x2 + y2 = 1.

sin2 q + cos2 q = (y/r)2 + (x/r)2

                        = y2/r2 + x2/r2

                        = (y2 + x2)/r2

                        = r2/r2

                       = 1        

 

C. PROOF BY CONTRADICTION Math is consistent.  If we make an assumption and it leads, by the rules of mathematics, to something that is clearly false, then an assumption must have been false as well.

 

THEOREM: is irrational

PROOF: Suppose  is a rational number a/b.  By factoring a and b, we can cancel common factors. Therefore, we can assume that  = n/m where n and m have no common factors and m ¹ 0.

*= n/m

 m = n

2m2 = n2

Since n2 is even, n must have a factor of 2, say n = 2k so n2 = 4k2.

      2m2 = 4k2

      m2 = 2k2

Since m2 is even, m must have a factor of 2.  But then both m and n have a factor of 2.  This is a contradiction of the assumption that n and m have no common factors.  Thus the assumption that  is rational must be false. ÿ

 

D. CONTRAPOSITIVE PROOF If Joe is a pope then Joe is male.  If Joe is not male then Joe is not a pope.  These statements are contrapositives of one another.  If we want to prove that P implies Q, we could instead prove that not Q implies not P, since it is the same as P implies Q.

 

THEOREM: The sum of an integer and a proper fraction is not an integer.

PROOF: Suppose that k + n/m is an integer h where k is an integer and n/m is a proper fraction.

k + n/m = h

n/m= h – k

Since the difference of two integers is an integer, n/m is an integer and so is not a proper fraction.   

 

E. PROOF BY TAKING CASES  Often, when a theorem is broken into the right parts, each part is much simpler than the whole, to prove.  Divide and conquer.

 

THEOREM: Every polynomial of odd degree has at least one real root. [Assume that it has already been established that ])

PROOF: We want to show that if P(x) = anxn + an - 1xn - 1 + ... + a1x + a0 is a polynomial with n odd and an ¹ 0, then there is a real number c, such that P(c) = 0.

Since  for | x| large enough, P(x) and anxn have the same sign. But anxn has opposite signs for positive x and negative x.

CASE 1: So, if an > 0, there are real numbers x0 < x1 such that P(x0) < 0 and P(x1) > 0.

CASE 2: Similarly if an < 0, we can find x0 < x1 such that P(x0) > 0 and P(x1) < 0.

In either case, it now follows directly from the Intermediate Value Theorem that (for d = 0) there is a real number c Î [x0, x1] with P(c) = 0.

{Taken from an SOS Math webpage by Helmut Knaust}

 

F. PROOF BY INDUCTION There is an infinite number of truths to be established.  We establish it for the first case.  We then prove that if it is true for any particular case, it must be true for the next.  Like a row of dominoes, the first proves the second, which proves the third, which proves the fourth and so on.

 

THEOREM: 1 + 2 + 3 + … + n =

PROOF: Suppose the theorem is true for (some) k: 1 + 2 + 3 + … + k = k(k + 1)/2

For n = k + 1,

1 + 2 + 3 + … + k+1 = (1 + 2 + 3 + … + k) + k+1     Group the kth case

                                 = k(k+1)/2 + k+1                        Because of the assumption about k

                                 = k(k+1)/2 + 2(k+1)/2               Getting a common denominator

                                 = [k(k+1) + 2(k+1)]/2                 Combine the fractions

                                 = (k + 1)(k + 2)/2                       Factor

                                 = (k+1)(k+1 + 1)/2                     Get the form n(n+1)/2 where n = k+1

In other words the theorem is true for the case n = k+1 if it is true for k.

Suppose n = 1.

Then 1 + 2 + 3 + … + n reduces to just 1.

On the other side, n(n+1)/2 = 1(1+1)/2 = 2/2 = 1

Since the theorem is true for 1, the theorem is true for 2.

Since the theorem is true for 2, the theorem is true for 3.

Since the theorem is true for 3, the theorem is true for 4. And so forth. 

By induction the theorem is true for every natural number.

 

The same proof at a slightly higher level:

THEOREM:  For any n Î N,

PROOF:  Let .  For k = 1,  so 1 Î S.  Suppose n Î S, for some n.

 =

          = 

          =  

           =  

           =  

           = , so n + 1 Î S. 

By induction  S É N.  So for any nÎ N,   

G. COMBINATION:  Most proofs use a combination of the techniques above. The following proof is a proof by contrapositive but it also uses cases. The negation of f is either increasing or decreasing on (a,b) is that f is neither increasing nor decreasing on (a, b), and so that is where the proof starts. This proof assumes the Intermediate Value Theorem (IVT).

 

THEOREM:   If a function f is both one-to-one and continuous on an interval (a, b) , then it must be either increasing or decreasing on (a, b).

 

PROOF:  Suppose f is a continuous function. If f were neither increasing nor decreasing, then there would exist numbers x1, x2 and x3 in (a, b) with x1 < x2 < x3 such that f(x2) does not lie between f(x1) and f(x3). There are two possibilities, either

(1) f(x3) lies between f(x1) and f(x2):

 


                                                f(x1)                                     f(x2)

                                                f(x3)                                     f(x3)

                                                f(x2)                                     f(x1)

                                                           x1   x2   x3                             x1   x2   x3

 

 

 

(2) f(x1) lies between f(x2) and f(x3):

 


                                                f(x2)                                     f(x3)

                                                f(x1)                                     f(x1)

                                                f(x3)                                     f(x2)

                                                           x1   x2   x3                             x1   x2   x3

 

 

 

Case 1: Apply the IVT to the continuous function f to get a number c between x1 and x2 such that f(c) = f(x3).

Case 2: Apply the IVT to the continuous function f to get a number c between x2 and x3 such that f(c) = f(x1).

In either case, there are two distinct x-values that have the same y-value. So f is not one-to-one. ÿ

 

Notice the way that the proof is broken into cases.  When doing this, make sure that all possible cases are covered, even if they seem obvious.  The pictures do not cover all the possible cases (the x’s could be negative for example) but the English and mathematical statements do.  Pictures are meant to help explain the proof, but the proof needs to be complete. 

 

Guidelines for making your own proofs:

Remember the four C’s:

  1. Correct
  2. Complete
  3. Clear
  4. Concise

They are all important and are listed in order of importance. If you have ever read a proof in a text and found gaps, you know how frustrating to try to complete the proof.  Perhaps some of the proofs given above do not seem clear. Try rewriting them so that they flow from the beginning assumptions to the ending conclusion. The proof you construct should be understandable, with no further information, to any other student in the class. Make sure it contains all the information that you would like to have, if you were reading the proof on your own, but do not write the proof for yourself or for the professor.  It is a communication; an argument to the world.  Even in mathematics we use the English language so make sure that every line is a complete sentence.  Use capitals appropriately as well as commas, periods and any other punctuation.  Even 1 = 2/2 has a verb and an object.