MATH 242 – Principles of Analysis Solutions for Problem Set 3 – due: Feb. 14

‘A‘ Section

1. A set B is said to be finite if there is some n ∈ N (the number of elements in B), and a one-to-one and onto mapping f : {1, 2, …, n} → B. (Intuitively, we think that f(1) = b_{1}, f(2) = b_{2}, … “counts through” all the elements of B one at a time without repetitions and without missing any elements in B.) For each of the following sets, either show B is finite by determining the n and constructing a mapping f as above, or say why no such mapping exists. a. B = {r = p/q ∈ Q | 1 ≤ q ≤ 4 and 0 < r < 1}

Solution: This is a finite set containing exactly 5 elements:

B = {1/2, 1/3, 2/3, 1/4, 3/4}

We can construct a 1-1 onto mapping from {1, 2, 3, 4, 5} to this B from the order they are listed here: f(1) = 1/2, f(2) = 1/3, f(3) = 2/3, f(4) = 1/4, f(5) = 3/4.

b. B = {r = p/q ∈ Q | 0 < r < 1} Solution: B is not a finite set because, for instance, it contains all of the \frac{1}{n} for n ∈ N.

c. B = {n ∈ Z | |n| ≤ 10^{14}} Solution: B is finite with n = 2 × 10^{14} + 1 elements. f(k) = −2 × 10^{4} − 1 + k defines a 1-1 and onto mapping from {1, 2, …, n} to B.

2. Which of the following sequences converge to 0? Explain your answers, but you do not need to provide complete formal proofs of your assertions. a. {x_{n}}, where

