$$$$

9  Subsequences

Highlights of this Chapter: We define the concept of subsequence, and investigate examples where subsequences behave much simpler than the overall sequence with the example of continued fractions. We then investigate the relationship between the convergence of subsequences and the convergence of a sequence as a whole. This leads to several nice theorems:

• A continued fraction description of the golden ratio and $\sqrt{2}$
• Theorem: a sequence converges if it is a union of subsequences converging to the same limit.
• Theorem: every bounded sequence contains a convergent subsequence.

Definition 9.1 A subsequence is a subset of a sequence which is itself a sequence. As sequences are infinite ordered lists of real numbers, an equivalent definition is that a subsequence is any infinite subset of a sequence.

We often denote an abstract subsequence like $s_{n_k}$, meaning that we have kept only the $n_k$ terms of the original, and discarded the rest.

Example 9.1 (Example Subsequences) In the sequence of all $n$-gons inscribed in a circle, the collection studied by archimedes (CITE EALRIER CHAP) by doubling is the subsequence $$\begin{array}{rl}{P}_{3\cdot 2^k}& =(P_{3\cdot 2^1},P_{3\cdot 2^2},P_{3\cdot 2^3},P_{3\cdot 2^4},\dots )\\ & =(P_6,P_{12},P_{24},P_{48},\dots )\end{array}$$

Archimedes began his estimation of $\pi$ using a simple idea: create a sequence of nested intervals (upper and lower bounds) from inscribing and circumscribing $n$-gons. But then he realized calculations would be much simpler if he focused only on a subsequence, namely that generated by side-doubling. We too will often run into situations like Archimedes, where the overall behavior of a sequence is difficult to understand, but we can pull out subsequences that are much easier to work with.

9.1 Continued Fractions

In the previous section, we uncovered a beautiful formula for the golden ratio as the limit of an infinite process of square roots. However, practically speaking (if you were interested in calculating the value of the golden ratio, as the ancient mathematicians were) this series is useless. The golden ratio itself involves a square root, so if you are seeking a method of approximations its fair to assume that you cannot evaluate the square root function exactly. But what does our sequence of approximations look like? To calculate the $n^{th}$ term, you need to take $n$ square roots! The very terms of our convergent sequence are actually much much more algebraically complicated than their limiting value.

To be practical, we would like a sequence that (1) contains easy to compute terms, and (2) converges to the number we seek to understand. By ?thm-rational-sequence, we know for any real number there exists a sequence of rationals that converges to it, and so it’s natural to seek a method of producing such a thing.

One method is the continued fraction, which is best illustrated by example. We know that the golden ratio $L$ satisfies the equation $L^2=L+1$, and dividing by $L$ this gives us an equation satisfied by $L$ and $1/L$:

$$L=1+\frac{1}{L}$$

Just like we did above, we can use this self-referential equation to produce a series, by plugging it into itself over and over. After one such substitution we get

$$L=1+\frac{1}{1+\frac{1}{L}}$$

And then after another such we get

$$L=1+\frac{1}{1+\frac{1}{1+\frac{1}{L}}}$$

Continuing this way over and over, we push the $L$ “off to infinity” on the right hand side, and are left with an infinite expression for $L$, as a limit of a sequence of fractions.

$$L=1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\cdots }}}}}}}}$$

Of course, this ‘infinite manipulation’ is not itself rigorous, but we can interpret this as a recursive sequence exactly as above. Setting $s_1=1$, we have the rule $s_{n+1}=1+\frac{1}{s_n}$, and we wish to understand $lim{s}_n$.

Example 9.2 (Continued Fraction of the Golden Ratio) The continued fration $$1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\cdots }}}}}}}}$$ defined by the recursive sequence $s_1=1$, $s_{n+1}=1+\frac{1}{s_n}$ limits to the golden ratio.

A continued fraction is a recursive sequence, so we can compute everything with the starting value and a single simple rule. To get a feel for the sequence at hand, let’s compute the first few terms:

$$s_1=1,s_2=2,s_3=\frac{3}{2},s_4=\frac{5}{3},s_5=\frac{8}{5},s_6=\frac{13}{8},s_6=\frac{21}{13},\dots$$

What’s one thing we notice about this sequence from its first few terms? Well - it looks like the fractions are all ratios of Fibonacci numbers! This won’t actually be relevant but it’s a good practice of induction with the sequence definition, so we might as well confirm it:

Example 9.3 (Fibonacci Numbers and the Golden Ratio) Recall that the Fibonacci numbers are defined by the recurrence relation $F_1=F_1=2$ and $F_{n+2}=F_{n+1}+F_n$. Show that the $n^{th}$ convergent $s_n$ of the continued fraction for the golden ratio is the ratio of the Fibonacci numbers $F_{n+1}/F_n$.

Proof. This is true for the first convergent which is $1$, and $F_2/F_1=1/1=1$. Assume the $n^{th}$ convergent is $s_n=F_{n+1}/F_n$, and consider the $n+1^{st}$: this is $$s_{n+1}=1+\frac{1}{s_n}=1+\frac{1}{\frac{F_{n+1}}{F_n}}$$ $$=1+\frac{F_n}{F_{n+1}}=\frac{F_{n+1}+F_n}{F_{n+1}}=\frac{F_{n+2}}{F_{n+1}}$$

The more important thing we notice is that looking at the magnitude of the terms, it is neither increasing or decreasing, but it appears the sequence is zig-zagging up and down. Its straightforward to prove this is actually the case:

Example 9.4 If $n$ is odd, then $s_n<s_{n+1}$. If $n$ is even, $s_n>s_{n+1}$.

Proof. Again, we proceed by induction: we prove only the first case, and leave the second as an exercise. Note first $s_1=1$, $s_2=2$ and $s_3=\frac{3}{2}$ so $s_1<s_2$ and $s_2>s_3$: the base case of each is true.

Now, assume that $n$ is odd, and $s_n<s_{n+1}$. Computing from here $$s_n<s_{n+1}⟹\frac{1}{s_n}>\frac{1}{s_{n+1}}⟹1+\frac{1}{s_n}>1+\frac{1}{s_{n+1}}$$

The last line of this computation is the definition of $s_{n+1}>s_{n+2}$,so we see the next one is decreasing as claimed. And applying the recurrence once more:

$$s_{n+1}>s_{n+2}⟹\frac{1}{s_{n+1}}<\frac{1}{s_{n+2}}⟹1+\frac{1}{s_{n+1}}<1+\frac{1}{s_{n+2}}$$ Where now the last line of the calculation is the definition of $s_{n+2}<s_{n+3}$, fininshing our induction step!

While the overall sequence isn’t monotone, it seems to be built of two different monotone sequences, interleaved with one another! In particular the odd subsequence $s_1,s_3,s_5,\dots$ is monotone increasing, and the even subsequence $s_2,s_4,s_6,\dots$ is monotone decreasing.

To study these subsequences separately, we first need to find a recurrence relation that gives us $s_{n+2}$ in terms of $s_n$: applying this to either $s_1$ or $s_2$ will then produce the entire even or odd subsequence.

$$s_{n+2}=1+\frac{1}{s_{n+1}}=1+\frac{1}{1+\frac{1}{s_n}}$$

Example 9.5 The subsequence $s_1,s_3,s_5,s_7,\dots$ is monotone increasing.

Proof. We prove this by induction. Starting from $s_1=1$, we compute $$s_3=1+\frac{1}{1+\frac{1}{1}}=1+\frac{1}{2}=\frac{3}{2}$$ So $s_1<s_3$, completing the base case. Next, assume for induction that $s_{n+2}>s_n$. We wish to show that $s_{n+4}>s_{n+2}$. Calculating from our assumption:

