Proof Techniques - Stanford Computer Science

1 Proof TechniquesJessica SuNovember 12, 20161 Proof techniquesHere we will learn to prove universal mathematical statements, like the square of any oddnumber is odd . It s easy enough to show that this is true in specific cases for example,32= 9, which is an odd number , and 52= 25, which is another odd number . However, toprove the statement, we must show that it works forallodd numbers, which is hard becauseyou can t try every single one of that if we want todisprovea universal statement, we only need to find one counterex-ample. For instance, if we want to disprove the statement the square of any odd number iseven , it suffices to provide a specific example of an odd number whose square is not even.

2 (For instance, 32= 9, which is not an even number .)Rule of thumb: Toprovea universal statement, you must show it works in all cases. Todisprovea universal statement, it suffices to find one counterexample.(For existence statements, this is reversed. For example, if your statement is there existsat least one odd number whose square is odd, then proving the statement just requires saying32= 9, while disproving the statement would require showing that none of the odd numbershave squares that are odd.) Proving something is true for all members of a groupIf we want to prove something is true for all odd numbers (for example, that the squareof any odd number is odd), we can pick an arbitrary odd numberx, and try to prove thestatement for that number .

3 In the Proof , we cannot assume anything aboutxother thanthat it s an odd number . (So we can t just setxto be a specific number , like 3, because thenour Proof might rely on special properties of the number 3 that don t generalize to all oddnumbers).Example:Prove that the square of any odd number is Special techniques1 Proof TECHNIQUESP roof:Letxbe an arbitrary odd number . By definition, an odd number is an integer thatcan be written in the form 2k+ 1, for some integerk. This means we can writex= 2k+ 1,wherekis some integer. Sox2= (2k+ 1)2= 4k2+ 4k+ 1 = 2(2k2+ 2k) + 1.

4 Sincekis aninteger, 2k2+ 2kis also an integer, so we can writex2= 2`+ 1, where`= 2k2+ 2kis aninteger. Therefore,x2is this logic works foranyodd numberx, we have shown that the square of any oddnumber is Special techniquesIn addition to the pick an arbitrary element trick, here are several other Techniques com-monly seen in Proof by contrapositiveConsider the statement If it is raining today, then I do not go to class. This is logically equivalent to the statement If I go to class, then it is not raining today. So if we want to prove the first statement, it suffices to prove the second statement (whichis called thecontrapositive).

5 Note that it isnotequivalent to the statement If I do not go to class, then it is rainingtoday (this is called the fallacy of the converse).Example:Letxbe an integer. Prove thatx2is an odd number if and only ifxis an :The if and only if in this statement requires us to prove both directions of theimplication. First, we must prove that ifxis an odd number , thenx2is an odd we should prove that ifx2is an odd number , thenxis an odd have already proven the first statement, so now we just need to prove the second state-ment. The second statement is logically equivalent to its contrapositive, so it suffices toprove that ifxis an even number , thenx2is even.

6 Supposexis an even number . This means we can writex= 2kfor some integerk. Thismeansx2= 4k2= 2(2k2). Sincekis an integer, 2k2is also an integer, so we can writex2= 2`for the integer`= 2k2. By definition, this meansx2is an even Proof by contradictionIn Proof by contradiction, you assume your statement is not true, and then derive a con-tradiction. This is really a special case of Proof by contrapositive (where your if is all ofmathematics, and your then is the statement you are trying to prove). Proof by induction1 Proof TECHNIQUESE xample:Prove that 2 is :Suppose that 2 was rational.

7 By definition, this means that 2 can be written asm/nfor some integersmandn. Since 2 =m/n, it follows that 2 =m2/n2, som2= any square numberx2must have an even number of prime factors, since any primefactor found in the firstxmust also appear in the secondx. Therefore,m2must have aneven number of prime factors. However, sincen2must also have an even number of primefactors, and 2 is a prime number , 2n2must have an odd number of prime factors. This is acontradiction, since we claimed thatm2= 2n2, and no number can have both an even numberof prime factors and an odd number of prime factors.

8 Therefore, our initial assumption waswrong, and 2 must be Proof by casesSometimes it s hard to prove the whole theorem at once, so you split the Proof into severalcases, and prove the theorem separately for each :Letnbe an integer. Show that ifnis not divisible by 3, thenn2= 3k+ 1 forsome :Ifnis not divisible by 3, then eithern= 3m+ 1 (for some integerm) orn= 3m+ 2(for some 1:Supposen= 3m+ 1. Thenn2= (3m+ 1)2= 9m2+ 6m+ 1 = 3(3m2+ 2m) + 3m2+ 2mis an integer, it follows that we can writen2= 3k+ 1 fork= 3m2+ 2:Supposen= 3m+ 2. Thenn2= (3m+ 2)2= 9m2+ 12m+ 4 = 9m2+ 12m+ 3 + 1 =3(3m2+ 4m+ 1) + 1.)

9 So we can writen2= 3k+ 1 fork= 3m2+ 4m+ we have proven the statement for both cases, and since Case 1 and Case 2 reflect allpossible possibilities, the theorem is Proof by inductionWe can use induction when we want to show a statement is true for all positive integersn.(Note that this is not the only situation in which we can use induction, and that inductionis not (usually) the only way to prove a statement for all positive integers.)To use induction, we prove two things: Base case:The statement is true in the case wheren= 1. Inductive step:If the statement is true forn=k, then the statement is also true forn=k+ actually produces an infinite chain of implications: The statement is true forn= Proof by induction1 Proof Techniques If the statement is true forn= 1, then it is also true forn= 2 If the statement is true forn= 2, then it is also true forn= 3 If the statement is true forn= 3, then it is also true forn= 4.

10 Together, these implications prove the statement for all positive integer values ofn. (It doesnot prove the statement for non-integer values ofn, or values ofnless than 1.)Example:Prove that 1 + 2 + +n=n(n+ 1)/2 for all integersn :We proceed by case:Ifn= 1, then the statement becomes 1 = 1(1 + 1)/2, which is step:Suppose the statement is true forn=k. This means 1 + 2 + +k=k(k+ 1)/2. We want to show the statement is true forn=k+ 1, 1 + 2 + +k+ (k+ 1) =(k+ 1)(k+ 2) the induction hypothesis ( because the statement is true forn=k), we have 1 + 2 + +k+ (k+ 1) =k(k+ 1)/2 + (k+ 1).