MATHEMATICAL PROVING STRATEGIES

MATHEMATICAL PROVING STRATEGIES

1. DIRECT PROOF

   • STEPS
     • For P=Q
       • 1. Assume that P is true
         • 2. Use P to show that Q must be true
   • EXAMPLE
     • Proof. Suppose x^2 +5y = y^2 +5x.
       • Then x^2 − y 2 = 5x−5y, and factoring gives (x− y)(x+ y) = 5(x− y).
         • Now consider two cases.
           • Case 1. If x − y =/= 0 we can divide both sides of (x − y)(x + y) = 5(x − y) by the non-zero quantity x− y to get x+ y = 5.
           • Case 2. If x− y = 0, then x = y. (By adding y to both sides.) Thus x = y or x+ y = 5.

2. CONTRAPOSITIVE

   • STEPS
     • For P=Q
       • 1. Assume -Q is true
         • 2. Show that -P must be true
           • 3. Observe that P=Q by contraposition
   • EXAMPLE
     • Suppose a,b ∈ Z. If both ab and a+ b are even, then both a and b are even.
       • Suppose it is not the case that both a and b are even. Then at least one of them is odd. There are three cases to consider
         • Case 1. Suppose a is even and b is odd. Then there are integers c and d for which a = 2c and b = 2d + 1. Then ab = 2c(2d + 1), which is even; and a + b = 2c +2d +1 = 2(c + d)+1, which is odd. Thus it is not the case that both ab and a+ b are even.
         • Case 2. Suppose a is odd and b is even. Then there are integers c and d for which a = 2c +1 and b = 2d. Then ab = (2c +1)(2d) = 2(d(2c +1)), which is even; and a + b = 2c +1+2d = 2(c + d)+1, which is odd. Thus it is not the case that both ab and a+ b are even.
         • Case 3. Suppose a is odd and b is odd. Then there are integers c and d for which a = 2c + 1 and b = 2d + 1. Then ab = (2c + 1)(2d + 1) = 4cd + 2c + 2d + 1 = 2(2cd + c + d) + 1, which is odd; and a + b = 2c + 1 + 2d + 1 = 2(c + d + 1), which is even. Thus it is not the case that both ab and a+ b are even.

3. CONTRADICTION

   • EXAMPLE
     • Suppose a,b ∈ R and a 6= 0. If a is rational and ab is irrational, then b is irrational.
       • Suppose for the sake of contradiction that a is rational and ab is irrational and b is not irrational.
         • Thus we have a and b rational, and ab irrational
           • Since a and b are rational, we know there are integers c,d, e, f for which a = c d and b = e f .
             • Then ab = ce d f , and since both ce and d f are integers, it follows that ab is rational. But this is a contradiction because we started out with ab irrational.
   • STEPS
     • For P=Q
       • 1. Assume P is true
         • 2. Assume -Q is true
           • 3. Demonstrate a contradiction

4. MATHEMATICAL INDUCTION

   • STEPS
     • 1. Show P(1) is true by letting n=1
       • 2. Assume P(k) is true by letting k=1
         • 3. Show P(k) > P(k+1)
           • 4. Conclude using " Thus, P(n) is true "
   • EXAMPLE
     • If n ∈ N, then 1/1·2 + 1/2·3 + 1/3·4 + 1/4·5 +··· + 1/n(n+1) = 1− 1/n+1 .
       • (1) When n = 1, the statement is 1/1(1+1) = 1− 1/1+1 , which simplifies to 1/2 = 1/2 .
         • (2) Now assume the statement is true for some integer n = k ≥ 1, that is assume 1/1·2 + 1/2·3 + 1/3·4 + 1/4·5 +··· + 1/k(k+1) = 1− 1/k+1 .
           • Next we show that the statement for n = k +1 is true.
             • Observe that 1/1·2 + 1/2·3 + 1/3·4 + 1/4·5 +··· + 1/k(k +1) + 1/(k +1)((k +1)+1)
               • = (1/1·2 + 1/2·3 + 1/3·4 + 1/4·5 +··· + 1/k(k +1) ) + 1/(k +1)(k +2)
                 • = (1− 1/k +1) + 1/(k +1)(k +2)
                   • = 1− 1/(k +1) + 1/(k +1)(k +2)
                     • = 1− (k +2)/ (k+1)(k +2) + 1/(k +1)(k +2)
                       • = 1− (k +1)/(k +1)(k +2)
                         • = 1− 1/(k +2)
                           • = 1− 1/(k +1)+1
                             • This establishes 1/1·2 + 1/2·3 + 1/3·4 + 1/4·5 +···+ 1/(k+1)(k+1)+1 = 1− 1/(k+1)+1 , which is to say that the statement is true for n = k +1.

Images and files in the map