$$\begin{array}{rl}{s}_{n+2}>s_n& ⟹\frac{1}{s_{n+2}}<\frac{1}{s_n}\\ & ⟹1+\frac{1}{s_{n+2}}<1+\frac{1}{s_n}\\ & ⟹\frac{1}{1+\frac{1}{s_{n+2}}}>\frac{1}{1+\frac{1}{s_n}}\\ & ⟹1+\frac{1}{1+\frac{1}{s_{n+2}}}>1+\frac{1}{1+\frac{1}{s_n}}\\ & ⟹s_{n+4}>s_{n+2}\end{array}$$

This completes the induction step, so the subsequence of odd terms is monotone increasing as claimed!

A nearly identical argument applies to the even subsequence:

Exercise 9.1 The subsequence $s_2,s_4,s_6,s_8,\dots$ is monotone decreasing.

Exercise 9.2 Let $f(x)=1+\frac{1}{x}$. Show that if $x<y$ then $f(x)>f(y)$; that is, $f$ reverses the ordering of numbers. Use this to give a more streamlined proof that the even and odd subsequences are both monotone, but the overall sequence zigzags.

Now that we know each sequene is monotone, we are in a position similar to the previous chapter where we played two sequences off one another to learn about $e$. The same trick works to show they are bounded.

Example 9.6 The odd subsequence of $s_n$ is bounded above, and the even subsequence is bounded below.

Proof. The even subsequece is monotone decreasing, but consists completely of positive terms. Thus, its bounded below by zero. Now we turn our attention to the odd subsequence: if $n$ is odd, we know that $s_n$ is bounded above by $s_{n+1}$, but $s_{n+1}$ is a member of the monotone decreasing even subsequence, so $s_{n+1}<s_2=2$. Thus, for all odd $n$, $s_n$ is bounded above by 2.

Now we know by monotone convergence that both the even and odd subsequences converge! Next, we show they converge to the same value:

Example 9.7 Both the even and odd subsequences converge to the same value.

Proof. Let $e_n=s_{2n}$ be the even subsequence and $o_n=s_{2n-1}$ the odd subsequence, and write $lim{e}_n=E$ and $lim{o}_n=\mathrm{\Theta }$. We wish to show $E=\mathrm{\Theta }$.

Using the recurrence relation we see $$o_{n+1}=1+\frac{1}{e_n}{e}_n=1+\frac{1}{o_n}$$ and so, using the limit laws and the convergence of $e_n,o_n$ $$\mathrm{\Theta }=1+\frac{1}{E}E=1+\frac{1}{\mathrm{\Theta }}$$ Therefore we see $\mathrm{\Theta }-E=\frac{1}{E}-\frac{1}{\mathrm{\Theta }}$, which after getting a common denominator implies $$\mathrm{\Theta }-E=\frac{\mathrm{\Theta }-E}{\mathrm{\Theta }E}$$ So whatever number $\mathrm{\Theta }-E$ is, it has the property that it is unchanged when divided by the number $\mathrm{\Theta }E$. But the only number unchanged by multiplication and division is zero! Thus $$\mathrm{\Theta }-E=0$$

Now we know that not only the even and odd subsequences converge but that they converge to the same limit! Its not too much more work to show that the entire sequence converges.

Example 9.8 The sequence $s_n$ converges.

Proof. Call the common limit of the even and odd subsequences $L$. Let $\epsilon >0$ Since $s_{2n-1}\to L$ we know there is an $N_1$ with $n>N_1$ implying $|s_{2n-1}-L|<\epsilon$. Similarly since $s_{2n}\to L$ we can find an $N_2$ where $n>N_2$ implies $|s_{2n}-L|<\epsilon$.

Set $N=max\{N_1,N_2\}$. Then if $n>N$ we see both the even and odd subsequences are within $\epsilon$ of $L$ by construction, and thus all terms of the sequence are within $\epsilon$ of $L$. But this is the definition of convergence! Thus $s_n$ is convergent and $lim{s}_n=L$.

