Mathematics 242 – Principles of Analysis Solutions for Problem Set 4 Due: March 1, 2013

‘A’ Section

1. Using the ‘Big Theorem’ on limits of sequences (Theorem 2.2.5 in the text), find the limit of each of the following:

(a) x_{n} = \frac{(3^{n}+4^{n/2})^{2}}{9^{n}}

Solution: Expanding the top by the binomial theorem, then dividing by 9^{n}, we have

\begin{aligned}x_{n} & = \frac{9^{n} + 2 · 6^{n} + 4^{n}}{9^{n}} \\ & = 1 + 2 · (6/9)^{n} + (4/9)^{n}. \end{aligned}

Hence by Theorem 2.2.5(a), and the fact that (6/9)^{n} → 0 and (4/9)^{n} → 0, the limit is 1.

(b) x_{n} = \sqrt{n}(\sqrt{16n + 3} − 4\sqrt{n}) (Hint: \sqrt{a} − \sqrt{b} = \frac{a−b}{\sqrt{a}+\sqrt{b}} – do you see why? Also, you may use the result of question 1 in the B section if needed.)

Solution: By the algebraic identity in the Hint, we have:

x_{n} = \sqrt{n} · \frac{(16n + 3) − 16n}{\sqrt{16n + 3} + 4\sqrt{n}}

= \frac{3\sqrt{n}}{\sqrt{16n + 3} + 4\sqrt{n}}

= \frac{3}{\sqrt{16 + 3/n} + 4}.

By Theorem 2.2.5(c) and question 1 in the B section, lim_{n→∞} x_{n} = \frac{3}{8}.

(c) x_{n} = \frac{1}{n^{4}} ∑_{k=0}^{4} \binom{n}{k} \frac{1}{2^{k}}. (The \binom{n}{k} are the binomial coefficients as in Problem Set 2.)

Solution: By the definition, after cancellation

\binom{n}{k} = \frac{n!}{k!(n − k)!} = \frac{n(n − 1) ⋯ (n − (k − 1))}{k!},

with k factors on the top. As a polynomial in n, the degree of the top is k. Hence, for k < 4, we will have lim_{n→∞} \frac{1}{n^{4}} \binom{n}{k} = 0 and lim_{n→∞} \frac{1}{n^{4}} \binom{n}{4} = \frac{1}{4!} by applying the Limit Sum Rule. Therefore

lim_{n→∞} x_{n} = \frac{1}{4!} · \frac{1}{2^{4}} = \frac{1}{384}.

2. For each of the following statements, first say whether the statement is true. Then, if the statement is true, give a reason; if it is false give a counterexample.

(a) Let {x_{n}} and {y_{n}} be sequences. If it is known that {x_{n}} and {x_{n} + y_{n}} converge, then {y_{n}} converges too.

Solution: This is true, since we can apply part (a) of Theorem 2.2.5 to deduce that y_{n} = (x_{n} + y_{n}) − x_{n} converges.

(b) If {x_{n}} and {y_{n}} both diverge, then so does {x_{n} · y_{n}}.

Solution: This is false. A counterexample: Let x_{n} = (−1)^{n} = y_{n}. Then both x_{n} and y_{n} diverge, but x_{n} · y_{n} is the constant sequence 1, which certainly converges.

(c) If x_{n} → a, y_{n} → b and x_{n} < y_{n} for all n ∈ N, then a < b.

Solution: This is false. Consider x_{n} = \frac{1}{2n} and y_{n} = \frac{1}{n}, for instance. Then x_{n} < y_{n} for all n ≥ 1. But x_{n} → 0 and y_{n} → 0 also. (The thing that is true is a ≤ b. See Theorem 2.2.7 in the text.)

(d) If x_{n} > 0 and \frac{x_{n+1}}{x_{n}} ≤ 1 for all n ≥ 1, then x_{n} → 0.

Solution: This is also false. The given information says x_{n} is strictly positive for all n, hence x_{n+1} ≤ x_{n}. So x_{n} is a monotone decreasing sequence that is bounded below by 0. It must converge, but not necessarily to zero. For example x_{n} = 1 + \frac{1}{n} satisfies all the conditions, but x_{n} → 1.

3. For each of the following sequences, first explain why the sequence is monotonic and bounded, then determine the limit:

(a) x_{n+1} = \sqrt{6 + x_{n}}, x_{1} = 1.

