Serendipity
106
Common Definitions
107
SECTiOn 2.1 Review
107
ExErCiSES 2.1
107
2.2 INDUCTION
110
First Principle of Induction
110
Proofs by Mathematical
Induction
112
Second Principle of Induction
118
SECTiOn 2.2 Review
122
ExErCiSES 2.2
122
2.3 MORE ON PROOF OF
CORRECTNESS
129
Loop Rule
129
Euclidean Algorithm
133
special interest page
Making Safer Software
136
SECTiOn 2.3 Review
137
ExErCiSES 2.3
137
2.4 NUMBER THEORY
143
The Fundamental Theorem
of Arithmetic
144
More on Prime Numbers
148
Euler Phi Function
149
SECTiOn 2.4 Review
152
ExErCiSES 2.4
152
Chapter 2 Review
155
On the Computer
156
CHAPTEr 3
recursion, recurrence
relations, and Analysis
of Algorithms
157
3.1 RECURSIVE DEFINITIONS
158
Recursively Defined Sequences
158
Recursively Defined Sets
162
Recursively Defined Operations
165
Recursively Defined Algorithms
166
SECTiOn 3.1 Review
171
ExErCiSES 3.1
171
3.2 RECURRENCE RELATIONS
180
Linear First-Order Recurrence
Relations
180
Expand, Guess, and Verify
180
A Solution Formula
182
Linear Second-Order
Recurrence Relations
188
Divide-and-Conquer
Recurrence Relations
193
SECTiOn 3.2 Review
197
ExErCiSES 3.2
197
3.3 ANALYSIS OF ALGORITHMS
203
The General Idea
203
Analysis Using Recurrence
Relations
206
Upper Bound
(Euclidean Algorithm)
210
special interest page
Of Trees % and Pancakes
211
SECTiOn 3.3 Review
212
ExErCiSES 3.3
212
Chapter 3 Review
217
On the Computer
218
CHAPTEr 4
Sets, Combinatorics,
and Probability
221
4.1 SETS
222
Notation
222
Relationships Between Sets
224
Sets of Sets
227
Binary and Unary Operations
228
Operations on Sets
230
Set Identities
233
Countable and Uncountable Sets
236
SECTiOn 4.1 Review
239
ExErCiSES 4.1
239
4.2 COUNTING
252
Multiplication Principle
252
Addition Principle
254
Using the Principles Together
255
Decision Trees
257
viii
Contents
106
Common Definitions
107
SECTiOn 2.1 Review
107
ExErCiSES 2.1
107
2.2 INDUCTION
110
First Principle of Induction
110
Proofs by Mathematical
Induction
112
Second Principle of Induction
118
SECTiOn 2.2 Review
122
ExErCiSES 2.2
122
2.3 MORE ON PROOF OF
CORRECTNESS
129
Loop Rule
129
Euclidean Algorithm
133
special interest page
Making Safer Software
136
SECTiOn 2.3 Review
137
ExErCiSES 2.3
137
2.4 NUMBER THEORY
143
The Fundamental Theorem
of Arithmetic
144
More on Prime Numbers
148
Euler Phi Function
149
SECTiOn 2.4 Review
152
ExErCiSES 2.4
152
Chapter 2 Review
155
On the Computer
156
CHAPTEr 3
recursion, recurrence
relations, and Analysis
of Algorithms
157
3.1 RECURSIVE DEFINITIONS
158
Recursively Defined Sequences
158
Recursively Defined Sets
162
Recursively Defined Operations
165
Recursively Defined Algorithms
166
SECTiOn 3.1 Review
171
ExErCiSES 3.1
171
3.2 RECURRENCE RELATIONS
180
Linear First-Order Recurrence
Relations
180
Expand, Guess, and Verify
180
A Solution Formula
182
Linear Second-Order
Recurrence Relations
188
Divide-and-Conquer
Recurrence Relations
193
SECTiOn 3.2 Review
197
ExErCiSES 3.2
197
3.3 ANALYSIS OF ALGORITHMS
203
The General Idea
203
Analysis Using Recurrence
Relations
206
Upper Bound
(Euclidean Algorithm)
210
special interest page
Of Trees % and Pancakes
211
SECTiOn 3.3 Review
212
ExErCiSES 3.3
212
Chapter 3 Review
217
On the Computer
218
CHAPTEr 4
Sets, Combinatorics,
and Probability
221
4.1 SETS
222
Notation
222
Relationships Between Sets
224
Sets of Sets
227
Binary and Unary Operations
228
Operations on Sets
230
Set Identities
233
Countable and Uncountable Sets
236
SECTiOn 4.1 Review
239
ExErCiSES 4.1
239
4.2 COUNTING
252
Multiplication Principle
252
Addition Principle
254
Using the Principles Together
255
Decision Trees
257
viii
Contents