Proofs

1 . Proofs 1/25/12 1 

2 . Bogus “Proof” that 2 = 4  Let x := 2, y := 4, z := 3  Then x+y = 2z  Rearranging, x-2z = -y and x = -y+2z  Multiply: x2-2xz = y2-2yz  Add z2: x2-2xz+z2 = y2-2yz+z2  Factor: (x-z)2 = (y-z)2  Take square roots: x-z = y-z  So x=y, or in other words, 2 = 4. ??? 2 1/25/12 

3 .A Proof • Theorem: The square of an integer is odd if and only if the integer is odd • Proof: Let n be an [Case analysis] integer. Then n is either n odd odd or even. ⇒ n=2k+1 for some integer k 2 2 ⇒ n =4k +4k+1, which is odd n even ⇒ n=2k for some integer k 2 2 ⇒ n =4k , which is even 3 1/25/12 

4 . More slowly … • Thm. For any integer n, n2 is odd if and only if n is odd. • To prove a statement of the form “P iff Q,” two separate proofs are needed: – If P then Q (or “P ⇒ Q”) – If Q then P (or “Q ⇒ P”) • “If P then Q” says exactly the same thing as “P only if Q” • So the 2 assertions together are abbreviated “P iff Q” or “P⇔Q” or “P ≡Q” 4 1/25/12 

5 .More slowly … • Thm. For any integer n, n2 is odd if and only if n is odd. (<=) If n is odd then n=2k+1 for some integer k … then n2=4k2+4k+1, which is odd (=>) “If n2 is odd then n is odd” is equivalent to “if n is not odd then n2 is not odd” (“contrapositive”) which is the same as “if n is even then n2 is even” (since n is an integer) … then n=2k for some k and n2=4k2, which is even 5 1/25/12 

6 .Contrapositive and converse • The contrapositive of “If P then Q” is “If (not Q) then (not P)” • The contrapositive of an implication is logically equivalent to the original implication • The converse of “If P then Q ” is “if Q then P ” – which in general says something quite different! 6 1/25/12 

7 .Proof by contradiction • To prove P, assume (not P) and show that a false statement logically follows. • Then the assumption (not P) must have been incorrect. 7 1/25/12 

8 . 2 is irrational • That is, there are no integers m and n such that 2  m   2 n • Suppose there were and derive a contradiction. 8 1/25/12 

9 . 2 is irrational 2  m • Suppose n  2 • Without loss of generality assume m and n have no common factors. – Because if both m and n were divisible by p, we could instead use 2  m / p  n / p  2 and eventually find a fraction in lowest terms whose square is 2. 9 1/25/12 

10 . 2 is irrational • Suppose (m/n)2 = 2 and m/n is in lowest terms. • Then m2 = 2n2. • Then m is even, say m = 2q. (Why?) • Then 4q2 =2n2, and 2q2 = n2. • Then n is even. (Why?) • Thus both m and n are divisible by 2. Contradiction. (Why?) 10 1/25/12 

11 . TEAM PROBLEMS! 1/25/12 11