Finally! Starting with a zigzag sequence where monotone convergene did not apply, we broke it into two subsequences, each of which were monotone, and each of which we could prove converge. Then we showed these subsequences have the same limit and hence the overall sequence converges. We made it! Now its quick work to confirm the limit is what we expected from our construction: the golden ratio.

Example 9.9 The sequence $s_n$ converges to the golden ratio.

Proof. Since throwing away the first term of the sequence does not change the limit, we see $lim{s}_{n+1}=lim{s}_n=L$. Using the recurrence relation and the limit laws, this implies $$lim{s}_{n+1}=lim1+\frac{1}{s_n}=1+\frac{1}{L}$$

THus, the limit $L$ satisfies the equation $L=1+1/L$ or $L^2=L+1$. This has two solutions $$\frac{1\pm \sqrt{5}}{2}$$ Only one of which is positive. Thus this must be the limit $$1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\cdots }}}}}}}}=\frac{1+\sqrt{5}}{2}$$s

We can apply this same process to discover another sequence of rational approximations to $\sqrt{2}$, by algebraic means (in contrast wtih the geometric approach of the babylonians). To start, we need to find a recursive formula that is satisfied by $\sqrt{2}$, and involves a reciprocal: something like

$$\sqrt{2}=\text{Rational stuff}+\frac{1}{\text{Rational stuff and }\sqrt{2}}$$

We can get such a formula through some trickery: first, using the difference of squares $a^2-b^2=(a+b)(a-b)$ we see that $1=2-1=(\sqrt{2}+1)(\sqrt{2}-1)$, which can be re-written

$$\sqrt{2}-1=\frac{1}{1+\sqrt{2}}$$ Now, substitute this into the obvious $\sqrt{2}=1+\sqrt{2}-1$ to get

$$\sqrt{2}=1+\frac{1}{1+\sqrt{2}}$$

This is a self-referential equation, meaning $\sqrt{2}$ appears on both sides.

Example 9.10 (Continued Fraction of $\sqrt{2}$) The continued fraction $$1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{2+\cdots }}}}}$$ converges to the square root of $2$.

9.2 Subsequences and Convergence

Hopefully this exploration into continued fractions has shown the usefulness of looking for easy-to-work-with subsequences, when theorems such as monotone convergence don’t automatically apply. It is then our goal to try and piece this information back together: if we know the limits of various subsequences, what can we say about the entire sequence?

A direct generalization of the even/odd case from our example above shows that if $s_n$ can separated into two subsequences which we can (separately) prove have the same limit, then the entire sequence converges to that

Proposition 9.1 (Union of Two Subsequences) If $s_n$ is the union of two subsequences $s_{n_k}$ and $s_{n_{\ell }}$ which both converge to the same limit, then $s_n$ converges to that limit.

Proof. Let $L$ be the common limit of $s_{n_k}$ and $s_{n_{\ell }}$, and fix and $\epsilon >0$. Then there is an $N_1$ such that for all $k>N_1$ we are assured that $|s_{n_k}-L|<\epsilon$ and there is an $N_2$ such that for all $\ell >N_2$ we know $|s_{n_{\ell }}-L|<\epsilon$. Choosing any particular $k\ge N_1$ and $\ell \ge N_2$ we set $N=max{n}_k,n_{\ell }$.

Now choose arbitrary $n>N$. The term $s_n$ is a a member of one of our two subsequences, but by design if $n=n_k$ then $k>N_1$ and if $n=n_{\ell }$ then $\ell >N_2$, so we know $|s_n-L|<\epsilon$, and our sequence converges as claimed.

Theorem 9.1 Let $s_n$ be a sequence, and assume that $s_n$ is the union of $N$ subsequences, all of which converge to the same limit $L$. Then $s_n$ is convergent, with limit $L$.

