Mathematics for Computer Science

7.4. Arithmetic Expressions 173  Case[x] The left hand side of equation (7.20) equals eval.f;n/by this base case in Definition ...

Chapter 7 Recursive Data Types174 7.5 Induction in Computer Science Induction is a powerful and widely applicable proof techniqu ...

7.5. Induction in Computer Science 175 Constructor cases: Iff;gare F18’s, then so are 1.fCg,fg,eg(the constante), the inverse f ...

Chapter 7 Recursive Data Types176 Problem 7.5. Definition.The recursive data type, binary-2PTG, ofbinary treeswith leaf labels, ...

7.5. Induction in Computer Science 177 (a)Write out (using angle brackets and labelsbintree,leaf, etc.) the binary-2PTG, G, pict ...

Chapter 7 Recursive Data Types178 Figure 7.2 Constructing the Koch Snowflake. Prove by structural induction that the area inside ...

7.5. Induction in Computer Science 179 Class Problems Problem 7.9. Letpbe the string[ ]. A string of brackets is said to beerasa ...

Chapter 7 Recursive Data Types180 Subcase(xis of the form[s^0 ]twheresis an erase ofs^0 ): Sinces 2 RecMatch, it is erasable by ...

7.5. Induction in Computer Science 181 right bracket. For example, here are the counts for two sample strings: [ ] ] [ [ [ [ [ ] ...

Chapter 7 Recursive Data Types182 according to the Environment Model and the Substitution Model, indicating where the rule for e ...

8 Number Theory Number theoryis the study of the integers.Whyanyone would want to study the integers is not immediately obvious. ...

Chapter 8 Number Theory184  ajb,  adividesb,  ais adivisorofb,  ais afactorofb,  bisdivisiblebya,  bis amultipleofa. Some ...

8.1. Divisibility 185 Famous Conjectures in Number Theory Goldbach Conjecture Every even integer greater than two is equal to th ...

Chapter 8 Number Theory186 Ifajbandbjc, thenajc. Ifajbandajc, thenajsbCtcfor allsandt. For allc¤ 0 ,ajbif and only ifcajcb. Pr ...

8.1. Divisibility 187 The numberqis called thequotientand the numberris called theremainderof ndivided byd. We use the notation ...

Chapter 8 Number Theory188 theb-jug is big enough: .0;0/!.a;0/ fill first jug !.0;a/ pour first into second !.a;a/ fill first ju ...

8.2. The Greatest Common Divisor 189 So we have established that the jug problem has an invariant property, namely that the amou ...

Chapter 8 Number Theory190 Proof. By the Division Theorem 8.1.5, aDqbCr (8.2) whererDrem.a;b/. Soais a linear combination ofband ...

8.2. The Greatest Common Divisor 191 is a preserved invariant on the states.x;y/. This preserved invariant is, of course, true i ...

Chapter 8 Number Theory192 We’ll prove Theorem 8.2.2 directly by explaining how to findsandt. This job is tackled by a mathemati ...