Mathematics for Computer Science
6 Induction Inductionis a powerful method for showing a property is true for all natural num- bers. Induction plays a central ro ...
Chapter 6 Induction114 So suppose you are student 17. By these rules, are you entitled to a miniature candy bar? Well, student 0 ...
6.1. Ordinary Induction 115 6.1.2 A Familiar Example The formula (6.1) below for the sum of the nonnegative integers up tonis th ...
Chapter 6 Induction116 6.1.3 A Template for Induction Proofs The proof of equation (6.1) was relatively simple, but even the mos ...
6.1. Ordinary Induction 117 writeup below is closer to what you might see in print and should be prepared to produce yourself. R ...
Chapter 6 Induction118 2 n 2 n Figure 6.1 A 2 n 2 ncourtyard fornD 3. Figure 6.2 The special L-shaped tile. B Figure 6.3 A tili ...
6.1. Ordinary Induction 119 Proof. (doomed attempt)The proof is by induction. LetP.n/be the proposition that there exists a tili ...
Chapter 6 Induction120 X X B X 2 n 2 n 2 n 2 n Figure 6.4 Using a stronger inductive hypothesis to prove Theorem 6.1.1. we have ...
6.1. Ordinary Induction 121 False Theorem.All horses are the same color. Notice that nonis mentioned in this assertion, so we’re ...
Chapter 6 Induction122 We’ve proved something false! Is math broken? Should we all become poets? No, this proof has a mistake. T ...
6.2. State Machines 123 (^01299) overflow start state Figure 6.5 State transitions for the 99-bounded counter. 6.2.1 States and ...
Chapter 6 Induction124 0 1 2 3 0 1 2 x y Figure 6.6 The Diagonally Moving Robot. 6.2.2 Invariant for a Diagonally-Moving Robot S ...
6.2. State Machines 125 0 1 2 3 0 1 2 x y goal ‹‹ Figure 6.7 Can the Robot get to.1;0/? ...
Chapter 6 Induction126 states to be: Even-sum..m;n//WWDŒmCnis evenç: Lemma 6.2.1. For any transition,q ! r, of the diagonally-mo ...
6.2. State Machines 127 Definition 6.2.4. Thereachable statesof a state machine,M, are defined recur- sively as follows: the s ...
Chapter 6 Induction128 Robert W Floyd The Invariant Principle was formulated by Robert W Floyd at Carnegie Tech^5 in Floyd was ...
6.2. State Machines 129 6.2.4 The Die Hard Example The movieDie Hard 3: With a Vengeanceincludes an amusing example of a state m ...
Chapter 6 Induction130 such that 0 b5;0l 3. (We can prove that the reachable values ofband lwill be nonnegative integers, bu ...
6.2. State Machines 131 To prove thatPis a preserved invariant of Die-Hard-Once-and-For-All machine, we assumeP.q/holds for some ...
Chapter 6 Induction132 multiplications calledFast Exponentiation. The register machine program below defines the fast exponentia ...
«
2
3
4
5
6
7
8
9
10
11
»
Free download pdf