1_Mathematical Proof Strategies

1_Mathematical Proof Strategies

1. Direct proof

   • 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

   • 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

   • Suppose a,b ∈ R and a 6= 0. If a is rational and ab is irrational, then b is irrational.
     • Proof. 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.

4. Mathematical induction

   • 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