《Mathematics for Computer》Notes for recitation 5

6.042/18.] Mathematics for Computer Science February 16, 2005 Srini devadas and Eric Lehman Notes for recitation 5 1 Well-ordering principle Every non-empty set of natural numbers has a minimum element Do you believe this statement? Seems obvious, right? Well, it is. But dont fail to realize how tight it is. Crucially, it talks about a non-empty set -otherwise, it would clearly be false. And it also talks about natural numbers -otherwise, it might again be false: think or example what would happen with the integers, or even the positive rational numbers This statement has a name, it is called the well-ordering principle. And, as most things we give names to, it's important. Why? Because it is equivalent to induction Something can be proved by induction iff it can be proved by the well-ordering principle We could go on and give a general proof of this, but we wont. Instead, we'll just convince ourselves of it by going through an example. Well reprove something that in the very first lecture(see Lecture Notes"Induction I")was proved by induction. Read the next page For reference, here is the outline that a proof by the well-ordering principle has. ( Compare it with the corresponding outline of a proof by strong induction. To prove that"P(n)is true for all n E N"using the well-ordering principle Use proof by contradiction Assume that P(n) has counterexamples. I.e., that P(n) is false on at least one n Define the set of counterexamples C=nENIP(n)) Invoke the well-ordering principle to select the minimum element c of C Since c is the smallest counterexample to P(n), conclude that both P(c) and P(0), P(1),., P(c-1). Use these to arrive at a contradiction. Watch out: the list 0. 1.... c-1 will contain no numbers at all if c=0 Conclude that P(n)must have no counterexamples. Namely, that(n)P(n)

6.042/18.062J Mathematics for Computer Science February 16, 2005 Srini Devadas and Eric Lehman Notes for Recitation 5 1 Well­ordering principle Every non­empty set of natural numbers has a minimum element. Do you believe this statement? Seems obvious, right? Well, it is. But don’t fail to realize how tight it is. Crucially, it talks about a non­empty set —otherwise, it would clearly be false. And it also talks about natural numbers —otherwise, it might again be false: think for example what would happen with the integers, or even the positive rational numbers. This statement has a name, it is called the well­ordering principle. And, as most things we give names to, it’s important. Why? Because it is equivalent to induction. Something can be proved by induction iff it can be proved by the well­ordering principle. We could go on and give a general proof of this, but we won’t. Instead, we’ll just convince ourselves of it by going through an example. We’ll reprove something that in the very first lecture (see Lecture Notes “Induction I”) was proved by induction. Read the next page. For reference, here is the outline that a proof by the well­ordering principle has. (Compare it with the corresponding outline of a proof by strong induction.) To prove that “P(n) is true for all n ∈ N” using the well­ordering principle: • Use proof by contradiction. • Assume that P(n) has counterexamples. I.e., that P(n) is false on at least one n. • Define the set of counterexamples C = {n ∈ N | ¬P(n)}. • Invoke the well­ordering principle to select the minimum element c of C. • Since c is the smallest counterexample to P(n), conclude that both ¬P(c) and P(0), P(1), . . . , P(c − 1). Use these to arrive at a contradiction. Watch out: the list 0, 1, . . . , c − 1 will contain no numbers at all if c = 0. • Conclude that P(n) must have no counterexamples. Namely, that (∀n)P(n)

Recitation 5 Theorem. For all n∈N:1+2+3+…+n=+ Proof. By contradiction. Assume that the theorem is false. Then, some natural numbers serve as counterexamples to it. Let's collect them in a set {n∈N|1+2+3+ +n By our assumption that the theorem admits counterexamples, C is a non-empty set of natural numbers. So, by the well-ordering principle, C has a minimum element, call it c That is, c is the smallest counterexample to the theorem Since c is a counterexample(cE C), we know that 1+2+3+…+c≠当 Since c is the smallest counterexample(c minimum of C), we know the theorem holds for all natural numbers smaller than c. (Otherwise at least one of them would also be in C and would therefore prevent c from being the minimum of C)[*] In particular, the theorem is true for c-1. That is 1+2+3+…+(c-1)= But then, adding c to both sides we get 1+2+3+…+(c-1)+c=2+c== hich means the theorem does hold for c, after all! That is, c is not a counterexample. But this is a contradiction And we are done Well, almost. Our argument contains a bug. Everything we said after [*] bases on the fact that c-l actually exists. That is, that there is indeed some natural number smaller than C. How do we know that? How do we know that c is not 0? Fortunately, this can be fixed. We know cf0 because c is a counterexample whereas 0 is not, as0=0(0+ 1)/2