Proof (Sketch). One can prove this directly, but choosing useful notation is tedious. The idea is as follows: for each of the $N$ sequences, let $M_1,M_2,\dots M_N$ be the threshold beyond which the subsequence is within $\epsilon$ of $L$ for some fixed $\epsilon >0$. Then set $M=max\{M_1,\dots ,M_N\}$ and note that for all $n>M$ each of the subsequences is within $\epsilon$ of $L$. Because the entire sequence is just the union of these $N$ subsequences, this means that every term of the sequence is within $\epsilon$ of $L$. But this is precisely the definition of $s_n\to L$. So we are done.

However, a simple example shows its not enough to simply say a sequence is a union of convergent subsequences: we do have to know they all have the same limit!

Example 9.11 The sequence $s_n=(-1{)}^n$ diverges, but its even and odd subsequences form constant (thus convergent) subsequences: $$\begin{array}{rl}{s}_{2n}& =(-1{)}^{2n}=1,1,1,\dots \\ s_{2n+1}& =(-1{)}^{2n-1}=-1,-1,-1,\dots \end{array}$$

Or, more generally

Exercise 9.3 Prove that if a sequence $s_n$ has two subsequences which converge to different values, then the overall sequence diverges. Rephrasing this positively gives a useful criterion: If $s_n$ is a convergent sequence, then all of its subsequences converge, and have the same limit.

Remark 9.1. This can be turned into a useful technique to prove two sequences $a_n,b_n$ have the same limit: interleave their terms $a_1,b_1,a_2,b_2,a_3,b_3,\cdots$ and try to prove the resulting sequence converges. If it does, then we know all subsequences have the same limit, and so both $a_n$ and $b_n$ converge to $L$.

9.3 Bolzano-Weierstrass

What about sequences that don’t converge? The theorem above says that it cannot be true that all their subsequences converge, but Example 9.11 does show that a divergent sequence can still contain convergent subsequences. A natural question then is - do they always? Alas, a simple counterexample shows us that is too much to ask:

Example 9.12 The sequence $s_n=n^2$ diverges, and all subsequences of it diverge.

But the problem here is not serious, its simply that the original sequence is unbounded and cannot possibly contain anything that converges. The perhaps surprising fact that this is the only constraint preventing the existence of a convergent subsequence is known as the Bolzano Weierstrass theorem.

Theorem 9.2 (Bolzano-Weierstrass) Every bounded sequence has a convergent subsequence

There are many ways to prove this, but a particularly elegant one uses (of course!) the monotone convergence theorem.

At first this sounds suspicious: we must confront head on the issue we ran into above, that not every sequence is monotone! However, the weaker property we actually need is true: while not every sequence is monotone, every sequence contains a monotone subsequence. There is a very clever argument for this, which needs one new definition.

Definition 9.2 (Peak of a Sequence) Let $s_n$ be a sequence and $N\in \mathbb{N}$. Then $s_N$ is a peak if it is larger than all following terms of the sequence: $$s_N\ge s_m\mathrm{\forall }m>N$$

Theorem 9.3 (Monotone Subsequences) Every sequence contains a monotone subsequence

Proof. Let $s_n$ be an arbitrary sequence. Then there are two options: either $s_n$ contains infinitely many peaks or it does not.

If $s_n$ contains infinitely many peaks, we can build the subsequence of all peaks. This is monotone decreasing: if $p_1$ is the first peak, then its greater than or equal to all subsequent terms $s_n$, and so its greater than or equal to the second peak $p_2$. (But, nothing here is special about $1$ and $2$, this holds for the $n^{th}$ and $n+1^{st}$ peak without change).

Otherwise, if $s_n$ contains only finitely many peaks, we will construct a monotone increasing subsequence as follows. Since there are finitely many peaks there must be a last peak, say this occurs at position $N$. Then $s_{N+1}$ is not a peak, and we will take this as the first term of our new sequence (let’s call it $q_1$). Because its not a peak, by definition there is some term farther down the sequence which is larger than $s_{N+1}$ - say this happens at index $N_2$ and call it $q_2$. But $q_2$ is also not a peak (as there were only finitely many, and we are past all of them), so there’s a term even farther down - say at index $N_3$ which is larger: call it $q_3$. Now we have $q_1<q_2<q_3$, and we can continue this procedure inductively to build a monotone increasing subsequence for all $n$.

