11 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 11.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 11.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{align*}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},\ldots)\\ &=(P_6,P_{12},P_{24},P_{48},\ldots) \end{align*}\]
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.
We will begin our exploration with an extended example, that illuminates the main idea.
11.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 11.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},\ldots\]
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 11.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 11.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}\implies \frac{1}{s_n}>\frac{1}{s_{n+1}}\implies 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}\implies \frac{1}{s_{n+1}}<\frac{1}{s_{n+2}}\implies 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,\ldots\) is monotone increasing, and the even subsequence \(s_2,s_4,s_6,\ldots\) 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 11.5 The subsequence \(s_1,s_3,s_5,s_7,\ldots\) 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{align*} s_{n+2}>s_n\,&\implies\, \frac{1}{s_{n+2}}<\frac{1}{s_n}\\ &\implies 1+\frac{1}{s_{n+2}}<1+\frac{1}{s_n}\\ &\implies \frac{1}{1+\frac{1}{s_{n+2}}}>\frac{1}{1+\frac{1}{s_n}}\\ &\implies 1+\frac{1}{1+\frac{1}{s_{n+2}}}>1+\frac{1}{1+\frac{1}{s_n}}\\ &\implies s_{n+4}>s_{n+2} \end{align*}\]
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 11.1 The subsequence \(s_2,s_4,s_6,s_8,\ldots\) is monotone decreasing.
Exercise 11.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 11.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 11.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 = \Theta\). We wish to show \(E=\Theta\).
Using the recurrence relation we see \[o_{n+1}=1+\frac{1}{e_n}\hspace{1cm} e_n=1+\frac{1}{o_n}\] and so, using the limit laws and the convergence of \(e_n, o_n\) \[\Theta = 1+\frac{1}{E}\hspace{1cm} E=1+\frac{1}{\Theta}\] Therefore we see \(\Theta-E = \frac{1}{E}-\frac{1}{\Theta}\), which after getting a common denominator implies \[\Theta - E = \frac{\Theta-E}{\Theta E}\] So whatever number \(\Theta-E\) is, it has the property that it is unchanged when divided by the number \(\Theta E\). But the only number unchanged by multiplication and division is zero! Thus \[\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 11.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 11.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}=\lim 1+\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 geomeric 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}=\textrm{Rational stuff} + \frac{1}{\textrm{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 11.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\).
Exercise 11.3 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 11.4 (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 11.5 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 contined fraction directly for cases like this, with a little more care:
Exercise 11.6 Find the continued fraction expansion for \(\sqrt{pq}\) if \(p\) and \(q\) are primes. What happens to your procedure when \(p=q\)?
11.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 gaol to try and piece this information back together: if we know the limits of various subsequences, what can we say about the entire sequence?
First of all, a simple example shows its not enough to say “if the even and odd subsequences converge, then the sequence converges”.
Example 11.11 The sequence \(s_n=(-1)^n\) diverges, but its even and odd subsequences form constant (thus convergent) subsequences: \[\begin{align*} s_{2n}&=(-1)^{2n}=1,1,1,\ldots\\ s_{2n+1}&=(-1)^{2n-1}=-1,-1,-1,\ldots \end{align*}\]
Indeed, if you can find any two subsequences which limit to different values, then the sequence itself must diverge. This is a useful thing to try yourself when developing intuition.
Exercise 11.7 If a sequence \(s_n\) has two subsequences which converge to different values, then the overall sequence diverges.
The converse of this: that a sequence converges if all subsequences converge to the same limit - is trivial to prove because the entire sequence is a subsequence of itself, so we’ve actually assumed convergence! Thus, we get a nice characterization:
Theorem 11.1 (Convergence in terms of Subsequences) A sequence \(s_n\) converges if and only if all of its subsequences converge, and have the same limit.
Remark 11.1. Its just as true if we even wish to weaken the hypothesis to only include proper subsequences. In this case, we could consider the proper subsequences of even and odd terms (for example): these converge to the same limit by hypothesis, and so via the argument in Example 11.8 we see the entire sequence converges.
Dealing with the collection of all subsequences is often technically difficult to do - so while this theorem statement is pretty clean sounding, its difficult to put into practice.
This showed us how to modify our original claim, about even and odd sequences however: so long as we assume they converge to the same limit, everything works.
Proposition 11.1 If the even and odd subsequences of \(s_n\) converge to the same limit \(L\), the \(s_n\) converges to \(L\).
Proof. This is actually done already in Example 11.8, when studying the golden ratio!
Here we generalize this slightly, to any finite collection of subsequences.
Theorem 11.2 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,\ldots 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,\ldots,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.
11.3 The Bolzano Weierstrass Theorem
What about sequences that don’t converge? The theorem above says that it cannot be true that all their subsequences converge, but Example 11.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 11.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 11.3 (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 11.2 (Peak of a Sequence) Let \(s_n\) be a sequence and \(N\in\NN\). Then \(s_N\) is a peak if it is larger than all following terms of the sequence: \[s_N\geq s_m\,\,\,\forall m>N\]
Theorem 11.4 (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!
We will not have much immediate use for this theorem in this or the following chapter, but 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.
11.3.1 \(\bigstar\) 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\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 11.8 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?