$$ \newcommand{\RR}{\mathbb{R}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\CC}{\mathbb{C}} \newcommand{\NN}{\mathbb{N}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\EE}{\mathbb{E}} \newcommand{\HH}{\mathbb{H}} \newcommand{\FF}{\mathbb{F}} \newcommand{\SO}{\operatorname{SO}} \newcommand{\dist}{\operatorname{dist}} \newcommand{\length}{\operatorname{length}} \newcommand{\uppersum}[1]{{\textstyle\sum^+_{#1}}} \newcommand{\lowersum}[1]{{\textstyle\sum^-_{#1}}} \newcommand{\upperint}[1]{{\textstyle\smallint^+_{#1}}} \newcommand{\lowerint}[1]{{\textstyle\smallint^-_{#1}}} \newcommand{\rsum}[1]{{\textstyle\sum_{#1}}} \newcommand{\partitions}[1]{\mathcal{P}_{#1}} \newcommand{\erf}{\operatorname{erf}} \newcommand{\ihat}{\hat{\imath}} \newcommand{\jhat}{\hat{\jmath}} \newcommand{\khat}{\hat{k}} \newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}} \newcommand{\smat}[1]{\left(\begin{smallmatrix}#1\end{smallmatrix}\right)} $$

Assignment 6

In the textbook after studying the continued fraction 1+$ which converges to the golden ratio, a similar method is proposed to find a continued fraction converging to $\sqrt{2}$. Read that example for the following exercise.

Exercise 1

Let $p$ be any prime number, find a recursive sequence defining a continued fraction which, if it converges has limit $\sqrt{p}$. (You do not need to prove the sequence actually converges here. But assuming it does have a limit, you should prove that limit is $\sqrt{p}$.)
Find a rational approximation to $\sqrt{6}$ by calculating the 5th terms in the continued fraction expansions for $\sqrt{2}$ and $\sqrt{3}$. (Using a calculator) how close is your rational approximation to the true value?

Solution. Starting from a prime number $p$, we define the recursive sequence $s_{n+1} = 1 + \frac{p-1}{1+s_n}$ starting from $s_0=1$. Assuming the sequence converges, its limit is positive as each term is $1$ plus a positive number. By the limit laws, $1+s_n$ also converges, and to a positive number; so $1/(1+s_n)$ converges and as $p-1$ is constant $\frac{p-1}{1+s_n}$ converges, and finally $1 + \frac{p-1}{1+s_n}$ converges. Thus, by limit laws, and the fact that $\lim s_n=\lim s_{n+1}$, \[ \lim s_{n+1} = \lim \left( 1 + \frac{p-1}{1+s_n} \right) = 1 + \frac{\lim (p-1)}{\lim (1+s_n)}. \]

Let the limit of the sequence be $L$, so $\lim s_n = \lim s_{n+1} = L$. Thus, we have \[ L = 1 + \frac{p-1}{1+L},\] so \[ L + L^2 = 1 + L + p - 1. \] So, $L + L^2 = L + p$, so $L^2 = p$, so $L = \pm\sqrt{p}$. But our sequence is all positive: $s_0=1$ and since $p-1>0$, each term is the 1 plus some positive number. Thus the limit is nonnegative, so $L=\sqrt{p}$ is the limit.

Now we use this for actual examples, to get approximations of $\sqrt{2}$ and $\sqrt{3}$. Let $p = 2$. We have \[ s_0 = 1 + \frac{2-1}{1} = 2 \] \[ s_1 = 1 + \frac{1}{1+2} = \frac{4}{3} \] \[ s_2 = 1 + \frac{1}{1+\frac{4}{3}} = \frac{10}{7} \] \[ s_3 = 1 + \frac{1}{1+\frac{10}{7}} = \frac{24}{17} \] \[ s_4 = 1 + \frac{1}{1+\frac{24}{17}} = \frac{58}{41} \] \[ s_5 = 1 + \frac{1}{1+\frac{58}{41}} = \frac{140}{99} \approx 1.4141\cdots \]

This is a pretty good approximation as $\sqrt{2}$ to four decimal places is (via calculator) equal to $1.4142\cdots$. We can do the same for $p=3$ where we have \[ s_0 = 1 + \frac{3-1}{1} = 3 \] \[ s_1 = 1 + \frac{2}{1+3} = \frac{3}{2} \] \[ s_2 = 1 + \frac{2}{1+\frac{3}{2}} = \frac{9}{5} \] \[ s_3 = 1 + \frac{2}{1+\frac{9}{5}} = \frac{12}{7} \] \[ s_4 = 1 + \frac{2}{1+\frac{12}{7}} = \frac{33}{19} \] \[ s_5 = 1 + \frac{2}{1+\frac{33}{19}} = \frac{45}{26} \approx 1.731\cdots \approx \sqrt{3} \]

This is also a good approximation, as $\sqrt{3}$ to three decimal places is (via calculator) $1.732\cdots$. Multiplying these together gives a rational approximation to $\sqrt{6}$:

\[\sqrt{6}=\sqrt{2\cdot 3}=\sqrt{2}\sqrt{3}\approx \frac{140}{99}\frac{45}{26}=\frac{350}{143}\approx 2.4475\cdots\]

This is a quite good approximation as a calculator gives $\sqrt{6}\approx 2.4494$

A nested interval proof of the Bolzano Weierstrass theorem goes like this:

If $s_n$ is bounded then there is some $a,b$ with $a\leq s_n\leq b$ for all $n$. Call this interval $I_0$, and inductively build a sequence of nested closed intervals as follows
At each stage $I_k=[a_k,b_k]$, bisect the interval with the midpoint $m_k=\frac{a_k+b_k}{2}$. This divides $I_k$ into two sub-intervals, and since $I_k$ contains infinitely many points of the sequence, one of these two halves must still contain infinitely many points. Choose this as the interval $I_{k+1}$.
Now, this sequence of nested intervals has nonempty intersection by the Nested Interval Property. So, let $L\in \RR$ be a point in the intersection.
Now, we just need to build a subsequence of $s_n$ which converges to $L$. We build it inductively as follows: let the first term be $s_1$, and then for each $k$ choose some point $s_{n_k}\in I_k$ that is distinct from all previously chosen points (we can do this because there are infinitely many points available in $I_k$ and we have only used finitely many so far in our subsequence).
This new sequence is trapped between $a_k$ and $b_k$, which both converge to $L$. Thus it converges by the squeeze theorem!

Exercise 2 In this problem, you are to check the main steps of this proof to ensure it works. Namely, given the above situation prove that

If $I_k=[a_k,b_k]$, the sequences $a_k$ and $b_k$ of endpoints converge. Hint: Monotone Convergence
$\lim a_k=\lim b_k$, so the Squeeze theorem really does apply *Hint: use that at each stage we are bisecting the intervals: can you find a formula for the sequence $b_k-a_k$, and prove this converges to zero?

Solution. By construction, the intervals $I_k$ are nested, which implies their sequences of endpoints are monotone. More precisely, if $I_k=[a_k,b_k]$, the construction of $I_{k+1}=[a_{k+1},b_{k+1}]$ leaves one endpoint alone and replaces the other with the average $m_k=\frac{a_k+b_k}{2}$: \[[a_{k+1},b_{k+1}]=[a_k,m_k]\hspace{1cm}\mathrm{or}\hspace{1cm}[a_{k+1},b_{k+1}]=[m_k,b_k].\] Since $a_k<m_k<b_k$, in both cases, $a_{k+1}\geq a_k$ and $b_{k+1}\leq b_k$.

Because the sequences $a_k,b_k$ are all inside the original closed interval $[a,b]$ they are bounded (above by $b$, and below by $a$). Thus, by monotone convergence they must converge.

So, we may let $a_k\to a$ and $b_k\to b$. We wish to show that $a=b$, so we consider the sequence $c_k=b_k-a_k$, measuring the length of the $k^{th}$ interval. We know from the construction that it gets cut in half with each step: this describes a recursive formula for $c_k$. \[c_0=b-a\hspace{1cm}c_{k+1}=\frac{1}{2}c_k\]

Since $c_k=b_k-a_k$ and $a_k,b_k$ are convergent, we know by the limit theorems that $c_k$ is convergent. So, we may write $\lim c_n=c$. But now, as the limit doesn’t depend on the truncating finitely many terms, \[c=\lim c_n = \lim c_{n+1}=\lim \frac{1}{2}c_n=\frac{1}{2}\lim c_n=\frac{1}{2}c\]

Thus, the limit $c$ satisfies the equation $c=\frac{1}{2}c$, and the only solution to this is $c=0$. And finally, by the limit theorems we see \[0=\lim c_n= \lim (b_n-a_n)=\lim b_n - \lim a_n =b-a\] So, $a=b$ as claimed.

Exercise 3 Let $a_n,b_n$ be bounded sequences. Prove that \[\limsup (a_n+b_n)\leq \limsup a_n +\limsup b_n\] and provide a counterexample to show that equality does not always hold.

Now assume that $a_n$ is actually convergent, and show \[\limsup (a_n+b_n)= \lim a_n +\limsup b_n\]

Solution (Part I). We begin our proof with a lemma about suprema: for any two sequences $x_n,y_n$ \[\sup \{x_n + y_n\} \leq \sup \{x_n\} + \sup \{y_n\}\]

By definition, since $\sup$ is an upper bound, $\sup x_n$ is an upper bound for all the $x$’s, and $\sup y_n$ is an upper bound for all the $y_n$’s. Thus, x_n +y_n$ is an upper bound for all the $x_n+y_n$. And, since a supremum is the least upper bound, this upper bound must be greater than or equal to the sup: giving the claim $\sup \{x_n + y_n\} \leq \sup \{x_n\} + \sup \{y_n\}$.

Getting back to the main problem at hand, we recall the limsup of a sequence $(x_n)$ is given by $\limsup x_n = \lim_{N \to \infty} \sup_{n \geq N} x_n.$ This lets us write out what we are trying to prove as a limit of suprema:

\[\limsup (a_n+b_n)\leq \limsup a_n +\limsup b_n\] \[ \lim_{N} \sup_{n \geq N} \{a_n + b_n\} \leq \lim_N\sup_{n\geq N}\{a_n\}+\lim_N\sup_{n\geq N}\{b_n\}\]

Now, for each fixed $N$, we apply our lemma to the truncated sequences $a_{N},a_{N+1},\ldots$ and $b_N,b_{N+1},\ldots$ to see \[\sup_{n \geq N} \{a_n + b_n\}\leq \sup_{n\geq N}\{a_n\}+\sup_{n\geq N}\{b_n\}\]

Taking the limit, we use the limit law for inequalities ($x_n\leq y_n\implies \lim x_n\leq \lim y_n$) to see

\[\lim_N \sup_{n \geq N} \{a_n + b_n\}\leq \lim_N\left(\sup_{n\geq N}\{a_n\}+\sup_{n\geq N}\{b_n\}\right)\]

And then we use the limit law for addition on the right hand side to conclude

\[\lim_N\left(\sup_{n\geq N}\{a_n\}+\sup_{n\geq N}\{b_n\}\right)=\lim_N\sup_{n\geq N}\{a_n\}+\lim_N\sup_{n\geq N}\{b_n\}\]

(Where note the use of these limit laws is justified, as we have proven the limsup always exists for bounded sequences; so we know the limits of these sequences exist before we begin). Concatenating these together gives the result

\[\limsup (a_n+b_n) = \lim_N \sup_{n \geq N} \{a_n + b_n\}\leq \lim_N\sup_{n\geq N}\{a_n\}+\lim_N\sup_{n\geq N}\{b_n\} = \limsup a_n+\limsup b_n\]

Solution (Part II). To see it really must be an inequality and not an equality, in general consider the example

In terms of $n$ we may write these as $a_n = (-1)^n$ and $b_n = (-1)^{n+1}$. Computing their limsups,

$\limsup a_n = 1$, since the subsequence at even indices is constantly $1$, so for all $N$, $\sup_{n\geq N}a_n=1$: we are taking a limit of a constant sequence.
$\limsup b_n = 1$, for the same reason.
But their sum $a_n + b_n = 0$ for all $n$, so $\limsup (a_n + b_n) = 0$.

Thus, we have \[ 0 = \limsup (a_n + b_n)\] but \[ \limsup a_n + \limsup b_n = 1 + 1 = 2.\]

So $\limsup (a_n+b_n) < \limsup a_n + \limsup b_n$, with a strict inequality.

Solution (Part III). Now suppose $a_n \to a$ for some limit $a$. Intuitively, this gets around the problem we see in the previous example, as the $a_n$ sequence is eventually settling down and can’t conspire to oscillate back and forth and “cancel” the $b_n$ sequence when summed together. But we must prove this really works.

Finish Typing Proof Here

Exercise 4 Let $a_n$ and $b_n$ be Cauchy sequences, and define the sequence $c_n$ to be the distance between them: \[c_n=|a_n-b_n|\] Prove that $c_n$ is Cauchy, directly from the definition of Cauchy Sequence. Hint: recall the reverse triangle inequality from previous homework!*

Solution. Since $a_n,b_n$ are Cauchy, we have that there exists $N_a\in \NN$ such that for all $n,m>N, |a_n-a_m|<\frac{\epsilon}{2}$ for all $\epsilon>0$ and $N_b\in \NN$ such that for all $n,m>N_b, |b_n-b_m|<\frac{\epsilon}{2}$ for all $\epsilon>0$.

Let $N = \max(N_a,N_b)$. Then we can add the inequalities such that for all $n,m>N$ and for all $\epsilon>0$, \[|a_n-a_m| + |b_n-b_m| < \epsilon\] \[|a_n-a_m| + |b_m-b_n| < \epsilon\] \[|a_n-b_n+b_m-a_m|<\epsilon\] \[|(a_n-b_n) - (a_m - b_m) <\epsilon\] And thus by the reverse triangle inequality we have $||a_n-b_n| - |a_m - b_m|| <\epsilon$. Therefore the sequence $c_n = |a_n-b_n|$ is cauchy.

Exercise 5 For each of the following, either give an example or explain why no such example exists:

A sequence that has a bounded subsequence, but does not have a convergent subsequence.
A sequence that does not contain the terms $0$ or $1$ but contains a subsequence converging to 0 and a subsequence converging to 1.
A Cauchy sequence with an unbounded subsequence
A divergent sequence with a cauchy subsequence
An unbounded sequence containing a cauchy subsequence

Solution.

This is not possible. If a sequence has a bounded subsequence, then this bounded subsequence must itself have a convergent subsequence (by Bolzano Weierstrass). And so our original sequence has a convergent subsequence.
This is possible: choose any sequence $a_n$ which converges to $0$ but never contains 0, and any sequence $b_n$ which converges to 1 without containing 1. Then build a sequence $s_n$ by making $a_n$ the even subsequence and $b_n$ the odd subsequence. For an explicit example, take \[s_n=\begin{cases} \frac{1}{n} & n\textrm{ is even}\\ 1-\frac{1}{n} & n\textrm{ is odd} \end{cases}\]
This is impossible. A cauchy sequence is convergent, and all subsequences of a convergent sequence converge to the same limit. Thus it cannot have a divergent subsequence, and all unbounded sequences diverge. (Alternatively, Cauchy sequences are bounded, and bounded sequences cannot have unbounded subsequences)
This is possible. The same example used for (2) would work here: or, even easier the sequence $0,1,0,1,0,1,0,1,\ldots$. This diverges, but its even and odd subsequences are constant: thus Cauchy.
This is possible: we can modify the example above by building a sequence like $0,1,0,2,0,3,0,4,\ldots$ where the odd subsequence is constant equal to 0 and the even subsequence is $s_{2n}=n$, which is unbounded.

Exercise 6 (Convergent Implies Cauchy) If $s_n$ is a convergent sequence, then $s_n$ is Cauchy. Hint: The triangle inequality and $|a_n-a_m|$ for a sequence converging to $L$ can tell you….what?

Solution. Choose $\epsilon>0$. Since $s_n$ is convergent, call its limit $L$. Then there exists an $N$ where for all $n>N$ we know $|s_n-L|<\epsilon/2$. Now for any $n,m>N$ consider $|s_n-s_m|$. Adding zero in a clever way and applying the triangle inequality:

\[|s_n-s_m|=|s_n-L+L-s_m|\leq |s_n-L|+|L-s_m|=|s_n-L|+|s_m-L|\]

But by assumption we know each of these final quantities is less than $\epsilon/2$ since both $n$ and $m$ are greater than $N$. That means \[|s_n-s_m|\leq|s_n-L|+|s_m-L| <\frac{\epsilon}{2}+\frac{\epsilon}{2}=\epsilon\]

This is the definition of Cauchy: for any $\epsilon$ theres an $N$ where past that, for any $n,m$ $|s_n-s_m|<\epsilon$. Thus $s_n$ is Cauchy as required.

Exercise 7 Let $s_n$ be a periodic sequence (meaning after some period $P$ we have $s_n=s_{P+n}$ for all $n$). Prove that if $s_n$ is Cauchy then it is constant. Hint: what’s the contrapositive?

Solution. The contrapositive states that if $s_n$ is not constant, it is not Cauchy. Assuming that $s_n$ is not constant means there are at least some $a,b$ where $s_a\neq s_b$. To show $s_n$ is not Cauchy, choose $\epsilon = |s_a-s_b|/2$, and select any $N$. Using the period $P>0$, we can find an $M$ such that $MP>N$ (using the Archimeddean property with $P,N$); thus $MP+a>N$ $MP+b>N$. But since $P$ is the period of our sequence \[s_{MP+a}=s_a\hspace{1cm}s_{MP+b}=s_b\]

So, $|s_{MP+a}-s_{MP+b}|=|s_a-s_b|>\epsilon$, so it is not Cauchy.

(The way to remember this result: if a sequence is perioidic and has terms that differ by more than $\epsilon$ somewhere, it has terms that differ by more than $\epsilon$ arbitrarily far out, by just adding multiples of the period).