Solution: We have x_{1} = 1 and x_{2} = \sqrt{7} > 1. Now assume we know x_{k+1} > x_{k} and consider x_{k+2} = \sqrt{6 + x_{k+1}}. Since x_{k+1} > x_{k}, we have 6 + x_{k+1} > 6 + x_{k}, hence x_{k+2} = \sqrt{6 + x_{k+1}} > \sqrt{6 + x_{k}} = x_{k+1}. By induction, it follows that x_{n} is a monotone strictly increasing sequence. We claim next that x_{n} is bounded above. For instance, we claim x_{n} < 10 for all n. This can also be proved by induction: x_{1} = 1 < 10 for the base case. If we assume x_{k} < 10, then x_{k+1} = \sqrt{6 + x_{k}} < \sqrt{6 + 10} = 4 < 10 also. Therefore by induction, x_{n} is bounded above. By the Monotone Convergence Theorem, it follows that x_{n} converges to some α ∈ R. If we take the limit as n → ∞ in the recursion equation, we get

α = lim_{n→∞} x_{n+1} = \sqrt{6 + lim_{n→∞} x_{n}} = \sqrt{6 + α}

Squaring, we get α^{2} = 6 + α, which has the roots α = 3, −2. Since x_{n} > 0 for all n, the limit must be α = 3.

(b) x_{n+1} = \frac{4x_{n}+7}{10}, x_{1} = 2.

Solution: We hve x_{1} = 2 and x_{2} = \frac{15}{2} = \frac{3}{2}. Assuming x_{k+1} ≤ x_{k}, consider

x_{k+2} = \frac{4x_{k+1} + 7}{10} ≤ \frac{4x_{k} + 7}{10} = x_{k+1}.

By induction the sequence is monotone decreasing. It is easy to see that x_{n} > 0 for all n, so the sequence is also bounded below, hence converges to some β ∈ R. Taking limits as in part (a), we get β = \frac{4β+7}{10}, so β = \frac{7}{6}.

‘B’ Section

1. Let a > 0. Show that if x_{n} → a and x_{n} ≥ 0 for all n, then \sqrt{x_{n}} → \sqrt{a}. (Hint: See part (b) of question 1 in the A section.)

Solution: Let ε > 0. Since x_{n} → a, there exists a natural number n_{0} such that |x_{n} − a| < ε\sqrt{a} for all n ≥ n_{0}. Then for all n ≥ n_{0} we have, using the identity from question 1 in the A section:

|\sqrt{x_{n}} − \sqrt{a}| = |\frac{x_{n} − a}{\sqrt{x_{n}} + \sqrt{a}}| ≤ \frac{|x_{n} − a|}{\sqrt{a}} < \frac{ε\sqrt{a}}{\sqrt{a}} = ε.

This shows \sqrt{x_{n}} → \sqrt{a}.

2. In this problem, you will show that the sequence x_{n} = ∑_{k=1}^{n} \frac{1}{k!} converges.

(a) First show that \frac{1}{k!} ≤ \frac{1}{2^{k−1}} for all integers k ≥ 1.

Solution: With k = 1, we have 1 ≤ 1 so the base case for an induction is established. Now assume that the inequality has been shown for k = ℓ and consider

\frac{1}{(ℓ + 1)!} = \frac{1}{ℓ!} · \frac{1}{ℓ + 1} ≤ \frac{1}{2^{ℓ−1}} · \frac{1}{2} = \frac{1}{2^{ℓ}} .

Hence the inequality is true for all k ≥ 1.

(b) Show that for all n ≥ 1,

1 + \frac{1}{2} + ⋯ + \frac{1}{2^{n−1}} = \frac{1 − \frac{1}{2^{n}}}{1 − \frac{1}{2}}

and deduce that x_{n} is bounded above by 2.

Solution: Let y_{n} = 1 + \frac{1}{2} + ⋯ + \frac{1}{2^{n−1}} . We see that y_{n} − \frac{1}{2}y_{n} “telescopes” as follows:

y_{n} − \frac{1}{2}y_{n} = 1 − \frac{1}{2^{n}} , hence y_{n} = \frac{1 − \frac{1}{2^{n}}}{1 − \frac{1}{2}}

as claimed. (This can also be proved by induction, of course.) Note that after some rearrangement,

y_{n} = 2 − \frac{1}{2^{n−1}} < 2

for all n. To make the connection with x_{n} above, we apply the inequality from part (a) term by term to the sum in the formula for x_{n}:

x_{n} = \frac{1}{1!} + \frac{1}{2!} + ⋯ + \frac{1}{n!} ≤ 1 + \frac{1}{2} + ⋯ + \frac{1}{2^{n−1}} = y_{n}

Combining these observations we have

x_{n} = ∑_{k=1}^{n} \frac{1}{k!} ≤ ∑_{k=1}^{n} \frac{1}{2^{n}} < 2

