《Mathematics for Computer》Lecture15 induction 3

6.042/18.] Mathematics for Computer Science February 15, 2005 Srini devadas and Eric Lehman Lecture notes Induction ill 1 Two Puzzles Here are two challenging puzzles 1.1 The 9-Number puzzle The numbers 1, 2,..., 9 are arranged in a 3 x 3 grid as shown below: 123 4|51|6 78|9 You can rearrange the numbers by rotating rows and columns. For example, rotating the first row to the right gives 231 4|56→[4|56 7S|9 Notice that 1 and 2 both moved right one position and the rightmost number, 3, jumped back to the left. Similarly, if we now rotate the first column downward, then 3 and 4 both move down one position and the bottom number, 7, jumps back up to the top 35|6 489 Can you find a sequence of moves that transposes the original configuration? 2|58 369

6.042/18.062J Mathematics for Computer Science February 15, 2005 Srini Devadas and Eric Lehman Lecture Notes Induction III 1 Two Puzzles Here are two challenging puzzles. 1.1 The 9­Number Puzzle The numbers 1, 2, . . . , 9 are arranged in a 3 × 3 grid as shown below: 1 2 3 4 5 6 7 8 9 You can rearrange the numbers by rotating rows and columns. For example, rotating the first row to the right gives: 1 2 3 4 5 6 7 8 9 −→ 3 1 2 4 5 6 7 8 9 Notice that 1 and 2 both moved right one position and the rightmost number, 3, jumped back to the left. Similarly, if we now rotate the first column downward, then 3 and 4 both move down one position and the bottom number, 7, jumps back up to the top: 3 1 2 4 5 6 7 8 9 −→ 7 1 2 3 5 6 4 8 9 Can you find a sequence of moves that transposes the original configuration? −→ . . . ? . . . −→ 1 2 3 4 5 6 7 8 9 1 4 7 2 5 8 3 6 9

2 Induction ill 1. 2 The Temple of Forever Each monk entering the Temple of Forever is given a bowl with 15 red beads and 12 green beads. Each time the Gong of Time rings, the monk must do one of two thing 1. If he has at least 3 red beads in his bowl, then he may remove 3 red beads and add 2 green beads 2. He may replace every bead in his bowl with a bead of the opposite color For example, at the first ring of the Gong of Time, the monk might replace every bead with one of the opposite color, giving him 12 red and 15 green. Then, at the second ring, he might remove 3 red and add 2 green, leaving 9 red and 17 green. A monk may leave the Temple of Forever only when he has exactly 5 red beads and 5 green beads in his bowl. Can you find a way to escape? 2 Using Induction to Analyze a Process An important application of induction is proving that a system never enters some unde- sirable state. For example, we might want to prove that a file system is never corrupted, records in a data structure are always rapidly retrievable, or a communication protocol never deadlocks. No new mathematical techniques are required to use induction for such purposes. But you'll need to think about induction somewhat differently. We'll use the umbe uzzle and the Temple of Forever as illustrations 2.1 Induction on time Some frustrating experiments suggest that there is no way to escape from the Temple of Forever or solve the 9-Number Puzzle But how could we hope to prove these conclusions using induction? Remember that induction establishes that some predicate P(n)is true for all n E N. For the Temple problem, should we use induction on the number of red beads? Green beads? The total? Worse the -Number puzzle doesn 't seem to involve a natural-valued variable at all! The common solution when analyzing a system is to use induction on time; that is 7e'll use induction to prove that some predicate P() is true for every n20 where n is the number of rotations, gong rings, moves, hours, steps, or whatever. Unfortunately, a naive approach still doesn't work. Let's try such an argument and see where we get stuck Theorem. No one leaves the temple of forever

2 Induction III 1.2 The Temple of Forever Each monk entering the Temple of Forever is given a bowl with 15 red beads and 12 green beads. Each time the Gong of Time rings, the monk must do one of two things: 1. If he has at least 3 red beads in his bowl, then he may remove 3 red beads and add 2 green beads. 2. He may replace every bead in his bowl with a bead of the opposite color. For example, at the first ring of the Gong of Time, the monk might replace every bead with one of the opposite color, giving him 12 red and 15 green. Then, at the second ring, he might remove 3 red and add 2 green, leaving 9 red and 17 green. A monk may leave the Temple of Forever only when he has exactly 5 red beads and 5 green beads in his bowl. Can you find a way to escape? 2 Using Induction to Analyze a Process An important application of induction is proving that a system never enters some unde￾sirable state. For example, we might want to prove that a file system is never corrupted, records in a data structure are always rapidly retrievable, or a communication protocol never deadlocks. No new mathematical techniques are required to use induction for such purposes. But you’ll need to think about induction somewhat differently. We’ll use the 9­Number Puzzle and the Temple of Forever as illustrations. 2.1 Induction on Time Some frustrating experiments suggest that there is no way to escape from the Temple of Forever or solve the 9­Number Puzzle. But how could we hope to prove these conclusions using induction? Remember that induction establishes that some predicate P(n) is true for all n ∈ N. For the Temple problem, should we use induction on the number of red beads? Green beads? The total? Worse, the 9­Number Puzzle doesn’t seem to involve a natural­valued variable at all! The common solution when analyzing a system is to use induction on time; that is, we’ll use induction to prove that some predicate P(n) is true for every n ≥ 0 where n is the number of rotations, gong rings, moves, hours, steps, or whatever. Unfortunately, a naive approach still doesn’t work. Let’s try such an argument and see where we get stuck. Theorem. No one leaves the Temple of Forever

Induction Ill Proof. We use induction. Let P(n) be the proposition, "After n gong rings, the number of red beads in the monk's bowl is not equal to the number of green beads Base case. Initially, there are 15 red beads and 12 green beads, so P(O)is true Inductive step. We must show that P(n)implies P(n+1) for all n 20. So assume that after n gong rings the number of red beads in the monks bowl is not equal to the number of green beads. Then after n+ l gong rings Ne re stuck! If we assume that P(n)is true, the monk might have, say,onen leaves him red beads and 3 green beads after n gong rings. But then removing 3 red and adding 2 grec with 5 red and 5 green, making P(n+ 1)false! In other words, we can't hope to prove P(n)implies P(n+1)in the inductive step--not because we aren' t sufficiently clever, but because it's just not true o we must be clever-er 2.2 Finding an Induction Hypothesis The key to proving that a system can never reach a"bad"state is chosing the right induc tion hypothesis. In particular, the induction hypothesis should describe a property that 1. True at the start 2. Invariant, meaning that if the system has the property before a move then it must also have the property after the move 3. False in the"bad"state Intuitively, were looking for a property that the system has initially and can never lose This means any state of the system lacking that property is unreachable Let's check a couple properties against these criteria The monk always has at least one bead. This is true initially since the monk starts with a bowlful of beads. Furthermore, this property is invariant. Suppose thethe monk has at least one bead If the monk removes 3 red beads and adds 2 green, then he is left with at least the 2 green.(Remember this operation is only allowed if the monk has at least 3 red. If the monk has at least one bead before swapping colors then he has at least one bead after doing so; in fact, chaning colors does not affect the number of beads at all

Induction III 3 Proof. We use induction. Let P(n) be the proposition, “After n gong rings, the number of red beads in the monk’s bowl is not equal to the number of green beads.” Base case. Initially, there are 15 red beads and 12 green beads, so P(0) is true. Inductive step. We must show that P(n) implies P(n+ 1) for all n ≥ 0. So assume that after n gong rings the number of red beads in the monk’s bowl is not equal to the number of green beads. Then after n + 1 gong rings... × We’re stuck! If we assume that P(n) is true, the monk might have, say, 8 red beads and 3 green beads after n gong rings. But then removing 3 red and adding 2 green leaves him with 5 red and 5 green, making P(n + 1) false! In other words, we can’t hope to prove P(n) implies P(n+1) in the inductive step— not because we aren’t sufficiently clever, but because it’s just not true! So we must be clever­er. 2.2 Finding an Induction Hypothesis The key to proving that a system can never reach a “bad” state is chosing the right induc￾tion hypothesis. In particular, the induction hypothesis should describe a property that is: 1. True at the start. 2. Invariant, meaning that if the system has the property before a move, then it must also have the property after the move. 3. False in the “bad” state. Intuitively, we’re looking for a property that the system has initially and can never lose. This means any state of the system lacking that property is unreachable. Let’s check a couple properties against these criteria. The monk always has at least one bead. This is true initially since the monk starts with a bowlful of beads. Furthermore, this property is invariant. Suppose the the monk has at least one bead. • If the monk removes 3 red beads and adds 2 green, then he is left with at least the 2 green. (Remember this operation is only allowed if the monk has at least 3 red.) • If the monk has at least one bead before swapping colors, then he has at least one bead after doing so; in fact, chaning colors does not affect the number of beads at all

Induction ill The problem is that this property also holds in the state we're trying to rule out, where the monk has 5 red and 5 green. So this property does not meet all our The monk has an unequal number of red and green beads. This property does hold at this start and does not hold in the " bad"state where the monk has 5 red and 5 green. However, this property is not preserved by every move. For example, if the monk has 13 red and 8 green, then after the next gong he could have 10 red and 10 green. In other words the property is not invariant. a good way to find an invariant is to list a lot of states and look for a distinctive feature they have in common For example here are some states the monk can reach (15,12)→(12,15) (9,17) (17,9) (12,14)→(14,12)→(11,14)→(14,11) (9,16) (11,13) Here the pair (r, g) denotes the state where the monk has r red beads and g green beads Continuing in this way, you might notice that the difference r-g only takes on certain values: 2,-2, 3,-3, 7,-7,8,-8, etc. In particular, the number of red beads minus the number of green beads is always of the form 5k+2 or 5k +3 where k is an integer. The rules for the Temple provide an explanation: adding 3 red and removing 2 green changes the difference by 5 And swapping colors negates the difference. Furthermore, this property holds at the start (since 15-12=5.0+3)and does not hold in the state were trying to prove unreachable (since 5-5=0 is not of the form 5k+ 2 or 5k+ 3). This is exactly the sort of property we need, so we re ready for a proof! Theorem 1. No one leaves the Temple of forever Proof. We use induction on the number of gong rings. Let P(n)be the proposition that after n rings, the number of red beads in the monk's bowl minus the number of green beads is equal to 5k+2 or 5k +3 for some integer k Base case: P(O)is true because initially(after zero rings)the number of red beads minus the number of green beads is 15-12=5.0+3 Inductive step: Now assume that P(n)holds after n gong rings, where n 20. Let r denote the number of red beads in the monk's bowl, and let g denote the number of green beads In these terms, we are assuming that r-g is equal to 5k+ 2 or 5k+ 3 for some integer k After n+ l gong rings, there are two cases to consider, depending on the monk's action 1. If r> 3, then the monk may have replaced 3 red beads with 2 green beads. Thus, the number of red beads minus the number of green becomes (r-3)-(g+2)=(r-g) This is equal to either 5(k-1)+2 or 5(k-1)+3, so P(n+ 1)is true

4 Induction III The problem is that this property also holds in the state we’re trying to rule out, where the monk has 5 red and 5 green. So this property does not meet all our criteria. The monk has an unequal number of red and green beads. This property does hold at this start, and does not hold in the “bad” state where the monk has 5 red and 5 green. However, this property is not preserved by every move. For example, if the monk has 13 red and 8 green, then after the next gong he could have 10 red and 10 green. In other words, the property is not invariant. A good way to find an invariant is to list a lot of states and look for a distinctive feature they have in common. For example, here are some states the monk can reach: (15, 12) → (12, 15) → (9, 17) → (17, 9) ↓ (12, 14) → (14, 12) → (11, 14) → (14, 11) ↓ ↓ ↓ (9, 16) → (16, 9) (8, 16) (11, 13) Here the pair (r, g) denotes the state where the monk has r red beads and g green beads. Continuing in this way, you might notice that the difference r − g only takes on certain values: 2, ­2, 3, ­3, 7, ­7, 8, ­8, etc. In particular, the number of red beads minus the number of green beads is always of the form 5k+2 or 5k+3 where k is an integer. The rules for the Temple provide an explanation: adding 3 red and removing 2 green changes the difference by 5. And swapping colors negates the difference. Furthermore, this property holds at the start (since 15 − 12 = 5 0 + 3 · ) and does not hold in the state we’re trying to prove unreachable (since 5 − 5 = 0 is not of the form 5k + 2 or 5k + 3). This is exactly the sort of property we need, so we’re ready for a proof! Theorem 1. No one leaves the Temple of Forever. Proof. We use induction on the number of gong rings. Let P(n) be the proposition that after n rings, the number of red beads in the monk’s bowl minus the number of green beads is equal to 5k + 2 or 5k + 3 for some integer k. Base case: P(0) is true because initially (after zero rings) the number of red beads minus the number of green beads is 15 − 12 = 5 0 + 3 · . Inductive step: Now assume that P(n) holds after n gong rings, where n ≥ 0. Let r denote the number of red beads in the monk’s bowl, and let g denote the number of green beads. In these terms, we are assuming that r − g is equal to 5k + 2 or 5k + 3 for some integer k. After n + 1 gong rings, there are two cases to consider, depending on the monk’s action: 1. If r ≥ 3, then the monk may have replaced 3 red beads with 2 green beads. Thus, the number of red beads minus the number of green becomes: (r − 3) − (g + 2) = (r − g) − 5 This is equal to either 5(k − 1) + 2 or 5(k − 1) + 3, so P(n + 1) is true

5 2. Alternatively, the monk may have exchanged every red bead for a green bead and vice versa. In this case, the number of reds minus the number of greens becomes g-r.Ifr-g=5k+3, then g-r=5(-k)-3=5(-k-1)+2.lfr-g=5k+2 5(k)-2=5(-A-1)+3. Thus, P(n +1)is again tr Therefore, P(n) implies P(n+1) for all n 20 By the induction principle, P(n)is true for all n 20. Since the number of red beads minus the number of greens is always of the form 5k+ 2 or 5k +3 and the difference required to leave the temple does not match either form, no monk can ever leave the Temple of Forever Q Many proofs that a system can not reach a"bad"state share several features with this The induction hypothesis holds initially and is preserved by every move, but does not hold in the"bad state The proof uses induction on time, as measured by gong rings, operations, or what- ever In the inductive step, there is one case for every possible operation In fact the proof that the 9-Number puzzle is unsolvable has the same format 3 The 9-Number puzzle We'l prove the 9-Number Puzzle insoluble using a property that probably would not occur to you immediately, but comes up all the time in puzzles and protocols involving arrangements of objects 3.1 Permutations and inversions A permutation of the numbers 1 thorugh 9 is a sequence containing each digit exactly once. Placing the rows of the puzzle side-by-side gives a permutation of the numbers 1 to 9. For example, the original configuration corresponds to a permutation as shown below: 4|5|6 123456789

Induction III 5 2. Alternatively, the monk may have exchanged every red bead for a green bead and vice versa. In this case, the number of reds minus the number of greens becomes g − r. If r − g = 5k + 3, then g − r = 5(−k) − 3 = 5(−k − 1) + 2. If r − g = 5k + 2, then g − r = 5(−k) − 2 = 5(−k − 1) + 3. Thus, P(n + 1) is again true. Therefore, P(n) implies P(n + 1) for all n ≥ 0. By the induction principle, P(n) is true for all n ≥ 0. Since the number of red beads minus the number of greens is always of the form 5k + 2 or 5k + 3 and the difference required to leave the temple does not match either form, no monk can ever leave the Temple of Forever. Many proofs that a system can not reach a “bad” state share several features with this one: • The induction hypothesis holds initially and is preserved by every move, but does not hold in the “bad state”. • The proof uses induction on time, as measured by gong rings, operations, or what￾ever. • In the inductive step, there is one case for every possible operation. In fact, the proof that the 9­Number Puzzle is unsolvable has the same format. 3 The 9­Number Puzzle We’ll prove the 9­Number Puzzle insoluble using a property that probably would not occur to you immediately, but comes up all the time in puzzles and protocols involving arrangements of objects. 3.1 Permutations and Inversions A permutation of the numbers 1 thorugh 9 is a sequence containing each digit exactly once. Placing the rows of the puzzle side­by­side gives a permutation of the numbers 1 to 9. For example, the original configuration corresponds to a permutation as shown below: −→ 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9

Induction ill An inversion is a pair of terms in a permutation that are in reverse order. For de the original permutation has zero inversions; 1 precedes 2, 1 precedes 3, 2 precedes 3, 1 precedes 4, and so forth. But now suppose we rotate the top row to the right as before 312456789 Now there are two inversions: 3 and 1 are out of order and so are 3 and 2. Suppose we rotate the first column downward 712 35|6 712356489 489 The resulting permutation has eight inversions (7,1)(7,2)(7,3)(7,5) (7,6)(7,4)(5,4)(6,4) At this point, one might guess that the number of inversions is always even. Let's check that this property does not hold for the transpose configuration, which wed like to prove unreachable 58 147258369 Sure enough, here there are nine inversions, which is an odd number (4,2) (7,2)(7,4)(7,3) (7,6) (8,3)(8, 3.2 The 9-Number Puzzle is Impossible Were now ready to prove that the 9-Number Puzzle is unsolvable. The proof relies on some preliminary facts about inversions. This is exactly the sort of situation where lem mas can make an argument more clear The parity of an integer refers to whether the number is even or odd. For example, as odd parity, 4 has even parity, and 0 has even parity. Lemma 2. Swapping two terms in a permutation changes the parity of the number of inversions Proof. Take an arbitrary permutation b1. bk: y

6 Induction III An inversion is a pair of terms in a permutation that are in reverse order. For example, the original permutation has zero inversions; 1 precedes 2, 1 precedes 3, 2 precedes 3, 1 precedes 4, and so forth. But now suppose we rotate the top row to the right as before: 3 1 2 4 5 6 7 8 9 −→ 3 1 2 4 5 6 7 8 9 Now there are two inversions: 3 and 1 are out of order and so are 3 and 2. Suppose we rotate the first column downward: 7 1 2 3 5 6 4 8 9 −→ 7 1 2 3 5 6 4 8 9 The resulting permutation has eight inversions: (7, 1) (7, 2) (7, 3) (7, 5) (7, 6) (7, 4) (5, 4) (6, 4) At this point, one might guess that the number of inversions is always even. Let’s check that this property does not hold for the transpose configuration, which we’d like to prove unreachable: 1 4 7 2 5 8 3 6 9 −→ 1 4 7 2 5 8 3 6 9 Sure enough, here there are nine inversions, which is an odd number: (4, 2) (4, 3) (7, 2) (7, 4) (7, 3) (7, 6) (5, 3) (8, 3) (8, 6) 3.2 The 9­Number Puzzle is Impossible We’re now ready to prove that the 9­Number Puzzle is unsolvable. The proof relies on some preliminary facts about inversions. This is exactly the sort of situation where lem￾mas can make an argument more clear. The parity of an integer refers to whether the number is even or odd. For example, 7 has odd parity, 4 has even parity, and 0 has even parity. Lemma 2. Swapping two terms in a permutation changes the parity of the number of inversions. Proof. Take an arbitrary permutation: x b1 . . . bk y

Induction Ill The horizontal lines indicate sequences of elements. Swapping c and y gives the permu tation: y b1.. bk This reverses the order of 2k +l pairs: a and y, a and each bi, and y and each b;. Effectively, this flips the parity 2k 1 times which is equivalent to flipping the parity once Lemma 3. Rotating three terms in a permutation preserves the parity of the number of inversions Proof. Take an arbitrary permutation A forward rotation is equivalent to swapping y and z and then swapping r and z y Similarly, a reverse rotation is equivalent to swapping and y and then r and z: In any case, two swaps flip the parity twice, which leaves the original parity unchanged Theorem 4. No sequence of moves transforms the original configuration of the 9-Number Puzzle into the transpose configuration Proof. We use induction. Let P(n) be the proposition that after n steps the number of inverted digits is even Base case. After 0 steps, the puzzle is in the original configuration. There are zero inver- sions, so P(0) is true Inductive step. Suppose that after n steps, the puzzle has an even number of inversions By Lemma 3, rotating three digits preserves the parity of the number of inversions. Thus, the puzzle has an even number of inversions after n+ l steps as well By the principle of induction, P(n) is true for all n 20; that is, the number of inversions is even after any sequence of moves. The transpose configuration is unreachable since it has an odd number of inversions A few wrap-up notes, First, notice that Lemma 3 holds when any three digits are ro- tated. Thus, even if we allowed rotations along the long diagonals of the 9-Number Puz zle, there would still be no way to reach the transpose configuration. Second, similar rguments about permutations and inversions explain why certain states are unreach able in many other puzzles. For example, you may have observed that there is no way to flip a single edge of Rubiks Cube. Finally, you might be discouraged that this technique only helps prove that puzzles are not solvable. This seems rather negative. But remember in that in the context of a file system or communication protocol, proving that the system never enters a corrupted or deadlocked state is a very good thing

Induction III 7 The horizontal lines indicate sequences of elements. Swapping x and y gives the permu￾tation: y b1 . . . bk x This reverses the order of 2k+1 pairs: x and y, x and each bi, and y and each bi. Effectively, this flips the parity 2k + 1 times which is equivalent to flipping the parity once. Lemma 3. Rotating three terms in a permutation preserves the parity of the number of inversions. Proof. Take an arbitrary permutation: x y z A forward rotation is equivalent to swapping y and z and then swapping x and z: z x y Similarly, a reverse rotation is equivalent to swapping x and y and then x and z: y z x In any case, two swaps flip the parity twice, which leaves the original parity unchanged. Theorem 4. No sequence of moves transforms the original configuration of the 9­Number Puzzle into the transpose configuration. Proof. We use induction. Let P(n) be the proposition that after n steps the number of inverted digits is even. Base case. After 0 steps, the puzzle is in the original configuration. There are zero inver￾sions, so P(0) is true. Inductive step. Suppose that after n steps, the puzzle has an even number of inversions. By Lemma 3, rotating three digits preserves the parity of the number of inversions. Thus, the puzzle has an even number of inversions after n + 1 steps as well. By the principle of induction, P(n) is true for all n ≥ 0; that is, the number of inversions is even after any sequence of moves. The transpose configuration is unreachable since it has an odd number of inversions. A few wrap­up notes, First, notice that Lemma 3 holds when any three digits are ro￾tated. Thus, even if we allowed rotations along the long diagonals of the 9­Number Puz￾zle, there would still be no way to reach the transpose configuration. Second, similar arguments about permutations and inversions explain why certain states are unreach￾able in many other puzzles. For example, you may have observed that there is no way to flip a single edge of Rubik’s Cube. Finally, you might be discouraged that this technique only helps prove that puzzles are not solvable. This seems rather negative. But remember in that in the context of a file system or communication protocol, proving that the system never enters a corrupted or deadlocked state is a very good thing!

Induction ill 4 Common induction mistakes There are several potholes that students commonly fall into while trying to write induc tion proofs. Some are simple, some are quite subtle. Collectively, these traps cost 6.042 students thousands of points every term. Here are the top grade -gutters and how to avoid them.(Alternatively, if you mash all these blunders into a single proof, you might be able to drive your ta bananas. 4.1 The Misplaced Quantifier Let's start with a simple, relatively minor gotcha. Can you spot the problem? Theorem 5. For alln >0 n(2n+1)(n+1) 6 Proof. We use induction. Let P(n)be the proposition, "For all n >0, 12+22+..+n2 In general, an induction hypothesis is a predicate P(n), which is a statement that is true or false depending on the value of n. The goal of an induction proof is to prove that P(n)=“12+2+…+n2 2n+1)(n+1 In the erroneous proof above, the predicate P(n)itself asserts that an equation holds for all 20. This makes no sense. The"For all n >0"bit should not be part of the induction hypothes 4.2 Misusing a Predicate as a Numerical function Here's another classic. This one is a pretty major error. Theorem 6. For all n >0 n(2n+1)(7+1)

8 Induction III 4 Common Induction Mistakes There are several potholes that students commonly fall into while trying to write induc￾tion proofs. Some are simple, some are quite subtle. Collectively, these traps cost 6.042 students thousands of points every term. Here are the top grade­gutters and how to avoid them. (Alternatively, if you mash all these blunders into a single proof, you might be able to drive your TA bananas.) 4.1 The Misplaced Quantifier Let’s start with a simple, relatively minor gotcha. Can you spot the problem? Theorem 5. For all n ≥ 0: 2 12 + 22 + . . . + n = n(2n + 1)(n + 1) 6 2 Proof. We use induction. Let P(n) be the proposition, “For all n ≥ 0, 12 + 22 + . . . + n = n(2n + 1)(n + 1)/6”. Base case. Etc. × In general, an induction hypothesis is a predicate P(n), which is a statement that is true or false depending on the value of n. The goal of an induction proof is to prove that P(n) is true for all n ≥ 0. A valid induction hypothesis in this case would be: 2 P(n) = “12 + 22 + . . . + n = n(2n + 1)(n + 1) ” 6 In the erroneous proof above, the predicate P(n) itself asserts that an equation holds for all n ≥ 0. This makes no sense. The “For all n ≥ 0” bit should not be part of the induction hypothesis. 4.2 Misusing a Predicate as a Numerical Function Here’s another classic. This one is a pretty major error. Theorem 6. For all n ≥ 0: 2 12 + 22 + . . . + n = n(2n + 1)(n + 1) 6

Induction Ill Po!. We use induction.LetP(m)be“12+22+….+n2=n(2n+1)(n+1)/6′ Base case,P(0)=20+)0+1=0 Inductive Step P(n)+(n+1)2 7(2n+1)(n+1 6 (n+1)(2m+1)+1)mn+2 6 =P(n+1) Remember, an induction hypothesis is a predicate P(n), which is a statement that is true or false depending on the value of n. In particular, P(n) has no a numerical value Adding P(n)is like trying to divide by a pomegranate. It makes no sense 4.3 Too Few base cases The Fibonacci numbers Fo, Fl, F2,... are defined recursively as follows: (Fn-1+Fn-2 when n≥2 Thus the first few Fibonacci numbers are,1, 1, 2, 3, 5,8,.... Each number is the sum of its two predecessors, except for the first two Well use Fibonacci numbers to demonstrate a error that usually comes up in connec tion with strong induction proofs False claim z. all fibonacci numbers are even Proof. We use strong induction. Let P(n) be the proposition that Fn is even Base case. Fo=0 is even, so P(O) is true Inductive step. Assume P(0),., P(n-1)to prove P(n). Now Fn= Fn-1+ Fn nd Fn- and Fn-2 are both even by assumptions P(n-1)and P(n-2), so Fn is also even By induction, all Fibonacci numbers are even

Induction III 9 2 Proof. We use induction. Let P(n) be “12 + 22 + . . . + n = n(2n + 1)(n + 1)/6”. Base case. P(0) = 0(2·0+1)(0+1) = 0 6 Inductive Step. P(n) + (n + 1)2 = n(2n + 1)(n + 1) 1 ) 2 + (n 6 (n + 1)(2(n + 1) + 1)(n + 2) = 6 = P(n + 1) × Remember, an induction hypothesis is a predicate P(n), which is a statement that is true or false depending on the value of n. In particular, P(n) has no a numerical value. Adding P(n) is like trying to divide by a pomegranate. It makes no sense. 4.3 Too Few Base Cases The Fibonacci numbers F0, F1, F2, . . . are defined recursively as follows: ⎧ ⎪⎨ ⎪⎩ 0 when n = 0 Fn = 1 when n = 1 Fn−1 + Fn−2 when n ≥ 2 Thus, the first few Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, . . . . Each number is the sum of its two predecessors, except for the first two. We’ll use Fibonacci numbers to demonstrate a error that usually comes up in connec￾tion with strong induction proofs. False Claim 7. All Fibonacci numbers are even. Proof. We use strong induction. Let P(n) be the proposition that Fn is even. Base case. F0 = 0 is even, so P(0) is true. Inductive step. Assume P(0), . . . , P(n − 1) to prove P(n). Now Fn = Fn−1 + Fn−2 and Fn−1 and Fn−2 are both even by assumptions P(n−1) and P(n−2), so Fn is also even. By induction, all Fibonacci numbers are even. ×

Induction ill The problem is that too few base cases are considered. This immediately raises a larger question: How many base cases must I consider? The answer goes back to the strong induction axiom. In order to prove P(n) for alln>0, you must prove all of the following 口1.P(0) 日2. P(O)implies P(1) 3. P(O)and P(1)imply P(2) d 4. P(O), P(1), and P(2)imply P(3) 5. P(O), P(1), P(2)and P(3)imply P(4) You can regard this as a scorecard for strong induction proofs; if you cant check off ev ery box, the proof is bogus. For example, in the "proof"above, we established the first statement under the base case heading. The argument under the inductive step heading es- tablished statements 3, 4, 5, etc. This argument does not work for n= l, because it relies on the assumption P(n-2). ) So heres the scorecard a 2. P(O) implies P(1) X 3. P(O)and P() imply P(2) X 4. P(0), P(1), and P(2)imply P(3) X 5. P(0), P(1), P(2)and P(3)imply P(4 In order to complete the proof, we would need to show that P(O)implies P(1). But we can not in this case, since P(1)is actually false; the Fibonacci number F1= l is odd 4.4 Choosing the Wrong Induction Variable Many problems involve several different natural-valued random variables. For exampl Theoren8. For all integers k≥0andr≥2 1+T+r+.+rk1-rk+1 We could try an induction argument based on the variable r or based on the variable k. One choice(k) leads to prompt success and the other(r)leads to disaster. How are yo to know which is which? There is no general answer, though we'l try to provide guidance from time to time For example, when proving a property of a system that changes in discrete time steps, use induction on the number of steps. Your best course is to avoid fixating exclusively on one variable; if the proof doesnt work out, try induction on another variable

10 Induction III The problem is that too few base cases are considered. This immediately raises a larger question: “How many base cases must I consider?” The answer goes back to the strong induction axiom. In order to prove P(n) for all n ≥ 0, you must prove all of the following: � 1. P(0) � 2. P(0) implies P(1) � 3. P(0) and P(1) imply P(2) � 4. P(0), P(1), and P(2) imply P(3) � 5. P(0), P(1), P(2) and P(3) imply P(4) . . . . . . etc. You can regard this as a scorecard for strong induction proofs; if you can’t check off ev￾ery box, the proof is bogus. For example, in the “proof” above, we established the first statement under the base case heading. The argument under the inductive step heading es￾tablished statements 3, 4, 5, etc. (This argument does not work for n = 1, because it relies on the assumption P(n − 2).) So here’s the scorecard: ×� � ×� ×� ×� 1. P(0) 2. P(0) implies P(1) 3. P(0) and P(1) imply P(2) 4. P(0), P(1), and P(2) imply P(3) 5. P(0), P(1), P(2) and P(3) imply P(4) . . . . . . etc. In order to complete the proof, we would need to show that P(0) implies P(1). But we can not in this case, since P(1) is actually false; the Fibonacci number F1 = 1 is odd. 4.4 Choosing the Wrong Induction Variable Many problems involve several different natural­valued random variables. For example: Theorem 8. For all integers k ≥ 0 and r ≥ 2: k 1 + r + r 2 + . . . + r = 1 − rk+1 1 − r We could try an induction argument based on the variable r or based on the variable k. One choice (k) leads to prompt success and the other (r) leads to disaster. How are you to know which is which? There is no general answer, though we’ll try to provide guidance from time to time. For example, when proving a property of a system that changes in discrete time steps, use induction on the number of steps. Your best course is to avoid fixating exclusively on one variable; if the proof doesn’t work out, try induction on another variable