x_{n} = \{ \begin{matrix}2^{n} & if n ≤ 1000 \\ 2^{−n} & if n > 1000 \end{matrix}

Solution: Intuitively, this sequence should converge to 0 since although the first part of it, for n ≤ 1000 grows very rapidly and reaches a huge value 2^{1000} ≐ 10^{300}, once n > 1000, the terms rapidly decrease to 0.

b. {y_{n}}, where

y_{n} = \{ \begin{matrix}1 & if n is evenly divisible by 100 \\ \frac{1}{n} & if n is not evenly divisible by 100 \end{matrix}

Solution: There are arbitrarily large n that are evenly divisible by 100. So there are y_{n} for n arbitarily large such that y_{n} = 1. (Formally, there exists ε > 0, like ε = 1/2, such that for all n_{0}, |y_{n} − 0| > 1/2 for some n ≥ n_{0}.)

c. {z_{n}}, where

z_{n} = \{ \begin{matrix}n & if n is a Mersenne prime number \\ \frac{(−1)^{n}}{n^{2}} & if n is not a Mersenne prime number \end{matrix}

(look these up on Wikipedia and read about them) Solution: The question of whether there are infinitely many Mersenne prime numbers (i.e. primes of the form M = 2^{p} − 1 where p is a prime), is a famous unsolved problem. It is not currently known whether there are infinitely many such primes or not. (As of January 2014, there are 48 of them known.) Hence we don’t know whether this sequence converges or not! If there are infinitely many Mersenne primes, the situation is like that in b. If not, that is, if there are only finitely many Mersenne primes, then the sequence does converge to 0.

3. Let f(x) = [x] be the greatest integer function, defined as [x] = the greatest integer ≤ x. a. If x_{n} → a, does it follow that [x_{n}] → [a]? Prove or give a counterexample.

Solution: This is false because, for instance if x_{n} = 1 − 1/n, then 0 ≤ x_{n} < 1 for all n ≥ 1, so [x_{n}] = 0 for all n. But x_{n} → a = 1, and [a] = [1] = 1.

b. If [x_{n}] → [a], does it follow that x_{n} → a? Prove or give a counterexample. Solution: This is also false. Here’s a counterexample: Let x_{n} = \frac{1}{2} for all n (a constant sequence). Then [x_{n}] = 0 for all n and [x_{n}] → [0]. But x_{n} → 1/2 ≠ 0.

‘B‘ Section

1.

a. Prove that \sqrt{3} is an irrational number.

Solution: Suppose on the contrary that \sqrt{3} = \frac{m}{n} where m, n are integers. We may assume m, n have no common factors (by cancelling any common factors between the numerator and denominator of the fraction). Squaring both sides and clearing denominators, we get 3n^{2} = m^{2}. Since 3 divides m^{2} evenly, 3 must also divide m. In other words m = 3k for some integer k. But then 3n^{2} = 9k^{2} so n^{2} = 3k^{2}. Now, we repeat the same reasoning to claim that 3 must divide n as well. Since we assumed m, n had no common factors, we have reached a contradiction. There can be no integers m, n that satisfy the original equation \sqrt{3} = \frac{m}{n}. Therefore \sqrt{3} is irrational.

b. If r ≠ 0 and s are rational numbers, show that r\sqrt{3} + s is also an irrational number. (Hint: Suppose not and derive a contradiction.) Solution: Suppose r\sqrt{3} + s = x, where x is rational. Then \sqrt{3} = \frac{x−s}{r} must also be rational (Q is closed under sums and quotients). But that contradicts part a. So r\sqrt{3} + s is also irrational.

c. If x = r\sqrt{3} + s and x′ = r′\sqrt{3} + s′ are two numbers as in part b, what can be said about x + x′ and xx′? Are they necessarily irrational too? Solution: No, the sum and product are not necessarily irrational. For instance if x = \sqrt{3} and x′ = −\sqrt{3}, then x+x′ = 0 and xx′ = −3. Both of those are rational.

2. Let A and B be two nonempty sets of real numbers.

a. Assume that x ≤ y for all x ∈ A and y ∈ B. Show that lub A and glb B must exist. Solution: Let y ∈ B (which exists because we assume B is nonempty. By the given information, x ≥ y for every x ∈ A. Therefore, y is an upper bound for A. By the LUB axiom for R, A has a least upper bound in R. Similarly every element of A is a lower bound for B, so glb(B) exists by the result of Corollary 1.5.11 in our text.

b. Under the same assumptions as part a, show that lub A ≤ glb B.

Solution: Let x ∈ A and y ∈ B. Then we have glb(B) ≤ y ≤ x ≤ lub(A) by the given information and the definitions. By transitivity of the order, glb(B) ≤ lub(A).

c. Now assume that A and B are bounded. Is it true that lub A ≤ glb B implies that x ≤ y for all x ∈ A and y ∈ B? Prove or give a counterexample. Solution: This is true. Every x ∈ A satisfies x ≤ lub(A) and every y ∈ B satisfies glb(B) ≤ y. But then under this assumption, x ≤ lub(A) ≤ glb(B) ≤ y. So x ≤ y for all x ∈ A and y ∈ B.

3. Let A be a bounded set of real numbers and let B = {kx | x ∈ A}, where k < 0 is a strictly negative number. Show that B is also bounded. Then, determine formulas for computing lub B and glb B in terms of lub A and glb A, and prove your assertions. Solution: Since A is bounded (i.e. bounded above and below), there exist real numbers ℓ, u such that ℓ ≤ x ≤ u for all x ∈ A. Since k is negative, this implies kℓ ≥ kx ≥ ku. But then B is bounded too, since ku is a lower bound and kℓ is an upper bound for B. Noting the reversal of the inequalities that occurred here, we claim that

(a) lub(B) = kglb(A), and

(b) glb(B) = klub(A).

To prove (a), write m = glb(A). By the definition, this means first that x ≥ m for all x ∈ A. But then kx ≤ km, and hence km is an upper bound for B. Next we assume that u is any other upper bound for B, so kx ≤ u for all x ∈ A. But this implies x ≥ \frac{u}{k} for all x ∈ A. So since m is the greatest lower bound for A, we have m ≥ \frac{u}{k}. But that implies km ≤ u. Therefore, km = lub(B). The proof of (b) is similar: write M = lub(A). By the definition, this means first that x ≤ M for all x ∈ A. But then kx ≥ kM, and hence kM is a lower bound for B. Next we assume that ℓ is any other lower bound for B, so kx ≥ ℓ for all x ∈ A. But this implies x ≤ \frac{ℓ}{k} for all x ∈ A. So since M is the least upper bound for A, we have M ≤ \frac{ℓ}{k}. But that implies kM ≥ ℓ. Therefore, kM = glb(B).

4. Determine whether each of the following sequences converge and prove your assertions using the ε, n_{0} definition of convergence. a. x_{n} = \frac{3n^{2}}{n^{2}+5}

Solution: This sequence converges to a = 3. Proof: Let ε > 0. Since N is not bounded in R, no matter how big \sqrt{\frac{15}{ε}} is, there exist n_{0} > \sqrt{\frac{15}{ε}} in N, and for any such n_{0}, n_{0}^{2} > \frac{15}{ε} (since the squaring function is increasing for positive inputs), and hence \frac{15}{n_{0}^{2}} < ε. Then for all n ≥ n_{0}, we have

|x_{n} − 3| = |\frac{−15}{n^{2} + 5}| < \frac{15}{n^{2}} ≤ \frac{15}{n_{0}^{2}} < ε.

This shows x_{n} → 3 as n → ∞ by the definition. b. x_{n} = \frac{1}{ln(n)} Solution: This sequence converges to a = 0. Proof: Let ε > 0. Since N is not bounded in R, no matter how big e^{\frac{1}{ε}} is, there exist n_{0} > e^{\frac{1}{ε}} in N, and for any such n_{0}, ln(n_{0}) > \frac{1}{ε} (since ln is increasing), and hence \frac{1}{ln(n_{0})} < ε. Then for all n ≥ n_{0}, we have

|x_{n} − 0| = |\frac{1}{ln(n)}| = \frac{1}{ln(n)} ≤ \frac{1}{ln(n_{0})} < ε.

This shows x_{n} → 0 as n → ∞ by the definition. c. x_{n} = cos(nπ).

Solution: We have cos(nπ) = 1 if n is even and cos(nπ) = −1 if n is odd. Therefore x_{n} = cos(nπ) is not convergent.