24 Monotone Sequence, MCT, and Cauchy Condensation Test

#todo/school : Do problems 2.4.1, 2, 3, 2.4.5, 6, 7, 8 📅 2024-10-27 ✅ 2024-10-24

2.4.1

Question

a. Prove that the sequence defined by $x_{1} = 3$ and:

x_{n + 1} = \frac{1}{4 - x_{n}}

converges.
b. Now that we know that $x_{n}$ 's limit exists, explain why $lim x_{n + 1}$ must also exist and equal the same value.
c. Take the limit of each side of the recursive equation in (a) to explicitly compute $lim x_{n}$ .

Proof
a. Using the MCT, all we have to show is that $x_{n}$ is bounded below and decreasing.

For the boundedness, we'll show it's bounded below by $0$ by induction. Clearly for the base case $x_{1} = 3 > 0$ so suppose that it's bounded below by $0$ for all $k < n$ for some $n \in N$ . For the $k + 1$ case notice that:

x_{k + 1} = \frac{1}{4 - x_{k}} \underset{x_{k} > 0}{\underset{⏟}{>}} \frac{1}{4} > 0

thus completing the inductive step.

For decreasing, via induction notice that $x_{2} = 1$ so $x_{2} \leq x_{1}$ for our base case. In general if we have the theorem holds up under $n$ then starting with our inductive hypothesis:

x_{n} \geq x_{n + 1} \Rightarrow 4 - x_{n} \leq 4 - x_{n + 1} \Rightarrow \frac{1}{4 - x_{n}} = x_{n + 1} \geq \frac{1}{4 - x_{n + 2}} = x_{n + 2}

Thus showing the inductive step.

b. If $(x_{n}) \to L$ then by the definition of convergence then $\forall ε > 0$ then choose $N \in N$ where for any $n \geq N$ then $| x_{n} - L | < ε$ . Let $ε > 0$ be arbitrary. Then we can choose such and $N$ . Notice that $n + 1 > n \geq N$ so then $| x_{n + 1} - L | < ε$ as desired. This shows that $(x_{n + 1}) \to L$ as needed, showing even that the limit value must be the same.

c. Notice that the left and right side limits must equal the same limit $L$ , so substitute it and solve:

\begin{aligned} lim x_{n + 1} & = lim \frac{1}{4 - x_{n}} \\ L & = \frac{1}{4 - lim x_{n}} \\ L & = \frac{1}{4 - L} \\ 4 L - L^{2} - 1 & = 0 \\ \Rightarrow L & = \frac{- 4 \pm \sqrt{16 - 4 (- 1) (- 1)}}{- 2} \\ L & = 2 \pm \frac{\sqrt{12}}{2} \\ L & = 2 \pm \sqrt{3} \end{aligned}

Now notice that since $x_{n}$ is decreasing and since $x_{1} = 3$ then $L \neq 2 + \sqrt{3}$ since then it would have to increase, which is a contradiction. Instead we must have that $L = 2 - \sqrt{3}$ .
☐

2.4.2

Question

a. Consider the recursively defined sequence $y_{1} = 1$ and:

y_{n + 1} = 3 - y_{n}

and set $y = lim y_{n}$ . Because $(y_{n}), (y_{n + 1})$ have the same limit, taking the limit across the recursive equation gives $y = 3 - y \Rightarrow lim y_{n} = \frac{3}{2}$ .
What is wrong with this argument?
b. This time set $y_{1} = 1$ and $y_{n + 1} = 3 - \frac{1}{y_{n}}$ . Can the strategy in (a) be applied to compute the limit of this sequence?

Proof
a. This is wrong because we are assuming, instead of trying to show, that $y_{n}$ converges in the first place. In this case it actually doesn't since $(y_{n}) = {\begin{cases} 1 & x is odd \\ 2 & x is even \end{cases}$ which clearly doesn't converge.

b. We should verify (in this case) that it's monotone and thus $y_{n}$ is increasing (since notice $y_{2} = 2$ so it's only monotone if it's increasing) and bounded.

First, clearly it seems to be increasing so let's show it. Let's do bounded first. Notice for induction that $y_{1} \leq 3$ as our base case. Doing the inductive step:

\begin{aligned} y_{n + 1} & = 3 - \frac{1}{y_{n}} & y_{n} \leq 3 ⟺ \frac{1}{y_{n}} \geq \frac{1}{3} \\ \leq 3 \end{aligned}

Thus we are bounded above by 3.

To show it's increasing, notice that $y_{2} \geq y_{1}$ for our base case. For the inductive step notice that:

\begin{aligned} y_{n + 1} \geq y_{n} & ⟺ \frac{1}{y_{n}} \geq \frac{1}{y_{n + 1}} \\ ⟺ \frac{- 1}{y_{n}} \leq \frac{- 1}{y_{n + 1}} \\ ⟺ 3 - \frac{1}{y_{n}} \leq 3 - \frac{1}{y_{n + 1}} \\ ⟺ y_{n + 1} \leq y_{n + 2} \\ ⟺ y_{n + 2} \geq y_{n + 1} \end{aligned}

Thus this completes the induction showing it's increasing.

To find the limit, now we can do what (a) describes:

y = 3 - \frac{1}{y} \Rightarrow y^{2} - 3 y + 1 = 0 \Rightarrow y = \frac{3 \pm \sqrt{5}}{2}

Notice that since we are increasing and $y_{1} = 1$ then we can't have the $-$ case, so then:

y = \frac{3 + \sqrt{5}}{2}

☐

2.4.3

Question

a. Show that:

\sqrt{2}, \sqrt{2 + \sqrt{2}}, \sqrt{2 + \sqrt{2 + \sqrt{2}}}, \dots

converges and find the limit.
b. Does the sequence:

\sqrt{2}, \sqrt{2 \sqrt{2}}, \sqrt{2 \sqrt{2 \sqrt{2}}}, \dots

converge? If so find the limit.

Proof
a. Notice that this is represented by the sequence $(a_{n})$ where $a_{1} = \sqrt{2}$ and:

a_{n + 1} = \sqrt{2 + a_{n}}

We'll show that this is increasing and bounded, thus using the Monotone Convergence Theorem will show it converges.

It helps to see what the limit should be if it is convergent:

\begin{aligned} lim a_{n + 1} & = lim a_{n} \\ \sqrt{2 + L} & = L \\ 2 + L & = L^{2} \\ 0 & = L^{2} - L - 2 \\ \Rightarrow L & = \frac{1 \pm \sqrt{1 - 4 (- 2)}}{2} \\ L & = \frac{1 \pm 3}{2} \\ L & = 2 & Assume increasing (show later) \end{aligned}

First let's show it's bounded above. We'll show $a_{n} \leq 2$ . Notice that $a_{1} = \sqrt{2} \leq 2$ so for the inductive step, notice that:

\begin{aligned} ⟺ a_{n + 1} & \leq 2 \\ ⟺ \sqrt{2 + a_{n}} & \leq 2 \\ ⟺ 2 + a_{n} & \leq 4 \\ ⟺ a_{n} & \leq 2 \end{aligned}

Which is true by the inductive hypothesis.

To show that it's increasing, notice that $a_{1} \leq a_{2}$ (you can see the decimal expansions to verify). Now for the inductive step:

\begin{aligned} ⟺ a_{n} & \geq a_{n - 1} & Ind. Hyp. \\ ⟺ 2 + a_{n} & \geq 2 + a_{n - 1} \\ ⟺ \sqrt{2 + a_{n}} & \geq \sqrt{2 + a_{n - 1}} \\ ⟺ a_{n + 1} & \geq a_{n} \end{aligned}

Thus the limit converges. Thus we can find the limit, which we found before:

a_{n} \to 2

b. For scratch, the sequence is given where $a_{1} = \sqrt{2}$ and:

a_{n + 1} = \sqrt{2 a_{n}}

If it did converge then we expect the limit to be:

\begin{aligned} lim a_{n + 1} & = lim \sqrt{2 a_{n}} \\ L & = \sqrt{2 L} \\ L^{2} - 2 L & = 0 \\ L (L - 2) & = 0 \end{aligned}

Clearly the sequence seems to be increasing so then $L = 2$ must be the only limit it can approach.

Let's show that the sequence is bounded by $L = 2$ . Notice that $a_{1} \leq 2$ so let's do the inductive step. Notice:

\begin{aligned} ⟺ & a_{n} \leq 2 & Ind. Hyp. \\ ⟺ & 2 a_{n} \leq 4 \\ ⟺ & \sqrt{2 a_{n}} \leq 2 \\ ⟺ & a_{n + 1} \leq 2 \end{aligned}

Finishing the inductive step.

Let's show it's increasing. Notice that $a_{1} \leq a_{2}$ for our base case. Notice now for the inductive step:

\begin{aligned} ⟺ & a_{n - 1} \leq a_{n} & Ind. Hyp. \\ ⟺ & 2 a_{n - 1} \leq 2 a_{n} \\ ⟺ & \sqrt{2 a_{n - 1}} \leq \sqrt{2 a_{n}} \\ ⟺ & a_{n} \leq a_{n + 1} \end{aligned}

Finishing the induction.

Thus the sequence is monotone and bounded above, so it is convergent. We find the limit as we did in the scratch work, which shows that $(a_{n}) \to 2$ .

☐

2.4.5

(Calculating Square Roots)

Let $x_{1} = 2$ and define:

x_{n + 1} = \frac{1}{2} (x_{n} + \frac{2}{x_{n}})

a. Show that $x_{n}^{2}$ is always greater than or equal to $2$ , and then use this to prove that $x_{n} - x_{n + 1} \geq 0$ (and thus the sequence is decreasing). Conclude that $lim x_{n} = \sqrt{2}$ .
b. Modify the sequence $(x_{n})$ so that it converges to $\sqrt{c}$ .

Proof

a. Let's do an induction. Clearly $x_{1} \geq 2$ . Doing the inductive step:

\begin{aligned} ⟺ & x_{n + 1}^{2} \geq 2 \\ ⟺ & {(\frac{1}{2} (x_{n} + \frac{2}{x_{n}}))}^{2} \geq 2 \\ ⟺ & \frac{1}{4} (x_{n}^{2} + \frac{4}{x_{n}^{2}} + 4) \geq 2 \\ ⟺ & x_{n}^{2} + \frac{4}{x_{n}^{2}} + 4 \geq 8 \\ ⟺ & \underset{\geq 2}{\underset{⏟}{x_{n}^{2}}} + \underset{\geq 2}{\underset{⏟}{\frac{4}{x_{n}^{2}}}} \geq 4 \end{aligned}

Thus work from the bottom up, since $x_{n}^{2} \geq 2$ gives the two findings below.

Completing the inductive hypothesis. Thus we've shown $x_{n}^{2} \geq 2$ for all $n$ .

Note

You can also show:

x_{n}^{2} - 2 = \frac{1}{4} {(x_{n} - \frac{2}{x_{n}})}^{2} \geq 0

To show $x_{n} - x_{n + 1} \geq 0$ :

\begin{aligned} x_{n} - x_{n + 1} \geq 0 & ⟺ x_{n} - \frac{1}{2} (x_{n} + \frac{2}{x_{n}}) \geq 0 \\ ⟺ \frac{1}{2} x_{n} - \frac{1}{x_{n}} \geq 0 \\ ⟺ \frac{1}{2} x_{n} \geq \frac{1}{x_{n}} \\ ⟺ x_{n}^{2} \geq 2 \end{aligned}

Which is true since $x_{n}^{2} \geq 0$ (via our finding above).

As a result then $(x_{n})$ is decreasing. Since we showed it's bounded below as well, then via the Monotone Convergence Theorem then $(x_{n})$ converges. As a result we can show that it converges to $\sqrt{2}$ :

\begin{aligned} lim x_{n + 1} & = lim x_{n} \\ \frac{1}{2} (L + \frac{2}{L}) & = L \\ \frac{1}{2} L + \frac{1}{L} & = L \\ \frac{1}{L} & = \frac{1}{2} L \\ 1 & = \frac{1}{2} L^{2} \\ 2 & = L^{2} \\ \sqrt{2} & = L \end{aligned}

b. We can try to work backwards similar to the last set of steps. Alternatively change one of the 2's to a $c$ and this should work. Let's try:

\frac{1}{2} (x_{n} + \frac{c}{x_{n}}) = x_{n + 1}

It should still converge by the same argument before (replace $2$ with $c$ ). To show the limit is what we want:

\begin{aligned} lim x_{n + 1} & = lim x_{n} \\ \frac{1}{2} (L + \frac{c}{L}) & = L \\ L + \frac{c}{L} & = 2 L \\ \frac{c}{L} & = L \\ c & = L^{2} \\ \sqrt{c} & = L \end{aligned}

☐

2.4.6

Arithmetic-Geometric Mean

a. Explain why $\sqrt{x y} \leq \frac{x + y}{2}$ for all $x, y > 0$ (the geometric mean is always less than the arithmetic mean).
b. Now let $0 \leq x_{1} \leq y_{1}$ and define:

x_{n + 1} = \sqrt{x_{n} y_{n}}, y_{n + 1} = \frac{x_{n} + y_{n}}{2}

Show that $lim_{n \to \infty} x_{n}$ and $lim_{n \to \infty} y_{n}$ exist and are equal.

Proof
a. Notice:

\begin{aligned} \sqrt{x y} & \circ \frac{x + y}{2} \\ x y & \circ {(\frac{x + y}{2})}^{2} \\ x y & \circ \frac{1}{4} (x^{2} + y^{2} + 2 x y) \\ 4 x y & \circ x^{2} + y^{2} + 2 x y \\ 2 x y & \circ x^{2} + y^{2} \\ 0 & \circ x^{2} + y^{2} - 2 x y \\ 0 & \circ (x - y)^{2} \\ 0 & \leq (x - y)^{2} \end{aligned}

So then work backwards to get our inequality as desired.

b. If we show that $y_{n}$ converges then we are done since we can use Squeeze Theorem with $0, y_{n}$ as our sequences to show that $x_{n}$ converges.

We should show that $y_{n}$ is bounded below by $0$ , which means we need to show $x_{n} + y_{n} \geq 0$ . By induction, notice $0 \leq x_{1} \leq y_{1}$ for our base case. Now for the inductive step suppose $0 \leq y_{n}$ . For the $n + 1$ case:

\begin{aligned} ⟺ & y_{n + 1} \geq 0 \\ ⟺ & \frac{x_{n} + y_{n}}{2} \geq 0 \\ ⟺ & x_{n} + y_{n} \geq 0 \\ ⟺ & x_{n} \geq y_{n} \end{aligned}

But via (a) then this is true because notice that, inductively for any $n$ , the AM has to be $\leq$ GM, so then:

\sqrt{x_{n} y_{n}} \leq \frac{x_{n} + y_{n}}{2} \Rightarrow x_{n + 1} \leq y_{n + 1}

So then we always have it that $y_{n + 1} \geq 0$ , completing the induction.

Now we'll show that $y_{n}$ is decreasing, and thus we could use MCT. Notice that for any $n$ :

\begin{aligned} y_{n + 1} \leq y_{n} & ⟺ \frac{x_{n} + y_{n}}{2} \leq y_{n} \\ ⟺ \frac{x_{n}}{2} \leq \frac{y_{n}}{2} \\ ⟺ x_{n} \leq y_{n} \end{aligned}

Which is true as we've shown before. The $x_{1} \leq y_{1}$ thus let's us start the induction off and the step above let's us complete the inductive step.

Now we know that $y_{n}$ converges, then $x_{n}$ converges by the Squeeze Theorem. As a result, their limits also have to equal (by the same Theorem). Therefore, their limits must also be 0.

☐

2.4.7

Limit Superior

Let $(a_{n})$ be a bounded sequence.
a. Prove that the sequence defined by $y_{n} = sup {a_{k} : k \geq n}$ converges.
b. The limit superior of $(a_{n})$ , or $lim sup a_{n}$ , is defined by:

lim sup a_{n} = lim y_{n}

where $y_{n}$ is the sequence from (a). Provide a reasonable definition for $lim inf a_{n}$ and briefly explain why it always exists for any bounded sequence.
c. Prove that $lim inf a_{n} \leq lim sup a_{n}$ for every bounded sequence, and give an example of a sequence for where the inequality is strict.
d. Show $lim inf a_{n} = lim sup a_{n}$ iff $lim a_{n}$ . In this case, all three share the same value.

Proof
a. First let's dissect some notation for $y_{n}$ . Here for each $i$ we say that $y_{i} = sup {a_{k} : k \geq n}$ if:

$y_{i}$ is an upper bound for all terms $a_{k} : k \geq n$ .
$y_{i}$ is the least of these upper bounds.

Notice that $(a_{n})$ being bounded implies that $sup {a_{k} : k \geq n}$ always exists.

We'll show that since $y_{n}$ is decreasing and bounded below that it converges by the MCT. For decreasing notice that if we assume the contrary that $y_{n + 1} > y_{n}$ then that means that there's some $a_{k}$ where $k \geq n + 1$ and some $a_{k^{'}}^{'}$ where $k^{'} \geq n$ . But then $k > k^{'}$ by construction, and implies that $a_{k} > a_{k^{'}}$ by those elements being out suprema. Then that implies that $a_{k^{'}}$ cannot be an upper bound, which is a contradiction. Thus $y_{n + 1} \leq y_{n}$ .

For bounded, notice that it must be bounded since it is a subsequence of $a_{n}$ which itself is bounded.

Definition

$lim inf a_{n} = lim sup {a_{k} : k \geq n}$

It must also exist similar to (a) since $z_{n} = inf {a_{k} : k \geq n}$ is increasing (take the same argument above but use $inf$ instead) and bounded above (since $(a_{n})$ is bounded) and thus must converge by MCT.

Notice that $lim sup a_{n}, lim inf a_{n}$ always exists as previously described. Using the Limits and Order (Order Limit Theorem) then if we show $inf a_{n} \leq sup a_{n}$ always then that gives the result. But we showed this in Suprema + Density Practice#1.3.11 (c) since these are sequences of real numbers (and thus $\exists c \in R$ in between these two sequences).

An example sequence where the inequality is strict is $(a_{n}) = (- 1)^{n}$ where the $lim sup a_{n} = 1$ but $lim inf a_{n} = - 1$ which don't equal.

d.
$lim inf a_{n} = lim sup a_{n}$ $⟺$ , since $a_{n}$ is in between these two other sequences, so by the Squeeze Theorem then $a_{n}$ converges and must converge to the same limit. This argument is iff.
☐

2.4.8

Question

For each series, find an explicit formula for the sequence of partial sums and determine if the series converges.
a. $\sum_{n = 1}^{\infty} \frac{1}{2^{n}}$
b. $\sum_{n = 1}^{\infty} \frac{1}{n (n + 1)}$
c. $\sum_{n = 1}^{\infty} \log (\frac{n + 1}{n})$

Proof

\begin{aligned} s_{m} & = \sum_{n = 1}^{m} \frac{1}{2^{n}} \\ = \frac{1}{2} + \frac{1}{4} + \dots + \frac{1}{2^{m}} \\ 2 s_{m} & = 1 + \frac{1}{2} + \frac{1}{4} + \dots + \frac{1}{2^{m - 1}} \\ 2 s_{m} & = 1 + s_{m} - \frac{1}{2^{m}} \\ s_{m} & = 1 - \frac{1}{2^{m}} \end{aligned}

Thus to find if it converges take the limit:

s = lim_{m \to \infty} s_{m} = lim 1 - \frac{1}{2^{- m}} = 1 - 0 = 1

so it converges to 1.

\begin{aligned} s_{m} & = \sum_{n = 1}^{m} \frac{1}{n (n + 1)} \\ = \frac{1}{1 (2)} + \frac{1}{2 (3)} + \dots + \frac{1}{m (m + 1)} \\ = (1 - \frac{1}{2}) + (\frac{1}{2} - \frac{1}{3}) + \dots + (\frac{1}{m} - \frac{1}{m + 1}) \\ = 1 - \frac{1}{m + 1} \end{aligned}

Taking the limit:

s = lim_{m \to \infty} s_{m} = 1 - 0 = 1

\begin{aligned} s_{m} & = \sum_{n = 1}^{m} \ln (\frac{n + 1}{n}) \\ e^{s_{m}} & = \exp (\sum_{n = 1}^{m} \ln (\frac{n + 1}{n})) \\ = \prod_{n = 1}^{m} \frac{n + 1}{n} \\ = \frac{2}{1} \cdot \frac{3}{2} \cdot \dots \cdot \frac{m + 1}{m} \\ = m + 1 \\ \Rightarrow s_{m} & = \ln (m + 1) \end{aligned}

Notice that the limit diverges in this case.

☐