Now, given that every sequence has a monotone subsequence, we know that every bounded sequence has a monotone and bounded subsequence. Such things converge by MCT, so we know every sequence has a convergent subsequence! This is the Bolzano Weierstrass Theorem.

We will use this often in whats to come to produce examples of convergent subsequences where it might otherwise be difficult to do so. Here’s a first example of such an argument

Proposition 9.2 (Analyzing All Convergent Subsequences) If $s_n$ is a bounded sequence such that every convergent subsequence converges to the same value, then $s_n$ converges.

Proof. Assume that every convergent (proper) subsequence of $s_n$ converges to $L$, but that $s_n$ itself does not. Then fixing some $\epsilon >0$ for each $n=1,2,3,\dots$ we can find an $k$ such that $|s_{n_k}-L|>\epsilon$. This is an infinite sequence of terms all of which are farther than $\epsilon$ from $L$, and is bounded as $s_n$ itself was bounded. Thus, by the Bolzano Weierstrass theorem there is a subsequence of this that converges. Its limit cannot be $L$ because all terms in the sequence are more than $\epsilon$ away from $L$, so we’ve found a subsequence of the original sequence that converges to a different value, contradicting the original assumption.

In addition to applications like the above, in time will come to appreciate it as one of the most elegant tools available to us. There will come many times (soon, when dealing with functions) where we can easily produce a sequence of points satisfying some property, but to make progress we need a convergent sequence of such points. The BW theorem assures us that we don’t have to worry - we can always make one by just throwing out some terms, so long as the sequence we have is bounded.

9.4 Limsup and Liminf

When a sequence doesn’t converge, it can have various subsequences that converge to different limits. One way to reign in the complexity of such things is via the concepts of limit supremum and limit infimum.

Definition 9.3 (Limsup and Liminf) Let $s_n$ be a bounded sequence, and for each $N\in \mathbb{N}$ define $u_N=\underset{n\ge N}{sup}\{s_n\}$. Then we define the limit superior of $s_n$ as $$lim sup{s}_n:=lim{u}_N=\underset{N\to \mathrm{\infty }}{lim}\underset{n\ge N}{sup}\{s_n\}$$ Similarly, with ${\ell }_N=\underset{n\ge N}{inf}\{s_n\}$ we define the limit inferior of $s_n$ to be $$lim inf{s}_n:=lim{\ell }_N=\underset{N\to \mathrm{\infty }}{lim}\underset{n\ge N}{inf}\{s_n\}$$

We will have occasional use for this definition during the course, mostly because of the following: that the limsup and liminf exist for all (bounded) sequences, not just convergent ones.

Proposition 9.3 (Existence of Limsup, Liminf) Let $s_n$ be a bounded sequence. Prove that $lim sup{s}_n$ and $lim inf{s}_n$ both exist

Proof. We verify for the limsup case, and leave the analgoous liminf as an exercise. For each $N$ let $u_N=\underset{n\ge N}{sup}\{s_n\}$ and notice that $u_N$ is a monotone decreasing sequence as we are taking the supremum over smaller and smaller sets (Exercise 3.4). Its easy to construct a lower bound for $u_N$: since $s_n$ is bounded we may take any lower bound $L$ and note for any $N$ this is a lower bound for the tail $\{s_n\mid n>N\}$. As the supremum is an upper bound and all lower bounds are $\le$ all upper bounds we see $L\le \underset{n>N}{sup}\{s_n\}=u_N$. Thus $u_N$ is a monotone decreasing sequence that is bounded below, which converges by the Monotone Convergence Theorem.

One use of these quantities is to bound the possible values of subsequential limits:

Exercise 9.4 (Bounding Subsequential Limits) Let $s_n$ be any bounded sequence and $s_{n_k}$ a convergent subsequence with limit $L$. Then $$lim inf{s}_n\le L\le lim sup{s}_n$$

