Math 28 Spring 2009 Exam 1

Math 28 Spring 2009: Exam 1 Instructions: Each problem is scored out of 10 points for a total of 50 points. You may not use any outside materials(eg. notes or calculators). You have 50 minutes to complete this exam. Problem 1. Using the definition of convergence show that a monotone sequence converges if and only if it is bounded. Proof. Let {an } be a monotone sequence. Assume first that {an } converges to a limit a. Let ² = 1. Then there exists an N ∈ N such that an ∈ V² (a) for all n ≥ N . Let M = max(|a1 | , . . . , |aN −1 | , |a| + 1). Consider an for an arbitrary n ∈ N. If an ∈ V² (a) then |an | < |a| + 1 ≤ M . Otherwise n ∈ {1, . . . , N − 1} and then clearly an ≤ M . Assume now that {an } is bounded. Then the set {an | n ∈ N} is a bounded subset of R. If {an } is decreasing, then {−an } is increasing, so we may assume that {an } is an increasing sequence. Let a = sup({an | n ∈ N}). Let ² > 0. By the characterization of supremum there exists an N ∈ N such that aN > a − ². In other words aN ∈ V² (a). Since {an } is increasing and a is an upper bound, we must have aN ≤ an ≤ a for all n ≥ N and hence an ∈ V² (a). So we have shown that for any ² > 0, there exists an N ∈ N such that for all n ≥ N, an ∈ V² (a). Therefore, {an } converges to a. Therefore a monotone sequence converges if and only if it is bounded. Problem 2. Apply the Cauchy Criterion to each of the following series. P∞ 1 (a) n=1 n! . P∞ 2n (b) n=1 n2 +1 . Proof. (a) Let ² > 0, and let N ∈ N be such that N1 < ². Let m > n ≥ N , and write m = n + k. Let sn be the nth partial sum of the series. Then we have |sn+k − sn | = < = = < 1 1 + ··· + (n + 1)! (n + k)! 1 1 + ··· + (n + 1)n (n + k)(n + k − 1) 1 1 1 1 − + ··· + − n n+1 n+k n+k+1 1 1 − n n+k+1 1 1 ≤ <² n N So this series converges by the Cauchy Criterion. (b) Let sn be the nth partial sum of the series, and let tn be the nth partial sum of the harmonic series. Let ² > 0, then let N ∈ N and m > n ≥ N be such that |tm − tn | ≥ ² (such values exist since the harmonic series diverges). Now consider 2n 1 2n ≥ 2 = 2 +1 n +n n n2 1 ∀n ∈ N. so we have 2(n + 1) 2m + ··· + 2 (n + 1)2 + 1 m +1 2(n + 1) 2m ≥ + ··· + 2 (n + 1)2 + (n + 1)2 m + m2 1 1 + ··· + = n+1 m = |tm − tn | ≥ ². |sm − sn | = Problem 3. Provide an example (or state why it is not possible) for each of the following. (a) A sequence of nested intervals whose intersection is empty. (b) A convergent sequence with a subsequence which is strictly increasing and a subsequence which is strictly decreasing. (c) A Cauchy sequence which is not monotone. Proof. (a) Let In = (0, 1/n) for all n ∈ N. Then ∩∞ n=0 In = ∅, since by the archimedean property any real number x is not in one of the (0, 1/n) since we can always find an n ∈ N such that 1/n < x. (b) Define a sequence {an } by an = (−1)n n1 for all n ∈ N. This is an alternating sequence which converges to 0. The subsequence of positive terms is strictly decreasing, while the subsequence of negative terms is strictly increasing. (c) Define a sequence {an } by an = (−1)n n1 for all n ∈ N. This is an alternating sequence which converges therefore is also Cauchy. It is not monotone since it is alternating. Problem 4. Determine the cardinality of the set {(x, y) | x, y ∈ Q}. Proof. We know that Q is countable, so we can enumerate Q as {q1 , q2 , . . .}. Now we can write (x, y) ∈ Q × Q as a matrix A = (aij ) as (qi , qj ). Now we use the function f : N → A determined by sending the images of N to the entries as described in the following matrix.   f (1) f (3) f (6) f (10) · · · f (2) f (5) f (9)  ···   f (4) f (8) · · ·   . f (7) · · ·    .. . This map f clearly hits every entry eventually since every diagonal is finite and hits every entry only once so provides a 1-1 onto correspondence between N and Q × Q. 2 This method is equivalent to decomposing Q × Q into sets An = {(qi , qj ) | i + j = n} for n ≥ 2. These sets are all finite and we map N sequentially to all of A2 then to all of A3 and so on. Note that we could also write this as a countable union of countable sets {(x, y) | x, y ∈ Q} = ∪x∈Q {(x, y) | y ∈ Q}. Problem 5. Define a sequence recursively by an+1 = a2n − an + 1 for all n ∈ N with a1 = 12 . Determine the convergence or divergence of this sequence. If it converges, find the value of convergence. Proof. Monotone: We have a1 = 1/2 ≤ a2 = 34 so proceed by induction. We assume an ≥ an−1 for all n < N for some N ∈ N. We will show aN +1 − aN ≥ 0. Consider ¢ ¡ aN +1 − aN = (a2N − aN + 1) − aN = a2N − 2aN + 1 = (aN − 1)2 ≥ 0 Bounded: We will show by induction that the sequence is bounded above by 1. It is clearly true for a1 = 12 . Now assume an ≤ 1 for all n < N for some N ∈ N. Consider aN = a2N −1 − aN −1 + 1. Since aN −1 ≤ 1 we have a2N −1 ≤ aN −1 and hence a2N −1 − aN −1 ≤ 0, so we have aN = a2N −1 − aN −1 + 1 ≤ 1. Since it is increasing we have that a1 = 12 is a lower bound. From the Monotone Convergence Theorem we have convergence an → a, so applying the ALT we know that a = a2 − a + 1 and hence a = 1. 3