Due Sept 19: Sect 1.2, Nos. 1,2,3,6,8
Sect 1.3, Nos. 1,2,3,4,7 Note misprints: 2(c) should read: "The union of two countable sets is countable." 7 should read: "Suppose that for each natural number n the set..." 8(c) should read: "The set of functions from a countable set to a finite set."
Due Sept 26: Sect 2.1, Nos. 1,2,5,6
Sect 2.2, Nos. 2,4,5,8
Sect 2.4, Nos. 1,6,7
The Catalan numbers are the sequence defined by C(1) = 1, C(2) = 1, and the recursion relation:
C(n) = C(1)C(n-1) + C(2)C(n-2) + ... + C(n-2)C(2) + C(n-1)C(1). So for example C(3) = 2, C(4) = 5, C(5) = 14, etc.
Let 2n points be placed around the circumference of a circle and labelled 0,1,2,...,2n-1. An n-chord configuration is a set of n non-intersecting chords in the circle, with end points at 0,1,2,...,2n-1. Prove that for any integer n, the number N(n) of distinct n-chord configurations is equal to the Catalan number C(n+1).
Hint: Let P(n+1)=N(n) to get the indices to match; set P(1) = N(0) = 1; show that P(2) = 1; and show that the P's satisfy the same recursion relation as the C's. To do this count separately the configurations in which the chord from 0 goes to 1, to 3, to 5, etc. Finally use induction to show that the same start and the same recursion relation implies that the two sequences are the same.
Due Oct 3: Sect 2.5, Nos. 1(a,b),3,4
Sect 2.6, Nos. 1,3,4.
No homework for October 10 (Midterm Exam).
Due October 17: Sect 3.1, Nos. 1,2,6,8,9,11,12.
Due October 24: Sect 3.2, Nos. 1,2,3,5,6 and the following
exercises in ``logic"
a) give the negation of the statement: ``Every person in this room has at least ten dollars."
b) give the negation of the statement: ``Every person in this room who has at least ten dollars is at most eighteen years old."
c) for each of the two definitions we have of ``f is continuous at x" state the negation: what it means for f NOT to be continuous at x.
d) take the definition in the book of ``f is uniformly continuous on the interval (a,b)" and state its negation: what it means for f to be NOT uniformly continuous.
e) take the definition of ``L is the limit of the sequence a_n" (a sub n) and state its negation: how do you know when L is NOT the limit of the sequence a_n?
Due October 31: Sect 3.2, Nos. 7,8,9,10,11.
Due November 7: Sect 3.3, Nos. 1,2,3,4,7,10
Sect 3.4, No. 1.
Due November 14: Sect 3.5, Nos. 1,2,3,5ab,6,7a,9.
Due November 21: Sect 4.1, Nos. 1,4,5,6,8
Sect 4.2, Nos. 1,3,5,6,7,8,11
Due Tuesday December 10: Sect 4.3, Nos. 1,2 (interpret ``the
first few" as ``the first five"),3,5,6 (use polynomials at x_0 = 9)
Sect 4.4 Nos. 1,2 (you may use your calculator for a rough location of the roots, and for implementing the steps of Newton's method), 6.
Due December 12: Sect 5.1, Nos. 1,2,3,8,12
Sect 5.2, Nos. 2,4,5,6
Sect 9.2, Nos. 1,2,3.