Proposition 9.4 A sequence $s_n$ converges if and only if $$lim sup{s}_n=lim inf{s}_n$$

Proof. For any $N$ we have ${\ell }_N=\underset{n\ge N}{inf}{s}_n\le s_N\le \underset{n\ge N}{sup}{s}_n=u_N$. But $lim{\ell }_N=lim inf{s}_n=lim sup{s}_n=lim{u}_N$ by assumption, so the squeeze theorem (Theorem 7.1) implies $s_N$ also converges, and has the same limit.

It is often useful to broaden our use of $lim sup$ and $lim inf$ to the extended reals $\mathbb{R}\cup \{\pm \mathrm{\infty }\}$. Here its true that every sequence has a limsup and liminf: either the sequence is bounded and they exist as proven above, or the sequence is unbounded with $lim sup,lim inf=\pm \mathrm{\infty }$. This slight generalization makes certain theorems easier to state, as one can use $lim sup$ and $lim inf$ without first checking they exist.

Exercise 9.5 (Subsequences & Limsup, Liminf) Let $s_n$ be a bounded sequence. Then there exists a subsequence which converges to the limsup and a subsequence which converges to the liminf.

9.5 Problems

Exercise 9.6 For any fixed $n$, prove that the following continued fraction exists, and find its vallue. $$\frac{1}{n+\frac{1}{n+\frac{1}{n+\frac{1}{n+\frac{1}{n+\frac{1}{n+\frac{1}{n+\frac{1}{n+\cdots }}}}}}}}$$

Exercise 9.7 (Continued Fractions for Roots) Let $p$ be any prime number, find the continued fraction for $\sqrt{p}$.

Knowing such sequences is extremely useful for computation, in the age before computers: if $n$ is a composite number we can find $\sqrt{n}$ by multiplying together the square roots of its prime factorization

Exercise 9.8 Find a rational approximation to $\sqrt{6}$ by calculating the first three terms in the continued fraction expansions for $\sqrt{2}$ and $\sqrt{3}$.

We could also find a continued fraction directly for cases like this, with a little more care:

Exercise 9.9 Find the continued fraction expansion for $\sqrt{pq}$ if $p$ and $q$ are primes. What happens to your procedure when $p=q$?

9.5.1 Limsup and Liminf

Exercise 9.10 Let $a_n,b_n$ be bounded sequences. Prove that $$lim sup(a_n+b_n)\le lim sup{a}_n+lim sup{b}_n$$ $$lim inf{a}_n+lim inf{b}_n\le lim inf(a_n+b_n)$$

Provide counterexamples to show that equality does not always hold.

Exercise 9.11 Let $a_n$ be convergent and $b_n$ be an arbitrary bounded sequence. Show that

$$lim sup(a_n+b_n)=lim{a}_n+lim sup{b}_n$$ $$lim inf(a_n+b_n)=lim{a}_n+lim inf{b}_n$$

Exercise 9.12 Let $a_n$ be convergent and $b_n$ be an arbitrary bounded sequence. Show that

$$lim sup(a_n{b}_n)=(lim{a}_n)(lim sup{b}_n)$$ $$lim inf(a_n{b}_n)=(lim{a}_n)(lim inf{b}_n)$$

9.5.2 $★$ An Alternative Proof of Bolzano-Weierstrass

An alternative argument for the BW theorem proceeds via the nested interval property. Here’s an outline of how this works

• If $s_n$ is bounded then there is some $a,b$ with $a\le s_n\le 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 \mathbb{R}$ 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 9.13 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?

Exercise 9.14 (Simultaneous Bolzano Weierstrass) Given two bounded sequences $x_n,y_n$ there is a subsequence $n_k$ of indices such that both $x_{n_k}$ and $y_{n_k}$ converge. Prove this, and then use induction to prove that for any finite number of bounded sequences, one can choose a subsequence of indices so they all converge.