Mathematics for Computer Science

4.5. Finite Cardinality 113 Problem 4.32. LetRWA!Bbe a binary relation. (a)Prove thatRis a function iffRıR^1 IdB. Write similar ...

Chapter 4 Mathematical Data Types114 Problem 4.36. LetRWA!Bbe a binary relation. Use an arrow counting argument to prove the fol ...

5 Induction Inductionis a powerful method for showing a property is true for all nonnegative integers. Induction plays a central ...

Chapter 5 Induction116 So suppose you are student 17. By these rules, are you entitled to a miniature candy bar? Well, student 0 ...

5.1. Ordinary Induction 117 5.1.2 A Familiar Example Below is the formula (5.1) for the sum of the nonnegative integers up ton. ...

Chapter 5 Induction118 5.1.3 A Template for Induction Proofs The proof of equation (5.1) was relatively simple, but even the mos ...

5.1. Ordinary Induction 119 5.1.4 A Clean Writeup The proof of Theorem 5.1.1 given above is perfectly valid; however, it contain ...

Chapter 5 Induction120 2 n 2 n Figure 5.1 A 2 n 2 ncourtyard fornD 3. Figure 5.2 The special L-shaped tile. used for the courty ...

5.1. Ordinary Induction 121 B Figure 5.3 A tiling using L-shaped tiles fornD 2 with Bill in a center square. center isn’t much h ...

Chapter 5 Induction122 X X B X 2 n 2 n 2 n 2 n Figure 5.4 Using a stronger inductive hypothesis to prove Theorem 5.1.2. Now we c ...

5.1. Ordinary Induction 123 5.1.6 A Faulty Induction Proof If we have done a good job in writing this text, right about now you ...

Chapter 5 Induction124 Soh 1 is the same color as the remaining horses besideshnC 1 —that is,h 2 ;:::;hn. Likewise,hnC 1 is the ...

5.2. Strong Induction 125 5.2.1 A Rule for Strong Induction Principle of Strong Induction. LetPbe a predicate on nonnegative int ...

Chapter 5 Induction126 Theorem.Every integer greater than 1 is a product of primes. Proof. We will prove the Theorem by strong i ...

5.2. Strong Induction 127 Figure 5.5 One way to make 26 Sg using Strongian currency We now proceed with the induction proof: Bas ...

Chapter 5 Induction128 Stack Heights Score 10 5 5 25 points 5 3 2 6 4 3 2 1 4 2 3 2 1 2 4 2 2 2 1 2 1 2 1 2 2 1 2 1 1 1 1 1 2 1 ...

5.3. Strong Induction vs. Induction vs. Well Ordering 129 Inductive step: Now we must show thatP.1/,... ,P.n/implyP.nC1/for all ...

Chapter 5 Induction130 need bother with the Well Ordering Principle either. But it’s equally easy to go the other way, and autom ...

5.4. State Machines 131 (^01299) overflow start state Figure 5.7 State transitions for the 99-bounded counter. is also called th ...

Chapter 5 Induction132 0 1 2 3 0 1 2 x y Figure 5.8 The Diagonally Moving Robot. To be precise, the robot’s transitions are: f.m ...