(c) Use part (b) to show that x_{n} converges.

Solution: We see x_{n} is a monotone increasing sequence since the terms that are added into x_{n} are all positive. Hence x_{n+1} = x_{n} + \frac{1}{(n+1)!} > x_{n} for all n ≥ 1. By part (b) x_{n} is also bounded above. It follows from the Monotone Convergence Theorem that x_{n} converges to some α ∈ R. (The limit is actually the number e − 1 (where e is the base of the natural logarithms).

3. In class, we proved the Monotone Convergence Theorem for sequences, the result stated as Theorem 2.3.3 in the text. In the proof we used the Least Upper Bound Axiom in a crucial way. It is an interesting fact that the implication goes the other way too. Namely if we assume that monotone increasing sequences of reals always converge to real numbers, it follows that that every set of reals that is bounded above has a least upper bound. You will show this in this problem using the following construction. Let A be any nonempty set of real numbers that is bounded above. The proof is based on constructing two sequences x_{n} and y_{n} by this inductive procedure:

(i) Let x_{1} ∈ A be any element of A, and let y_{1} be any upper bound for A. (ii) Assuming x_{k} and y_{k} have been constructed such that x_{k} ∈ A and y_{k} is an upper

bound for A, find x_{k+1} and y_{k+1} like this: Let m_{k} = \frac{x_{k}+y_{k}}{2} . If m_{k} is also an upper bound for A, then set x_{k+1} = x_{k} and y_{k+1} = m_{k}. Otherwise, there is some x ∈ A with m_{k} < x ≤ y_{k}, and in this case let x_{k+1} = x and y_{k+1} = y_{k}.

Note that an easy induction argument shows that this construction will produce sequences such that x_{n} ∈ A for all n ≥ 1 and y_{n} is an upper bound for A for all n ≥ 1.

Now prove the following statements to show that A has a least upper bound in R assuming the Monotone Convergence Theorem:

(a) Prove that both sequences {x_{n}} and {y_{n}} converge to elements of R, using the Monotone Convergence Theorem and its Corollary.

Solution: The x_{n} are all bounded above by y_{1} and the y_{n} are all bounded below by x_{1}. By the construction, we also see x_{n} is monotone increasing (whenever x_{n+1} ≠ x_{n}, we necessarily have x_{n+1} > x_{n}), and similarly y_{n} is monotone decreasing. Therefore both sequences converge in R by the Monotone Convergence Theorem and its Corollary.

(b) Show that lim_{n→∞} x_{n} = lim_{n→∞} y_{n} by showing that |x_{n} − y_{n}| ≤ \frac{|x_{1}−y_{1}|}{2^{n−1}} for all n ≥ 1.

Solution: First, note that each time we go from one integer k to the next integer k +1, the construction of the sequences x_{n} and y_{n} using the midpoints m_{n} shows

|x_{k+1} − y_{k+1}| ≤ \frac{1}{2}|x_{k} − y_{k}|.

It follows that |x_{n} − y_{n}| ≤ \frac{|x_{1}−y_{1}|}{2^{n−1}} for all n ≥ 1 as claimed. Now, say lim_{n→∞} x_{n} = α and lim_{n→∞} y_{n} = β. We want to show that α = β. To see this, note that we have, for all n,

x_{n} ≤ α ≤ β ≤ y_{n}

Therefore

|α − β| ≤ |x_{n} − y_{n}| = \frac{|x_{1} − y_{1}|}{2^{n−1}}

for all n ≥ 1. Since \frac{1}{2^{n−1}} → 0 as n → ∞, while |x_{1} − y_{1}| is constant, it follows that

|α − β| = 0, hence α = β.

(c) Let α be the common limit of the x_{n} and y_{n} sequences. Show that α = lub(A) by showing it satisfies the definition of a least upper bound.

Solution: We must show first that α ≥ x for all x ∈ A, and second that no number α − ε for ε > 0 is an upper bound for A. The first statement follows since each of the y_{n} satisfy y_{n} ≥ x for all x ∈ A. It follows from Theorem 2.2.7 in the text (applied to the y_{n} sequence and the constant sequence z_{n} = x) that lim_{n→∞} y_{n} = α ≥ x for all x ∈ A. Now let ε > 0 and consider α − ε. Since we have lim_{n→∞} x_{n} = α, it follows that there exists an n_{0} ∈ N such that α − ε < x_{n_{0}} ≤ α. Since x_{n_{0}} ∈ A, it follows that α − ε is not an upper bound for A. Therefore α = lub(A).