� � � � � Recitation 5 2 Theorem. For all n ∈ N: 1 + 2 + 3 + · · · + n = n(n 2 +1) . Proof. By contradiction. Assume that the theorem is false. Then, some natural numbers serve as counterexamples to it. Let’s collect them in a set: C = n ∈ N | 1 + 2 + 3 + · · · + n = n(n 2 +1) . By our assumption that the theorem admits counterexamples, C is a non­empty set of natural numbers. So, by the well­ordering principle, C has a minimum element, call it c. That is, c is the smallest counterexample to the theorem. Since c is a counterexample (c ∈ C), we know that 1 + 2 + 3 + · · · + c = c(c+1) . 2 Since c is the smallest counterexample (c minimum of C), we know the theorem holds for all natural numbers smaller than c. (Otherwise, at least one of them would also be in C and would therefore prevent c from being the minimum of C.) [∗] In particular, the theorem is true for c − 1. That is, 1 + 2 + 3 + · · · + (c − 1) = (c−1)c . 2 But then, adding c to both sides we get 2 = c −c+2c c(c+1) 1 + 2 + 3 + · · · + (c − 1) + c = , (c−1)c + c = 2 2 2 which means the theorem does hold for c, after all! That is, c is not a counterexample. But this is a contradiction. And we are done. Well, almost. Our argument contains a bug. Everything we said after [∗] bases on the fact that c − 1 actually exists. That is, that there is indeed some natural number smaller than c. How do we know that? How do we know that c is not 0? Fortunately, this can be fixed. We know c = 0 because c is a counterexample whereas 0 is not, as 0 = 0(0 + 1)/2

Recitation 5 2 Problem: Well-ordering principle Here is the geometric sum formula, which you proved in a previous recitation Use the well-ordering principle to prove that, when+ l, the formula is true for alln E N Prepare a complete, careful solution! Proof. By contradiction. Suppose the theorem is not true on all natural numbers, but instead it admits some counterexamples. Let C be the set of these counterexamples C={n∈N|1+r+2+…+r≠} By our assumption, C is a non-empty set of natural numbers. So, the well-ordering prin ciple guarantees C has a minimum element c. So, c is the smallest counterexample to the eorem Because c is a counterexample we know 1+7+n2+…+r≠ Because 1=(1-r)/(1-r), we know 0 is not a counterexample, and therefore c>0 Because c is the smallest counterexample, we know all numbers smaller than c satisfy the theorem -and such numbers do exist, as c>0. In particular c- l satisfies the theorem But then, adding r" to both sides of the equation, we get 1+r+r2+…+r-1+r°=+r°=11-r°+°-r+]=与 which implies c is not really a counterexample, a contradiction. Therefore there cant be any counterexamples to the theorem the theorem is true. D

� � � Recitation 5 3 2 Problem: Well­ordering principle Here is the geometric sum formula, which you proved in a previous recitation. 3 1 + r + r 2 + r + . . . + r n = 1 − rn+1 1 − r Use the well­ordering principle to prove that, when r = 1, the formula is true for all n ∈ N. Prepare a complete, careful solution! Solution. Proof. By contradiction. Suppose the theorem is not true on all natural numbers, but instead it admits some counterexamples. Let C be the set of these counterexamples: | � 1− 1 r − n r +1 C = n ∈ N 1 + r + r 2 + · · · + r n = . By our assumption, C is a non­empty set of natural numbers. So, the well­ordering prin￾ciple guarantees C has a minimum element c. So, c is the smallest counterexample to the theorem. Because c is a counterexample, we know 1−rc+1 1 + r + r 2 + · · · + r c =� . 1−r Because 1 = (1 − r1)/(1 − r), we know 0 is not a counterexample, and therefore c > 0. Because c is the smallest counterexample, we know all numbers smaller than c satisfy the theorem —and such numbers do exist, as c > 0. In particular, c − 1 satisfies the theorem 1−rc 1 + r + r 2 + · · · + r c−1 = 1−r . But then, adding rc to both sides of the equation, we get 1−rc c 1−rc+1 c 1 1 + r + r 2 + · · · + r c−1 + r = 1−r + r c = 1−r [1 − r c + r − r c+1] = 1−r which implies c is not really a counterexample, a contradiction. Therefore, there can’t be any counterexamples to the theorem. The theorem is true

Recitation 5 3 Problem: a robot A robot lives on a two dimensional grid and is free to walk around. However each move it makes is always one step north or south and one step east or west. Its purpose in life is to reach point (1,0). Unfortunately, the robot was born at point(0, 0). Prove that it will point(1,0)looks like Solution. The approach that seems reasonable is to use induction on the number n of moves made by the robot. But we must be careful in selecting the inductive hypothesis P(n). If it simply corresponds to what we want to prove -that is, if it simply is"after n steps the robot is not at point (1,0)"- we are bound to encounter the same problems as in class against the g-Number Puzzle. So, we must prove something stronger Trying out several paths that the robot might take, we soon see that the robot can reach only points that lie on the line r+y=0 and every other parallel of it. One way to describe this set of positions is to say that a point(, y)belongs to it iff the sum + y is even. We are now ready to prove the following theorem, which is stronger than the one we were asked to prove Theorem. The sum of the robots coordinates is always even Proof. The proof is by(simple) induction on the number n e n of moves made by the robot. The inductive hypothesis P(n)is this: after n moves, the sum of the robot's coor- dinates is even Base case: We show that P(O)is true. Indeed, after O steps, the robot is still at its birthpoint (0,0), and the sum of its coordinates is 0+0=0, as required Inductive step: We show that P(m) implies P(n+1), for all n E N. So, fix any n E N and assume that P() is true; that is, after its nth move, the robot is at a position(a, y) such that a +y is even. After the n+lst moves, the robot will have moved one step north or south(which changes So, if(a',y)is the new point, we have r west(which also changes its y-coordinate by 1) its X-coordinate by 1)and one step east x=x±1 o that the new sum of coordinates x+y=(x±1)+(y±1)=(x+y)+(±1)+(±1)]=(x+y)+d where d E(2,,+2. In all cases, I'+y is a sum of two even numbers. So, P(n +1) holds Therefore, by induction, P(n) is true for all n E N. The theorem holds Now, to prove that the robot never reaches point (1,0), we just need to observe that the sum 1+0=l is not even

Recitation 5 4 3 Problem: A robot A robot lives on a two dimensional grid and is free to walk around. However each move it makes is always one step north or south and one step east or west. Its purpose in life is to reach point (1, 0). Unfortunately, the robot was born at point (0, 0). Prove that it will never see how point (1, 0) looks like. Solution. The approach that seems reasonable is to use induction on the number n of moves made by the robot. But we must be careful in selecting the inductive hypothesis P(n). If it simply corresponds to what we want to prove —that is, if it simply is “after n steps the robot is not at point (1, 0)”— we are bound to encounter the same problems as in class against the 9­Number Puzzle. So, we must prove something stronger. Trying out several paths that the robot might take, we soon see that the robot can reach only points that lie on the line x+y = 0 and every other parallel of it. One way to describe this set of positions is to say that a point (x, y) belongs to it iff the sum x + y is even. We are now ready to prove the following theorem, which is stronger than the one we were asked to prove. Theorem. The sum of the robot’s coordinates is always even. Proof. The proof is by (simple) induction on the number n ∈ N of moves made by the robot. The inductive hypothesis P(n) is this: after n moves, the sum of the robot’s coor￾dinates is even. Base case: We show that P(0) is true. Indeed, after 0 steps, the robot is still at its birthpoint (0, 0), and the sum of its coordinates is 0 + 0 = 0, as required. Inductive step: We show that P(n) implies P(n + 1), for all n ∈ N. So, fix any n ∈ N and assume that P(n) is true; that is, after its nth move, the robot is at a position (x, y) such that x + y is even. After the n+1st moves, the robot will have moved one step north or south (which changes its x­coordinate by 1) and one step east or west (which also changes its y­coordinate by 1). So, if (x� , y� ) is the new point, we have x� = x ± 1 and y� = y ± 1 so that the new sum of coordinates is x� + y� = (x ± 1) + (y ± 1) = (x + y) + [(±1) + (±1)] = (x + y) + d where d ∈ {−2, 0, +2}. In all cases, x� + y� is a sum of two even numbers. So, P(n + 1) holds. Therefore, by induction, P(n) is true for all n ∈ N. The theorem holds. Now, to prove that the robot never reaches point (1, 0), we just need to observe that the sum 1 + 0 = 1 is not even

Recitation 5 4 Square Infection The following problem is fairly tough until you hear a certain one-word clue. Then the solution is easy! Suppose that we have an n x n grid, where certain squares are infected Here is an example where n=6 and infected squares are marked x × Now the infection begins to spread in discrete time steps. Two squares are considered djacent if they share an edge; thus, each square is adjacent to 2, 3 or 4 others. A square is infected in the next time step if either the square was previously infected, or the square is adjacent to at least two already-infected squares In the example the infection spreads as shown below. |×| Over the next few time-steps, the entire grid becomes infected Theorem. An n x n grid can become completely infected only if at least n squares are initially Prove this theorem using induction and some additional reasoning. If you are stuck, ask your recitation instructor for the one-word clue Solution. Define the perimeter of an infected region to be the number of edges with xactly one side. Let I denote the Proof. We use induction on the number of time steps k to prove that the perimeter of the the perimeter of the infected region is at most, ypothesis P(k)is this: after k time steps, infected region never increases. The inductive hy

Recitation 5 5 4 Square Infection The following problem is fairly tough until you hear a certain one­word clue. Then the solution is easy! Suppose that we have an n × n grid, where certain squares are infected. Here is an example where n = 6 and infected squares are marked ×. × × × × × × × × Now the infection begins to spread in discrete time steps. Two squares are considered adjacent if they share an edge; thus, each square is adjacent to 2, 3 or 4 others. A square is infected in the next time step if either • the square was previously infected, or • the square is adjacent to at least two already­infected squares. In the example, the infection spreads as shown below. × × × × × × × × ⇒ × × × × × × × × × × × × × × × × ⇒ × × × × × × × × × × × × × × × × × × × × × × Over the next few time­steps, the entire grid becomes infected. Theorem. An n × n grid can become completely infected only if at least n squares are initially infected. Prove this theorem using induction and some additional reasoning. If you are stuck, ask your recitation instructor for the one­word clue! Solution. Define the perimeter of an infected region to be the number of edges with infection on exactly one side. Let I denote the perimeter of the initially­infected region. Proof. We use induction on the number of time steps k to prove that the perimeter of the infected region never increases. The inductive hypothesis P(k) is this: after k time steps, the perimeter of the infected region is at most I

Recitation 5 Base case: P(O)is true by definition; the perimeter of the infected region is at most I after 0 time steps, because I is defined to be the perimeter of the initially-infected region Inductive step: We now show that P(h)implies P(k+ 1)for all k >0. So, fix any k>0 and assume that P(k)is true; that is, after k steps, the perimeter of the infected region is at most I After step k+l the primeter can only change because some squares are newly infected. By the rules above, each newly-infected square is adjacent to at least two previously-infected squares. Thus, for each newly-infected square, at least two edges are removed from the perimenter of the infected region, and at most two edges are added to the perimeter Therefore, the perimeter of the infected region can not increase and is at most I after k+1 steps as well. Hence, P(k+ 1)is true By induction, we conclude that P(k) is true for all nk>0 Now, if an n x n grid is completely infected then the perimeter of the infected region is 4n. Thus, the whole grid can become infected only if the perimeter is initially at least 4n Since each square has perimeter 4, at least n squares must be infected initially

Recitation 5 6 Base case: P(0) is true by definition; the perimeter of the infected region is at most I after 0 time steps, because I is defined to be the perimeter of the initially­infected region. Inductive step: We now show that P(k) implies P(k + 1) for all k ≥ 0. So, fix any k ≥ 0 and assume that P(k) is true; that is, after k steps, the perimeter of the infected region is at most I. After step k+1 the primeter can only change because some squares are newly infected. By the rules above, each newly­infected square is adjacent to at least two previously­infected squares. Thus, for each newly­infected square, at least two edges are removed from the perimenter of the infected region, and at most two edges are added to the perimeter. Therefore, the perimeter of the infected region can not increase and is at most I after k + 1 steps as well. Hence, P(k + 1) is true. By induction, we conclude that P(k) is true for all nk ≥ 0. Now, if an n × n grid is completely infected, then the perimeter of the infected region is 4n. Thus, the whole grid can become infected only if the perimeter is initially at least 4n. Since each square has perimeter 4, at least n squares must be infected initially