Convergent Sequences
If we analyze the values of a sequence we can see that certain behaviors or patterns can occur such as the sequence becoming monotonically increasing or decreasing or the sequence staying within a certain range, i.e. being bounded between two values.
Another pattern we may notice is that the terms of the sequence get closer and closer to a certain value as the index \(n\) increases. Let’s consider the following sequence and its terms:
\[a_n = \frac{2n+3}{n} \text{ with } n \in \mathbb{N} \]| \(a_1\) | \(a_2\) | \(a_3\) | \(a_{10}\) | \(a_{1000}\) | \(a_{100000}\) |
|---|---|---|---|---|---|
| 5 | 3.5 | 3 | 2.3 | 2.003 | 2.00003 |
As \(n\) grows larger, the terms of the sequence get closer and closer to 2. This value is called the limit of the sequence. If the terms of the sequence get closer to some value as \(n\) increases, then we say the sequence converges to that value. If the terms of the sequence do not get close to a certain value, then we say the sequence diverges. Another common phrasing is that as \(n\) approaches infinity, the terms of the sequence approach the limit. We can formally write this as:
\[\lim_{n \to \infty} \frac{2n+3}{n} = 2 \]Another common way to refer to the limit is by saying that the limes of the sequence is 2. The limes is the latin word for limit.
Epsilon-Neighborhood
To formally define the limit of a sequence, we first introduce the concept of an epsilon neighborhood (or epsilon strip). This is a region around a suspected limit with a radius of \(\epsilon\), where \(\epsilon > 0\).
The index of the term that first enters this neighborhood is called the dipping number or entry index, and is denoted as \(N_{\epsilon}\) or \(N_0\). So for example if we have a sequence \(a_n\) that converges to a limit \(L\), then for every \(\epsilon > 0\) we can define the neighborhood around \(L\) as:
\[\{n \in \mathbb{N} | \quad |a_n - L| < \epsilon\} \text{ or } \{n \in \mathbb{N} | a_n \in (L-\epsilon, L+\epsilon)\} \]The entry index \(N_{\epsilon}\) is the index of the term that first enters this neighborhood. This means that for all \(n \geq N_{\epsilon}\), the terms \(a_i\) are in the neighborhood around \(L\), i.e. \(a_i \in (L-\epsilon, L+\epsilon) \forall i \geq N_{\epsilon}\).
For a given sequence \(a_n = \frac{2n+3}{n}\) and \(\epsilon = 0.1\), we can calculate the entry index \(N_{0.1}\) by solving the inequality:
\[\begin{align*} \left|\frac{2n+3}{n} - 2\right| < 0.1 \\ \left|\frac{3}{n}\right| < 0.1 \\ \frac{3}{n} < 0.1 \\ 3 < 0.1n \\ 30 < n \end{align*} \]So for \(\epsilon = 0.1\), the entry index \(N_{0.1} = 31\). We can check this by calculating the terms of the sequence for \(n=29\), \(n=30\), and \(n=31\):
- \(a_{29} = \frac{2*29+3}{29} = 2.1034\)
- \(a_{30} = \frac{2*30+3}{30} = 2.1\)
- \(a_{31} = \frac{2*31+3}{31} = 2.0968\)
The entry index is 31 not 30 as the terms must be less than 0.1 away from the limit.
This is what D’Alembert and cauchy used to make the first definition of a limit. A sequence \(a_n\) converges to a limit \(L\) if for every \(\epsilon > 0\) there exists an entry index \(N_{\epsilon}\) such that for all \(n \geq N_{\epsilon}\) the terms \(a_n\) are in the \(\epsilon\)-neighborhood around \(L\). In other words, after a certain point in the sequence, all terms are within \(\epsilon\) of the limit. More formally:
\[L \text{ is the limit of } a_n \text{ if } \forall \epsilon > 0, \exists N_{\epsilon} \in \mathbb{N} \text{ such that } \forall n \geq N_{\epsilon}, |a_n - L| < \epsilon \]Another way to define the limit is to say that a sequence \(a_n\) converges to a limit \(L\) if for every \(\epsilon > 0\) there exists a finite number of terms in the sequence that are outside the \(\epsilon\)-neighborhood. These two definitions are equivalent. As in the first definition, there are a finite many terms outside the neighborhood, all terms where \(n \leq N_{\epsilon}\) and which then means there are an infinite number of terms inside the neighborhood. We can define the elements outside the neighborhood just like we did with the elements inside the neighborhood:
\[\{n \in \mathbb{N} | \quad |a_n - L| \geq \epsilon\} \text{ or } \{n \in \mathbb{N} | a_n \notin (L-\epsilon, L+\epsilon)\} \]An important note is that a sequence has at most one real number as its limit if it is a real valued sequence. The limit can not be infinity as infinity is not a real number. So if a sequence converges to infinity, it is divergent. We can also define this more formally. A sequence \(a_n\) converges/diverges to \(+\infty\) if for every \(T > 0\) there exists an entry index \(N_T\) such that for all \(n \geq N_T\) the terms are:
\[\lim_{n \to \infty} a_n = +\infty \text{ if } \forall T > 0, \exists N_T \in \mathbb{N} \text{ such that } \forall n \geq N_T, a_n > T \]The same holds for \(-\infty\) if \((-a_n)\) converges to \(+\infty\).
If a sequence converges to the limit 0 then we say that the sequence is a null sequence. These are important sequences to look at as they are the building blocks for many other sequences and also later for series.
For each sequence the limit is unique. So if a sequence converges to a limit, then this limit is unique. The proof of this is rather intuitive. Let’s assume that a sequence converges to two different limits \(L\) and \(M\). Then if we define an epsilon so that the neighborhood around \(L\) and \(M\) do not overlap. For example if \(\epsilon = \frac{|L-M|}{2}\) then the neighborhoods around \(L\) and \(M\) do not overlap.
\[(L-\epsilon, L+\epsilon) \cap (M-\epsilon, M+\epsilon) = \emptyset \]
We know that by definition that all terms outside of an epsilon neighborhood are finite and the terms inside the neighborhood are infinite. However, if the neighborhoods do not overlap then the infinite epsilon neighborhood around \(L\) is part of the finite elements outside the neighborhood around \(M\) and vice versa. This is a contradiction and therefore the limit must be unique.
We can also show that all sequences that converge are bounded. intuitively this might make sense to some but we can also prove this. If a sequence converges to a limit \(L\) then we can choose \(\epsilon = 1\). We then know that there are infinite many terms in the neighborhood around \(L\). So these values are bounded by \(L+1\) and \(L-1\). We then also know that there are only a finite number of terms outside of this neighborhood and that these together cover the whole sequence. To find the bounds we then need to find the maximum and minimum of the finite terms. We know that these values are larger than \(L+1\) and smaller than \(L-1\) as otherwise they would be in the neighborhood. So the sequence is bounded (For real valued sequences, otherwise if one of the bounds is infinity then the sequence is not bounded).
However, the other way around is not true. Not all bounded sequences converge. For example the sequence \(a_n = (-1)^n\) is bounded between -1 and 1 but does not converge. This is because the terms keep switching between -1 and 1 and do not get closer to a certain value.
\[a_n \text{ converges} \implies a_n \text{ is bounded} \]A sequence converges to a limit \(L\) if for every \(\epsilon > 0\) the set
\[\{n \in \mathbb{N} | a_n \notin (L-\epsilon, L+\epsilon)\} \]is finite (the indices outside the epsilon neighborhood). Specifically if we set \(\epsilon = 1\) then we can say that the set of indices outside the epsilon neighborhood is finite:
\[E = \{n \in \mathbb{N} | a_n \notin (L-1, L+1)\} \]For all \(n \in \mathbb{N} \setminus E\) we then have the follow:
\[|a_n| = |a_n - L + L| \leq |a_n - L| + |L| \leq 1 + |L| \]Notice that here the reason the difference \(|a_n - L|\) is bounded by 1 is because we chose \(\epsilon = 1\). So we can say that the sequence is bounded by \(|L| + 1\). We can then pick a maximum value \(C = \max \{|a_n| \mid n \in E \}\) from the infinite epsilon neighborhood. The bound for the entire sequence can then be defined as:
\[|a_n| \leq M \text{ where } M = \max \{C, |L| + 1\} + 1 \]Prove that the 2 definitions of a limit are the same
For the constant sequence such as \(a_n = 5\) the limit is the constant itself, so in this case 5. This is rather obvious but we can also prove it. By definition we know that after some specific index \(N_{\epsilon}\) all terms have to be within the epsilon neighborhood around the limit and because epsilon is larger than 0 so get the following that needs to be satisfied for all \(n \geq N_{\epsilon}\):
\[|a_n - L | < \epsilon \implies |a_n - L| = 0 < \epsilon \]In this case \(L\) is simply 5. This can also be generalized to any constant sequence:
\[(a_n)_{n \geq 1} = c \implies \lim_{n \to \infty} a_n = c \]Because the following always holds:
\[\begin{align*} |a_n - c| = |c - c| = 0 \forall n \geq 1 \\ |a_n - c| = 0 < \epsilon \forall n \geq 1 \text{ for any } \epsilon > 0 \end{align*} \]The next sequence we can look at is the following:
\[(a_n)_{n \geq 1} = \frac{1}{n} = 1, \frac{1}{2}, \frac{1}{3}, \ldots \]This is a so called harmonic sequence. In general the harmonic sequence is defined as:
\[(a_n)_{n \geq 1} = \frac{1}{a + (n-1)d} = \frac{1}{a}, \frac{1}{a + d}, \frac{1}{a + 2d}, \ldots \]where \(a\) is the first term and \(d\) is the common difference. In the above case \(a = 1\) and \(d = 1\). We can see that the terms of the sequence get closer and closer to 0 as \(n\) increases. So we could suspect that the limit of this sequence is 0. We can also prove this using the epsilon neighborhood definition of a limit. We want to show that for every \(\epsilon > 0\) there exists an index \(N_{\epsilon}\) such that for all \(n \geq N_{\epsilon}\) the following holds:
\[|a_n - 0| < \epsilon \text{ or } \frac{1}{n} < \epsilon \]For this sequence again we can get \(|a_n - 0| < \epsilon\) for all \(n \geq N_{\epsilon}\). Because of Archimedes principle we know that for any \(x > 0\) there exists a \(n \in \mathbb{N}\) such that \(y \leq nx\) for all \(y \in \mathbb{R}\). If we set \(x = \epsilon\) and \(y = 1\) then we know the following:
\[\begin{align*} y \leq nx \\ 1 \leq N_{\epsilon} \epsilon \\ \frac{1}{\epsilon} \leq N_{\epsilon} \end{align*} \]So we can choose \(N_{\epsilon} = \lceil \frac{1}{\epsilon} \rceil\) which is the smallest integer larger than or equal to \(\frac{1}{\epsilon}\). This means that for all \(n \geq N_{\epsilon}\) the following holds:
\[|a_n - 0| = \frac{1}{n} \leq \frac{1}{N_{\epsilon}} < \epsilon \]So the limit of the sequence is 0. We call such sequences that converge to 0 null or zero sequences. This is a very important class of sequences as they are a building block for convergent series. So we formally say that a sequence is a null sequence if:
\[\lim_{n \to \infty} a_n = 0 \]We have seen that some index \(N_{\epsilon}\) exists such that for all \(n \geq N_{\epsilon}\) the harmonic sequence is within the epsilon neighborhood around 0. We can also calculate this index for a given epsilon. For example if we had \(\epsilon = 0.8\) then we can calculate $N_0.8 by doing the following:
\[\begin{align*} \frac{1}{N_{0.8}} < 0.8 \\ 1 < 0.8N_{0.8} \\ \frac{1}{0.8} < N_{0.8} \\ 1.25 < N_{0.8} \end{align*} \]So \(N_{0.8} = 2\) which means that for \(\epsilon = 0.8\) all terms after \(n=2\) are within the epsilon neighborhood around 0. We can also see this by calculating the terms of the sequence for \(n=1\), \(n=2\), and \(n=3\) etc.
\[\begin{align*} |a_1 - 0| = |1 - 0| = 1 \\ |a_2 - 0| = |0.5 - 0| = 0.5 \\ |a_3 - 0| = |0.333 - 0| = 0.333 \\ \dots \end{align*} \]Let’s look at the following sequence:
\[(a_n)_{n \geq 1} = \frac{n}{n+1} = \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \ldots \]By observing the terms of the sequence we can see that they get closer and closer to 1 as \(n\) increases. We can also prove this using the epsilon neighborhood definition of a limit. We want to show that for every \(\epsilon > 0\) there exists an index \(N_{\epsilon}\) such that for all \(n \geq N_{\epsilon}\) the following holds:
\[|a_n - 1| < \epsilon \text{ or } \left|\frac{n}{n+1} - 1\right| < \epsilon \]We can rewrite this as:
\[\begin{align*} \left|\frac{n}{n+1} - 1\right| < \epsilon \\ \left|\frac{n - (n+1)}{n+1}\right| < \epsilon \\ \left|\frac{-1}{n+1}\right| < \epsilon \\ \frac{1}{n+1} < \epsilon \end{align*} \]Then by the Archimedes property we know that some \(N_{\epsilon} \in \mathbb{N}\) exists such that:
\[\begin{align*} \frac{1}{N_{\epsilon}+1} < \epsilon \\ 1 < \epsilon(N_{\epsilon}+1) \\ \frac{1}{\epsilon} < N_{\epsilon}+1 \\ \frac{1}{\epsilon} - 1 < N_{\epsilon} \end{align*} \]Which means that the sequence converges to 1. We can also calculate the entry index for a given epsilon. For example if we had \(\epsilon = 0.1\) then we can calculate \(N_{0.1}\) by doing the following:
\[\begin{align*} \frac{1}{N_{0.1}+1} < 0.1 \\ 1 < 0.1(N_{0.1}+1) \\ \frac{1}{0.1} < N_{0.1}+1 \\ 10 < N_{0.1}+1 \\ 9 < N_{0.1} \end{align*} \]So \(N_{0.1} = 10\) which means that for \(\epsilon = 0.1\) all terms after \(n=10\) are within the epsilon neighborhood around 1.
We have seen lots of examples of sequences that converge to a limit. But what about sequences that do not converge? Let’s look at the following sequence:
\[(a_n)_{n \geq 1} = (-1)^n = -1, 1, -1, 1, \ldots \]Intuitively it is clear that this sequence does not converge as the terms keep switching between -1 and 1. We can also prove this by contradiction. Let’s assume that the sequence converges to a limit \(L\). Then the following must hold for \(\epsilon > 0\) and \(\forall n \geq N_{\epsilon}\):
\[|a_n - L| < \epsilon \]Let’s assume by contradiction that a limit exists and that \(\epsilon = \frac{1}{2}\). We know that \(|a_n - a_{n+1}| = 2\) for all \(n \in \mathbb{N}\). Then we also know that there exists an index \(N_{\epsilon}\) such that for all \(n \geq N_{\epsilon}\) the following holds:
\[\begin{align*} 2 &= |a_n - a_{n+1}| \\ &= |a_n - L + L - a_{n+1}| \\ &\leq |a_n - L| + |L - a_{n+1}| \\ &\leq \epsilon + \epsilon = \frac{1}{2} + \frac{1}{2} = 1 2 &\leq 1 \end{align*} \]This is a contradiction and therefore the sequence does not converge. Note that we just added 0 by adding and subtracting \(L\) and then used the triangle inequality. The reason why we can say that \(|a_n - L| + |L - a_{n+1}| \leq \epsilon + \epsilon\) is because we assumed that the sequence converges to \(L\) and therefore for all \(n \geq N_{\epsilon}\) the terms are within the epsilon neighborhood around \(L\). Key here is for the terms greater than or equal to the entry index \(N_{\epsilon}\), so if it holds for \(a_n\) then it also holds for \(a_{n+1}\) as the term is even larger than \(n\).
Lastly let’s look at the following sequence:
\[(a_n)_{n \geq 1} = n = 1, 2, 3, 4, \ldots \]This sequence is actually a special case of the arithmetic sequence. An arithmetic sequence is a sequence where the difference between two consecutive terms is constant. In this case the constant is 1 but we could also for example look at the sequence \(a_n = 2n + 3\) as an arithmetic sequence with a common difference of 2. We can also write this more generally as:
\[a_n = a_1 + (n-1)d \text{ with } d \in \mathbb{R} \text{ and } n \in \mathbb{N} \]The specific sequence above does not converge as the terms keep getting larger and larger. We can prove this by contradiction. Let’s assume that the sequence converges to a limit \(L\). Then for \(\epsilon = 1\) we know that there exists an index \(N_{\epsilon}\) such that for all \(n \geq N_{\epsilon}\) the following holds:
\[|a_n - L| < 1 \text{ or } |n - L| < 1 \]However, \(n\) is positive and gets larger and larger, therefore the distance also gets larger and larger. So there exists no such \(N_{\epsilon}\) that satisfies the inequality for all \(n \geq N_{\epsilon}\). Therefore the sequence does not converge. Or in other words we have:
\[|n - L| < 1 \implies -1 < n - L < 1 \implies L - 1 < n < L + 1 \]So for a fixed \(L\) the number \(n\) is in the interval \((L-1, L+1)\) which is not possible for all \(n \geq N_{\epsilon}\) as \(n\) gets larger and larger. So the sequence does not converge.
Suppose we have the following sequence for \(a > 0\):
\[\lim_{n \to \infty} \sqrt[n]{a} = a^{1/n} = 1 \]and want to prove that the limit of this sequence is 1. For \(a = 1\) this is rather obvious as the terms are all 1. But what about for \(a \neq 1\)? First we look at the case of \(a > 1\). For this we can define the following new sequence:
\[b_n = a_n - 1 = \sqrt[n]{a} - 1 \]then we have \(b_n \geq 0\) for all \(n \in \mathbb{N}\). By the binomial theorem we also have:
\[1 + n b_n \leq (1 + b_n)^n = (1 + \sqrt[n]{a} - 1)^n = a \]By rearranging this we get:
\[\begin{align*} 1 + n b_n \leq a \\ n b_n \leq a - 1 \\ b_n \leq \frac{a - 1}{n} \\ 0 \leq b_n \leq \frac{a - 1}{n} \end{align*} \]Because the right side of the inequality goes to 0 as \(n\) goes to infinity, we can conclude that \(b_n\) also goes to 0 as \(n\) goes to infinity. So we have:
\[\lim_{n \to \infty} b_n = \sqrt[n]{a} - 1 = 0 \implies \lim_{n \to \infty} \sqrt[n]{a} = 1 \]Now we just need to prove the case for \(0 < a < 1\). For this we can set \(c= \frac{1}{a}\) then \(c > 1\) and we use our previous result so \(\lim_{n \to \infty} \sqrt[n]{c} = 1\). We can then rewrite the sequence as:
\[1 = \lim_{n \to \infty} \sqrt[n]{c} = \lim_{n \to \infty} \sqrt[n]{\frac{1}{a}} = \lim_{n \to \infty} \frac{\sqrt[n]{1}}{\sqrt[n]{a}} = \lim_{n \to \infty} \frac{1}{\sqrt[n]{a}} = \frac{1}{\lim_{n \to \infty} \sqrt[n]{a}} = 1 \]which implies that \(\lim_{n \to \infty} \sqrt[n]{a} = 1\) as well. So we can conclude that for all \(a > 0\) the limit of the sequence \(\sqrt[n]{a}\) is 1.
Suppose we have the following sequence:
\[\lim_{n \to \infty} sqrt[n]{n} = \sqrt{1}, \sqrt[2]{2}, \sqrt[3]{3}, \ldots \]We could assume that the limit of this sequence is 1 as the terms get closer and closer to 1 or also because we can rewrite the sequence as:
\[\lim_{n \to \infty} \sqrt[n]{n} = n^{\frac{1}{n}} \]and then as \(n\) goes to infinity the exponent goes to 0 just like above. However, this reasoning would be incorrect as the the term also grows as the exponent grows. But we can still prove that the sequence converges to 1 by bringing it into a form that we can analyze. We can rewrite the sequence as follows:
\[n^{\frac{1}{n}} = e^{\ln(n^{\frac{1}{n}})} = e^{\frac{\ln(n)}{n}} \]Now we can analyze the limit of the exponent \(\frac{\ln(n)}{n}\) as \(n\) goes to infinity. It is rather obvious that this limit is 0 as the logarithm grows much slower than the linear function \(n\). We can also prove this using L’Hôpital’s rule. So we have e^0 which is 1. So we can conclude that the limit of the sequence is 1.
We could also solve this in a way similar to the previous example. By the definition of the limit we want to show that for every \(\epsilon > 0\) there exists an index \(N_{\epsilon}\) such that for all \(n \geq N_{\epsilon}\) the following holds:
\[\left| \sqrt[n]{n} - 1 \right| < \epsilon \]We can rewrite this as:
\[\begin{align*} \left| n^{\frac{1}{n}} - 1 \right| < \epsilon \\ - \epsilon < n^{\frac{1}{n}} - 1 < \epsilon \\ 1 - \epsilon < n^{\frac{1}{n}} < 1 + \epsilon \\ (1 - \epsilon)^{n} < n < (1 + \epsilon)^{n} \end{align*} \]We then use the binomial theorem to expand the right side:
\[\begin{align*} (1 + \epsilon)^{n} = 1 + n\epsilon + \frac{n(n-1)}{2}\epsilon^2 + \ldots + \epsilon^n \\ (1 + \epsilon)^{n} \geq 1 + \frac{n(n-1)}{2}\epsilon^2 + 0 \\ (1 + \epsilon)^{n} \geq \frac{n(n-1)}{2}\epsilon^2 \end{align*} \]Which then gives us:
\[\begin{align*} n < (1 + \epsilon)^{n} \geq \frac{n(n-1)}{2}\epsilon^2 \\ n < \frac{n(n-1)}{2}\epsilon^2 \\ 2n < n(n-1)\epsilon^2 \\ 2 < (n-1)\epsilon^2 \\ \frac{2}{\epsilon^2} < n-1 \\ \frac{2}{\epsilon^2} + 1 < n \end{align*} \]So we can choose \(N_{\epsilon} = \lceil \frac{2}{\epsilon^2} + 1 \rceil\) for any \(\epsilon > 0\), showing that the limit of the sequence is 1.
Suppose we have the following sequence:
\[\lim_{n \to \infty} \sqrt{n^2 + 3n} - n \]To solve this we want to remove as many of the roots and terms of \(n\) as possible. A nice trick here is extend the root with a fraction equal to 1. We can rewrite the sequence as follows:
\[\begin{align*} \lim_{n \to \infty} \left(\sqrt{n^2 + 3n} - n\right)^2 = \lim_{n \to \infty} \frac{\sqrt{n^2 + 3n} - n}{1} \cdot \frac{\sqrt{n^2 + 3n} + n}{\sqrt{n^2 + 3n} + n} \\ = \lim_{n \to \infty} \frac{(\sqrt{n^2 + 3n})^2 - n^2}{\sqrt{n^2 + 3n} + n} \\ = \lim_{n \to \infty} \frac{n^2 + 3n - n^2}{\sqrt{n^2 + 3n} + n} \\ = \lim_{n \to \infty} \frac{3n}{\sqrt{n^2 + 3n} + n} \\ = \lim_{n \to \infty} \frac{3n}{\sqrt{n^2(1 + \frac{3}{n})} + n} \\ = \lim_{n \to \infty} \frac{3n}{n \sqrt{1 + \frac{3}{n}} + n} \\ = \lim_{n \to \infty} \frac{3}{\sqrt{1 + \frac{3}{n}} + 1} \\ = \lim_{n \to \infty} \frac{3}{K + 1} \end{align*} \]Where \(K = \lim_{n \to \infty} \sqrt{1 + \frac{3}{n}}\). We can then use the previous example to show that \(K = 1\). So we have:
\[\left|\sqrt{1 + \frac{3}{n}} - 1\right| < \epsilon \]We can rewrite this as:
\[\begin{align*} \left|\sqrt{1 + \frac{3}{n}} - 1\right| = \left|\frac{\sqrt{1 + \frac{3}{n}} - 1}{1}\frac{\sqrt{1 + \frac{3}{n}} + 1}{\sqrt{1 + \frac{3}{n}} + 1}\right| \\ = \left|\frac{(1 + \frac{3}{n}) - 1}{\sqrt{1 + \frac{3}{n}} + 1}\right| \\ = \left|\frac{\frac{3}{n}}{\sqrt{1 + \frac{3}{n}} + 1}\right| \\ = \frac{3}{n(\sqrt{1 + \frac{3}{n}} + 1)} \end{align*} \]We can leave out the absolute signs as the nominator is always positive for \(n \geq 1\) and so is the denominator, as a square root is always positive. If we set \(n=1\) we can also see that:
\[n\sqrt{1 + \frac{3}{n}} + 1 = 1\sqrt{1 + 3} + 1 = 2 \]So the denominator is always larger than 2 for all \(n \geq 1\). So putting this all together we get:
\[\begin{align*} \left|\sqrt{1 + \frac{3}{n}} - 1\right| < \epsilon \\ \frac{3}{n(\sqrt{1 + \frac{3}{n}} + 1)} < \epsilon \\ \frac{3}{2n} < \epsilon \\ 3 < 2n\epsilon \\ \frac{3}{2\epsilon} < n \end{align*} \]So we can choose \(N_{\epsilon} = \lceil \frac{3}{2\epsilon} \rceil\) for any \(\epsilon > 0\). Therefore the limit of the expression is 1, so K=1. We can then plug this back into our original expression:
\[\lim_{n \to \infty} \sqrt{n^2 + 3n} - n = \lim_{n \to \infty} \frac{3}{K + 1} = \frac{3}{1 + 1} = \frac{3}{2} \]Suppose we have the following sequence:
\[\lim_{n \to \infty} \sqrt{n} - \sqrt{n + 1} \]an initial assumption would be that the limit is 0 as the terms grow, the factor of 1 becomes irrelevant so we have \(\sqrt{n} - \sqrt{n + 1} \approx \sqrt{n} - \sqrt{n} = 0\). This also becomes visible if we rewrite the sequence as follows using the similar trick as above:
\[\begin{align*} \sqrt{n} - \sqrt{n + 1} &= \frac{\sqrt{n} - \sqrt{n + 1}}{1} \cdot \frac{\sqrt{n} + \sqrt{n + 1}}{\sqrt{n} + \sqrt{n + 1}} \\ &= \frac{(\sqrt{n})^2 - (\sqrt{n + 1})^2}{\sqrt{n} + \sqrt{n + 1}} \\ &= \frac{n - (n + 1)}{\sqrt{n} + \sqrt{n + 1}} \\ &= \frac{-1}{\sqrt{n} + \sqrt{n + 1}} \leq \frac{-1}{\sqrt{n} + \sqrt{n}} = \frac{-1}{2\sqrt{n}} \end{align*} \]If we then but this into the definition of the limit we get:
\[\begin{align*} \left|(\sqrt{n} - \sqrt{n + 1}) - 0\right| < \epsilon \\ \left|\frac{-1}{\sqrt{n} + \sqrt{n + 1}}\right| < \epsilon \\ \left|\frac{-1}{2\sqrt{n}}\right| < \epsilon \\ \frac{1}{2\sqrt{n}} < \epsilon \\ \frac{1}{2\epsilon} < \sqrt{n} \\ \frac{1}{4\epsilon^2} < n \end{align*} \]So we can choose \(N_{\epsilon} = \lceil \frac{1}{4\epsilon^2} \rceil\) for any \(\epsilon > 0\). Therefore the limit of the expression is 0.
Properties of Convergent Sequences
There are some key properties of convergent sequences that are important to know. These properties can help us understand how sequences behave and how we can manipulate them.
To start with, if we have the sequences \(a_n, b_n\) and \(c_n\) and we define \(c_n = a_n \pm b_n\) then we can also look at some properties of the limit of the sequence \(c_n\). If we have the sequences \(a_n\) and \(b_n\) that converge to the limits \(a\) and \(b\) respectively, then we can say that the limit of the sequence \(c_n\) converges to the sum of the limits of the sequences \(a_n\) and \(b_n\). In other words if \(\lim_{n \to \infty} a_n = a\) and \(\lim_{n \to \infty} b_n = b\), then:
\[\lim_{n \to \infty} c_n = \lim_{n \to \infty} (a_n \pm b_n) = \lim_{n \to \infty} a_n \pm \lim_{n \to \infty} b_n = a \pm b \]If the sequence \(a_n\) converges to \(a\) then we can say that for every \(\epsilon > 0\) there exists an index \(N_{\epsilon}\) such that for all \(n \geq N_1\) the following holds:
\[|a_n - a| < \epsilon \text{ or } |a_n - a| < \frac{\epsilon}{2} \]The same holds for the sequence \(b_n\) and we can say that for every \(\epsilon > 0\) there exists an index \(N_{\epsilon}\) such that for all \(n \geq N_2\) the following holds:
\[|b_n - b| < \epsilon \text{ or } |b_n - b| < \frac{\epsilon}{2} \]If we know but these together we can then say that for all \(N_{\epsilon} = \max(N_1, N_2)\) the following holds:
\[\begin{align*} |c_n - (a \pm b)| &= |(a_n \pm b_n) - (a \pm b)| \\ &= |(a_n - a) \pm (b_n - b)| \\ &\leq |(a_n - a) + (b_n - b)|=|a_n - a| + |b_n - b| < \frac{\epsilon}{2} + \frac{\epsilon}{2} = \epsilon \\ &\leq |(a_n - a) - (b_n - b)| = |a_n - a| + |-(b_n - b)| = |a_n - a| + |b_n - b| < \frac{\epsilon}{2} + \frac{\epsilon}{2} = \epsilon \end{align*} \]Suppose we have the following sequences:
\[\lim _{n \to \infty} \frac{n}{n+1} \]Then we can solve this using the above rule. We can rewrite the sequence as follows:
\[\begin{align*} \frac{n}{n+1} &= \frac{n + 1 - 1}{n + 1} \\ &= \frac{n + 1}{n + 1} - \frac{1}{n + 1} \\ &= 1 - \frac{1}{n + 1} \end{align*} \]the limit of 1 is of course 1 and the limit of \(\frac{1}{n + 1}\) we have also already seen that it converges to 0. So we can say that:
\[\lim_{n \to \infty} \frac{n}{n+1} = 1 - 0 = 1 \]Similarly if we say that the sequences \(a_n\) and \(b_n\) are bounded then we can also say that the sequence \(c_n\) is bounded. The bounds of the sequence \(c_n\) are the sum of the bounds of the sequences \(a_n\) and \(b_n\). In other words if \(a_n\) is bounded by \(m_1\) and \(M_1\) and \(b_n\) is bounded by \(m_2\) and \(M_2\), then we can say that the sequence \(c_n = a_n \pm b_n\) is bounded by \(m_1 + m_2\) and \(M_1 + M_2\).
Since \(|a_n| \leq M_1\) and \(|b_n| \leq M_2\),
\[|a_n + b_n| \leq |a_n| + |b_n| \leq M_1 + M_2 \]for all \(n \in \mathbb{N}\).
However, we can’t say the opposite. If \(c_n\) converges to \(c\), then we can’t say that \(a_n\) and \(b_n\) also converge! A simple counterexample is if we define the following sequences:
\[\begin{align*} a_n = (-1)^n \\ b_n = (-1)^{n+1} \\ c_n = a_n + b_n = 0 \end{align*} \]Then we can easily see that \(c_n\) converges to 0, but \(a_n\) and \(b_n\) do not converge as they oscillate between -1 and 1. We also can’t say that if \(c_n\) converges then at least one of the sequences \(a_n\) or \(b_n\) converges. This again can be seen with the same example as above. Both \(a_n\) and \(b_n\) do not converge, but \(c_n\) does converge to 0.
Another important property of convergent sequences is that if a sequence converges to a limit, then what happens in the beginning of the sequence does not matter. In other words, if we have a sequence \((a_n)_{n\geq 1}\) that converges to \(a\), then we can define a new sequence \((b_n)_{n\geq 1}\) by shifting the index of the original sequence by some \(k \in \mathbb{N}\), so \(b_n = a_{n+k}\). Then the new sequence also converges to the same limit \(a\):
\[\lim_{n \to \infty} a_n = \lim_{n \to \infty} a_{n+k} \text{ for all } k \in \mathbb{N} \]Let \(\epsilon > 0\) be given. Since \(a_n \to a\), \(\exists N\) such that \(|a_n - a| < \epsilon\) for all \(n \geq N\). But then for all \(n \geq N\), \(|a_{n+k} - a| < \epsilon\) as \(n+k \geq N\) for large enough \(n\). Thus, \(a_{n+k} \to a\).
Similarly we can also say that if \(a_n\) converges to \(a\) if we then define \(b_n = a_{n+1} + a_{n}\), then \(b_n\) also converges:
\[\lim_{n \to \infty} a_n \to a \implies \lim_{n \to \infty} b_n = \lim_{n \to \infty} (a_{n+1} + a_{n}) = a + a = 2a \]We can prove this using the definition of a limit. If \(\lim_{n \to \infty} a_n = a\), then for every \(\epsilon > 0\) there exists an index \(N_{\epsilon}\) such that for all \(n \geq N_{\epsilon}\) the following holds:
\[|a_n - a| < \epsilon \]Then we can also find an index \(N_{\epsilon}\) such that for all \(n \geq N_{\epsilon}\) the following holds:
\[|b_n - 2a| = |a_{n+1} + a_{n-1} - 2a| \leq |a_{n+1} - a| + |a_{n-1} - a| < \epsilon + \epsilon = 2\epsilon \]So we can say that \(b_n\) converges to \(2a\). The fact that we now have \(2\epsilon\) instead of \(\epsilon\) is not a problem as the archimedes principle still holds.
In fact we we can show that if \(a_n\) converges to \(a\) and we define \(b_n = a_{n+1} - a_{n}\), then \(b_n\) always converges to 0:
\[\lim_{n \to \infty} a_n = a \implies \lim_{n \to \infty} b_n = \lim_{n \to \infty} (a_{n+1} - a_{n}) = 0 \]This follows from the definition of a limit. If \(\lim_{n \to \infty} a_n = a\), then for every \(\epsilon > 0\) there exists an index \(N_{\epsilon}\) such that for all \(n \geq N_{\epsilon}\) the following holds:
\[|a_n - a| < \epsilon \]Because it holds for all \(n \geq N_{\epsilon}\), then that also includes \(n+1\) so we have:
\[|a_{n+1} - a| < \epsilon \]putting this together we get:
\[|b_n| = |a_{n+1} - a_n| = |(a_{n+1} - a) - (a_n - a)| \leq |a_{n+1} - a| + |a_n - a| < \epsilon + \epsilon = 2\epsilon \]However, the other way does not hold in general. So for example if \(b_n = a_{n+1} - a_{n}\) converges to \(0\), then we can not say that \(a_n\) converges to some limit. A simple counterexample is if we define the following sequences:
\[b_n = (-1)^{n-1} - (-1)^{n} = 0 \]Then we can see that \(b_n\) converges to 0, but \(a_n\) does not converge as it oscillates between -1 and 1.
Convergent sequences can also be scaled. So if we have a sequence \(a_n\) that converges to \(a\) and we multiply it by a constant \(c\), then the new sequence \(c \cdot a_n\) also converges to \(c \cdot a\). In other words:
\[\lim_{n \to \infty} c \cdot a_n = c \cdot \lim_{n \to \infty} a_n = c \cdot a \]Given \(\epsilon > 0\), since \(a_n \to a\), \(\exists N\) such that \(|a_n - a| < \frac{\epsilon}{|c|}\) for all \(n \geq N\) (if \(c \neq 0\); for \(c = 0\) the result is trivial). Then
\[|c a_n - c a| = |c| \cdot |a_n - a| < |c| \cdot \frac{\epsilon}{|c|} = \epsilon. \]So \(c a_n \to c a\).
Let \(a_n = \frac{1}{n}\), \(c = 5\). Then,
\[\lim_{n \to \infty} 5 a_n = 5 \cdot 0 = 0. \]The same goes for multiplying two convergent sequences. If we have two sequences \(a_n\) and \(b_n\) that converge to \(a\) and \(b\) respectively, then the sequence \(a_n \cdot b_n\) also converges to \(a \cdot b\). In other words:
\[\lim_{n \to \infty} a_n \cdot b_n = \lim_{n \to \infty} a_n \cdot \lim_{n \to \infty} b_n = a \cdot b \]The proof is very similar to previous ones. We want to show that for every \(\epsilon > 0\) there exists an index \(N_{\epsilon}\) such that for all \(n \geq N_{\epsilon}\) the following holds:
\[|a_n \cdot b_n - a \cdot b| < \epsilon \]we can rewrite this term and use the triangle inequality:
\[\begin{align*} |a_n \cdot b_n - a \cdot b| &= |a_n \cdot b_n - a_n \cdot b + a_n \cdot b - a \cdot b| \\ &= |a_n \cdot (b_n - b) + b \cdot (a_n - a)| \\ &\leq |a_n| \cdot |b_n - b| + |b| \cdot |a_n - a| \end{align*} \]Because \(a_n\) converges we also know that it is bounded by some \(K\) and \(k\) such that \(k \leq a_n \leq K\) for all \(n \geq N_{1}\). So for all \(n \geq N_{1}\) we can say that:
\[|a_n| \leq K \]and because \(|b|\) is just a constant and \(a_n\) and \(b_n\) converge we can write:
\[|a_n - a| < \frac{\epsilon}{K + |b|} \text{ and } |b_n - b| < \frac{\epsilon}{K + |b|} \]Putting this all together we get:
\[\begin{align*} |a_n \cdot b_n - a \cdot b| &< \epsilon \\ &\leq |a_n| \cdot |b_n - b| + |b| \cdot |a_n - a| \\ &\leq K \cdot |b_n - b| + |b| \cdot |a_n - a| \\ &\leq K \cdot \frac{\epsilon}{K + |b|} + |b| \cdot \frac{\epsilon}{K + |b|} \\ &= \frac{K \cdot \epsilon + |b| \cdot \epsilon}{K + |b|} \\ &= \frac{(K + |b|) \cdot \epsilon}{K + |b|} \\ &= \epsilon \]Suppose we have the following sequences:
\[\lim_{n \to \infty} \frac{n^2 - 2n}{n^2 + n + 1} \]We can then rewrite this as follows:
\[\begin{align*} \frac{n^2 - 2n}{n^2 + n + 1} &= \frac{n^2(1 - \frac{2}{n})}{n^2(1 + \frac{1}{n} + \frac{1}{n^2})} \\ &= \frac{1 - \frac{2}{n}}{1 + \frac{1}{n} + \frac{1}{n^2}} \\ &= \frac{1 - 0}{1 + 0 + 0} \\ &= 1 \end{align*} \]Here we used the fact that \(\lim_{n \to \infty} \frac{1}{n} = 0\) and our multiplication rule for limits meaning \(\lim_{n \to \infty} \frac{1}{n^2} = 0 \cdot 0\) and the addition rules.
Lastly we can also say that if we have two sequences \(a_n\) and \(b_n\) that converge to \(a\) and \(b\) respectively, then the sequence \(\frac{a_n}{b_n}\) also converges to \(\frac{a}{b}\) as long as \(b \neq 0\). In other words:
\[\lim_{n \to \infty} \frac{a_n}{b_n} = \frac{\lim_{n \to \infty} a_n}{\lim_{n \to \infty} b_n} = \frac{a}{b} \]Since \(b_n \to b \neq 0\), \(\exists N_1\) such that \(|b_n| \geq |b|/2 > 0\) for all \(n \geq N_1\) (by the definition of limit). Let \(\epsilon > 0\). Since \(a_n \to a\) and \(b_n \to b\), \(\exists N_2\) such that for all \(n \geq N_2\),
\[|a_n - a| < \frac{\epsilon |b|}{3}, \qquad |b_n - b| < \min\left(\frac{|b|}{2}, \frac{\epsilon |b|^2}{3 (|a|+1)}\right) ``` Set $N = \max(N_1, N_2)$. Then for $n \geq N$, ```math \begin{align*} \left| \frac{a_n}{b_n} - \frac{a}{b} \right| &= \left| \frac{a_n b - a b_n}{b_n b} \right| \\ &= \left| \frac{a_n b - a b + a b - a b_n}{b_n b} \right| \\ &= \left| \frac{b(a_n - a) + a(b - b_n)}{b_n b} \right| \\ &\leq \frac{|b||a_n - a| + |a||b_n - b|}{|b_n||b|} \end{align*} \]By our choice, \(|b_n| \geq |b|/2\) and \(|a_n - a|\), \(|b_n - b|\) are both small. Plug in these bounds and simplify to get the desired result (details as in standard analysis texts).
Suppose we have the following sequence:
\[\lim_{n \to \infty} (1 + \frac{1}{n})^b \]where \(b \in \mathbb{Z}\). Then we already know that the limit of 1 is 1 and the limit of \(\frac{1}{n}\) is 0. So we know that \(\lim_{n \to \infty} (1 + \frac{1}{n}) = 1\). If \(b > 0\) then we just essentially have this term \(b\) times which is still 1. If \(b < 0\) then we have the term \(\frac{1}{(1 + \frac{1}{n})^{|b|}}\) which also converges to 1 as \(n\) goes to infinity. So we can conclude that the limit of the sequence is 1 for all \(b \in \mathbb{Z}\).
The example above as we can also generalize this to a property. If we have a sequence \(a_n\) that converges to \(a\) we then have the following property:
\[\lim_{n \to \infty} (a_n)^b = a^b \text{ for all } b \in \mathbb{R} \]From the above we actually notice that it also just a generalization of the following property of limits:
\[\lim_{n \to \infty} \sqrt[b]{a_n} = \sqrt[b]{\lim_{n \to \infty} a_n} \text{for } b > 0 \]This follows from the previous property of exponents as the square root is just an exponent of \(\frac{1}{2}\) and the \(b\)-th root is an exponent of \(\frac{1}{b}\). So we can generalize this to any positive exponent \(b\). However, if we are taking the \(n\)-th root or power where \(n\) is the index of the term then we can not use this property as the exponent is not constant but rather depends on \(n\).
Suppose we have the following sequence:
\[\lim_{n \to \infty} \frac{3^n + (-2)^n}{3^n - 2^n} \]We can rewrite this as follows:
\[\begin{align*} \lim_{n \to \infty} \frac{3^n + (-2)^n}{3^n - 2^n} &= \lim_{n \to \infty} \frac{3^n(1 + (-\frac{2}{3})^n)}{3^n(1 - (\frac{2}{3})^n)} \\ &= \lim_{n \to \infty} \frac{\lim_{n \to \infty} 1 + \lim_{n \to \infty} (-\frac{2}{3})^n}{\lim_{n \to \infty} 1 - \lim_{n \to \infty} (\frac{2}{3})^n} \\ &= \frac{1 + 0}{1 - 0} \\ &= 1 \end{align*} \]Squeeze Theorem
The squeeze theorem or sometimes also called the sandwich theorem states that if we have two sequences \((a_n)_{n\geq 1}\) and \((c_n)_{n\geq 1}\) that have the same limit \(L\) so:
\[\lim_{n \to \infty} a_n = \lim_{n \to \infty} c_n = L \]and a third sequence \((b_n)_{n\geq 1}\) for which after a certain index \(K\) the following holds:
\[a_n \leq b_n \leq c_n \text{ for all } n \geq K \]Then the sequence \((b_n)_{n\geq 1}\) also converges to \(L\) so:
\[\lim_{n \to \infty} b_n = \lim_{n \to \infty} a_n = \lim_{n \to \infty} b_n = L \]This is a very simple but powerful theorem that can be used to show that many sequences converge to a certain limit. The idea is that if we can find two sequences that are always above and below the sequence we are interested in and these two sequences converge to the same limit, so they slowly get closer and closer to each other and squeeze the sequence we are interested in, then the sequence we are interested in also converges to the same limit.
To prove the squeeze theorem, lets assume we have two sequences \((a_n)_{n\geq 1}\) and \((c_n)_{n\geq 1}\) that converge to the same limit \(L\), meaning we have the indices \(N_a \geq K\) and \(N_c \geq K\) where \(K\) is the index after which the sequence \((b_n)_{n\geq 1}\) is squeezed between \((a_n)_{n\geq 1}\) and \((c_n)_{n\geq 1}\). Then by definition of the limit we have that for all \(n \geq N_a\) and \(n \geq N_c\) the following holds:
\[|a_n - L| < \epsilon \text{ and } |c_n - L| < \epsilon \]If we then define \(N_b = \max(N_a, N_c)\) we have for all \(n \geq N_b\) as they are also larger than \(K\):
\[a_n \leq b_n \leq c_n \\ \]which can be rewritten as:
\[a_n - L \leq b_n - L \leq c_n - L \]which by definition of the above limit inequalities means that:
\[-\epsilon < a_n - L \leq b_n - L \leq c_n - L < \epsilon \]So we have that for all \(n \geq N_b\) the following holds:
\[|b_n - L| < \epsilon \]Meaning that the sequence \((b_n)_{n\geq 1}\) also converges to \(L\).
Let’s look at the sequence \(a_n = \frac{sin(n)}{n}\). We know that the sine function is bounded between -1 and 1 and then that by dividing everything by \(n\) we get the following:
\[\frac{-1}{n} \leq \frac{sin(n)}{n} \leq \frac{1}{n} \]As \(n\) goes to infinity the terms on the left and right side go to 0. So by the squeeze theorem the sequence \(a_n = \frac{sin(n)}{n}\) also converges to 0.
\[\lim_{n \to \infty} \frac{sin(n)}{n} = 0 \]Suppose we have the following sequence:
\[\lim_{n \to \infty} \sqrt[n]{5^n + 11^n + 17^n} \]We can then use the squeeze theorem. Specifically we can find the following upper and lower bounds for the sequence:
\[\sqrt[n]{17^n} \leq \sqrt[n]{5^n + 11^n + 17^n} \leq \sqrt[n]{3 \cdot 17^n} \]It logically follows that \(\sqrt[n]{17^n} = 17\) and using the previous example where we showed that the limit of \(\sqrt[n]{a} = 1\) for all \(a > 0\), we can also show that \(\sqrt[n]{3 \cdot 17^n} = 17 \cdot \sqrt[n]{3}\). So we have:
\[\begin{align*} \lim_{n \to \infty} \sqrt[n]{17^n} \leq \lim_{n \to \infty} \sqrt[n]{5^n + 11^n + 17^n} \leq \lim_{n \to \infty} \sqrt[n]{3 \cdot 17^n} \\ 17 \leq \lim_{n \to \infty} \sqrt[n]{5^n + 11^n + 17^n} \leq 17 \\ \lim_{n \to \infty} \sqrt[n]{5^n + 11^n + 17^n} = 17 \end{align*} \]Monotone Convergence Theorem
The monotone convergence theorem is a very important theorem and way to show that certain sequences converge. It states that if a sequence is monotonically increasing and bounded above or monotonically decreasing and bounded below, then the sequence converges. The intuitive idea behind this theorem is that if a sequence is monotonically increasing, then the terms of the sequence get larger and larger but are still bounded above by some value. This means that the sequence can not grow indefinitely and must converge to some limit. The same holds for monotonically decreasing sequences that are bounded below.
Lets’ formally define the theorem. First we need to remind ourselves of the definitions of monotonic sequences. A sequence \((a_n)_{n\geq 1}\) is called monotonically increasing if for all \(n \geq 1\) the following holds:
\[a_n \leq a_{n+1} \]Then if the sequence is also bounded above, i.e. there exists a real number \(c\) such that the following holds:
\[a_n \leq c \text{ for all } n \geq 1 \]Then the sequence converges to the supremum of the set of all terms of the sequence. We can write this as:
\[\lim_{n \to \infty} a_n = \sup\{a_n | n \geq 1\} \]The same holds for monotonically decreasing sequences that are bounded below. Here the limit uses the infimum instead of the supremum.
\[\lim_{n \to \infty} a_n = \inf\{a_n | n \geq 1\} \]So the formal statement of the monotone convergence theorem is:
\[a_n \text{ is monotone} \land a_n \text{ is bounded} \implies a_n \text{ converges} \]The other direction does not hold. For example the sequence \(a_n = (-1)^n \frac{1}{n}\) converges to 0 but it is only bounded by 1 and -1 and not monotonically increasing or decreasing as it oscillates between -1 and 1.
The proof of the monotone convergence theorem is rather intuitive. We will only show the proof for the case of monotonically increasing sequences that are bounded above. The proof for monotonically decreasing sequences that are bounded below is similar.
If \((a_n)_{n\geq 1}\) is bounded above, then there exists the supremum \(c = \sup\{a_n | n \geq 1\}\). This then means that because \(c\) is the smallest upper bound, we know that for every \(\epsilon > 0\) the value \(c - \epsilon\) is not an upper bound for the sequence. So there exists an index \(N_{\epsilon}\) so that \(a_{N_{\epsilon}} > c - \epsilon\).
From this it follows that for all \(n \geq N_{\epsilon}\) the following holds:
\[c - \epsilon < a_{N_{\epsilon}} \leq a_n \leq c < c + \epsilon \]Key here is that because the sequence is monotonically increasing, we know that all terms after \(N_{\epsilon}\) are larger than \(a_{N_{\epsilon}}\) so we can write \(a_n \geq a_{N_{\epsilon}}\) for all \(n \geq N_{\epsilon}\). This then leads to the definition of the limit with rearranging the terms:
\[\begin{align*} c - \epsilon < a_n < c + \epsilon \\ -\epsilon < a_n - c < \epsilon \\ |a_n - c| < \epsilon \text{ for all } n \geq N_{\epsilon} \end{align*} \]Let’s look at the following sequence where \(b \in \mathbb{Z}\) and \(q \in \mathbb{R}\).
\[(a_n)_{n \geq 1} = n^b q^n \]This sequence has the following special property:
\[\lim_{n \to \infty} n^b q^n = 0 \text{ if } 0 \leq q < 1 \]This is clear if \(q = 0\) as then all terms are 0. If \(q\) is positive so \(q > 0\) then the sequence is monotonically decreasing. We can see this if we look at the next term of the sequence and with some rearranging we get the following:
\[\begin{align*} a_{n+1} &= (n+1)^b q^{n+1} \\ &= (n+1)^b q^n \cdot q \\ &= \frac{(n+1)^b}{n^b} \cdot n^b q^n \cdot q \\ &= \frac{(n+1)^b}{n^b} \cdot a_n cdot q \\ &= \left(\frac{n+1}{n}\right)^b \cdot a_n \cdot q \\ &= \left(1 + \frac{1}{n}\right)^b \cdot a_n \cdot q \end{align*} \]Because we know the following:
\[(a_n)_{n \geq 1} = (1 + \frac{1}{n})^b \text{ then } \lim_{n \to \infty} a_n = 1 \]This sequence goes to 1 as \(n\) goes to infinity. Because the term in the brackets gets closer and closer to 1 as \(n\) increases. So the limit of this sequence is 1 which means the following holds for all \(\epsilon > 0\):
\[|(1 + \frac{1}{n})^b - 1| < \epsilon \text{ for all } n \geq N_{\epsilon} \]and because \(b \in \mathbb{Z}\) the term is always positve so if we set \(\epsilon = \frac{1}{q} -1\) then we get the following:
\[\begin{align*} |(1 + \frac{1}{n})^b - 1| < \epsilon \\ (1 + \frac{1}{n})^b - 1 < \frac{1}{q} - 1 \\ (1 + \frac{1}{n})^b < \frac{1}{q} \end{align*} \]And lastly we can use this to show that the sequence is monotonically decreasing:
\[\begin{align*} a_{n+1} &= \left(1 + \frac{1}{n}\right)^b \cdot a_n \cdot q \\ &< \frac{1}{q} \cdot a_n \cdot q \\ &= a_n \end{align*} \]So we have shown that the sequence is monotonically decreasing and bounded below by 0 because \(q\) is positive. So by the monotone convergence theorem the sequence converges. The question remains what is the limit \(L\) of the sequence? For this we can use the trick that what happens in the begging of the sequence does not matter for the limit. So we use the following important property of limits:
\[\lim_{n \to \infty} a_n = \lim_{n \to \infty} a_{n+k} \text{ for all } k \in \mathbb{N} \]This results in the following:
\[\begin{align*} a_{n + 1} = (1 + \frac{1}{n})^b \cdot a_n \cdot q \\ \lim_{n \to \infty} a_{n + 1} &= \lim_{n \to \infty} (1 + \frac{1}{n})^b \cdot a_n \cdot q \\ L &= \lim_{n \to \infty} (1 + \frac{1}{n})^b \cdot \lim_{n \to \infty} a_n \cdot q \\ L &= 1 \cdot L \cdot q \\ L - qL &= 0 \\ L(1 - q) &= 0 \end{align*} \]so the statement corresponding to that the sequence converges only holds if \(q < 1\). If \(q = 1\) then the sequence is constant and converges to \(n^b\). If \(q > 1\) then the sequence diverges to infinity as the terms get larger and larger. The same can be shown for the case where \(q < 0\) in this case the sequence oscillates between positive and negative values but still converges to 0 if \(q > -1\) and diverges to infinity if \(q < -1\). If \(q = -1\) then the sequence just oscillates between the values \(n^b\) and \(-n^b\) and does not converge.
So we can summarize the results as follows:
- If \(|q| < 1\) then the sequence converges to 0.
- If \(|q| = 1\) then the sequence converges to \(n^b\) if \(q = 1\) and oscillates between \(n^b\) and \(-n^b\) if \(q = -1\).
- If \(|q| > 1\) then the sequence diverges to infinity if \(q > 1\) and diverges to negative infinity if \(q < -1\).
It turns out that this sequence is similar to a very important class of sequences. Specifically if we omit the \(n^b\) part and just look at sequence \(a_n = q^n\) then this is the so called geometric sequence. There is also an alternative definition of a geometric sequence that is more common in the literature. A geometric sequence is defined as:
\[(a_n)_{n \geq 1} = a_1 r^{n-1} \]where \(a_1\) is the first term of the sequence and \(r\) is the common ratio. To get from the first definition to the second we can simply set \(a_1 = n^b\) and \(r = q\). Then the actual first term is \(q\) and every subsequent term is the previous term multiplied by the common ratio \(r\).
If we observe the terms we can see that what is actually happening that each term is actually the previous term multiplied by the common ratio \(r\). So we can write the terms of the sequence as:
\[a_1, a_1 r, a_1 r^2, a_1 r^3, \ldots \]
If we think of the geometric sequence in terms of changing the area as illustrated we can understand the relation of the value of the ratio and how it affects the convergence a bit more intuitively. It also shows that geometric progression is exponential growth or exponential decline, as opposed to arithmetic progressions showing linear growth or linear decline.
However, probably the most important fact that comes from the sequence above is for the asymptotic growth of algorithms. If we pick \(q=\frac{1}{r} where \)r > 1$ then we know that this sequence converges to 0. When writing it out we get the following:
\[\lim_{n \to \infty} \frac{n^b}{r^n} = 0 \text{ for } r > 1 \]Which shows that the exponential growth of \(r^n\) is much larger than the polynomial growth of \(n^b\). This is a very important result as it shows that algorithms that take exponential time to run are much slower than algorithms that take polynomial time to run. This is a very important result in the analysis of algorithms and is often used to show that certain algorithms are not efficient.
Bernoulli’s Inequality
Bernoulli’s Inequality states that for all \(n \in \mathbb{N}\) and \(x \in \mathbb{R}\) the following holds:
\[(1+x)^n \geq 1+nx \]The inequality essentially says: if you repeatedly increase a quantity by a fixed proportion \(x\), the total increase after \(n\) iterations \((1+x)^n\) will always be at least as large as simply adding up \(n\) times the proportion \(x\) to the initial value provided \(x \geq -1\). In other words, compound growth (multiplicative) always outpaces or at least matches linear growth (additive), except in some degenerate or negative cases.
This can be proven by induction.
The base case for \(n=1\) is trivial as \((1+x)^1 = 1+x\). For the inductive step we assume that the inequality holds for some \(n=k\) and then show that it also holds for \(n=k+1\).
\[\begin{align*} (1+x)^{k+1} &= (1+x)^k \cdot (1+x) \\ &\geq (1+ kx) \cdot (1+x) \text{ by the inductive hypothesis} \\ &= 1 + x + kx + kx^2 \\ &= 1 + (k+1)x + kx^2 \\ &\geq 1 + (k+1)x \text{ because } kx^2 \geq 0 \text{ for } k \geq 0 \end{align*} \]Therefore the inequality holds for all \(n \in \mathbb{N}\) and \(x \in \mathbb{R}\).
Euler’s Number
There are some key constants in mathematics that always pop up in different areas of mathematics. One of these constants is the number pi, \(\pi = 3.14159...\), which is the ratio of the circumference of a circle to its diameter. Another important constant is Euler’s number, \(e = 2.71828...\), which is the base of the natural logarithm \(\ln(x)\). But where does this number come from?
One possible origin of Euler’s number is the compound interest formula. Imagine you are given a coin and you want to invest it in a bank that pays you interest. The bank pays you interest at a rate of 100% per year, so essentially you double your money every year. If you invest your coin for one year, you will have \((1+1)=2\) coins at the end of the year. The following year you will have \(4\) coins, then \(8\) coins and so on. This is a very simple example of exponential growth.
Now imagine that instead of waiting a whole year to get your interest, you get it twice a year so every 6 months. Then you will have \((1+\frac{1}{2})^2 = (1.5)^2 = 2.25\) coins at the end of the year. If you get your interest every month, then you will have \((1+\frac{1}{12})^{12} \approx 2.613\) coins at the end of the year. If you get your interest every day, then you will have \((1+\frac{1}{365})^{365} \approx 2.714\) coins at the end of the year.
This pattern continues and the more often you get your interest, the closer you get to a certain limit. This limit is actually Euler’s number \(e\). We can write this as:
\[\lim_{n \to \infty} \left(1 + \frac{1}{n}\right)^n = e \]So there is a natural limit to how much you can grow your money by compounding interest. The more often you compound your interest, the closer you get to this limit.
Limits of Recursive Sequences
We have seen that sequences can be defined recursively, meaning that each term is defined based on the previous terms. These sequences can also converge to a limit. To find the limit of a recursive sequence, we can use the same techniques as for non-recursive sequences with the monoton convergence theorem being the most important one as we can prove via induction that the sequence is bounded and monotonically increasing or decreasing.
Fibonacci Sequence
Babylonian/Heron’s Method
Heron’s method, also known as the Babylonian method, is a way to approximate square roots of real numbers. Using this method we can also approximate a real number by a rational number with any desired accuracy.
The idea of the method is that a square with an area of \(A\) has a side length of \(\sqrt A\). To approximate \(\sqrt a\) we start by creating a rectangle which we know the area of and then slowly adjust the sides to get closer to a square with the area of \(A\) and therefore the side length of \(\sqrt A\). Importantly, this method only works for \(A > 1\).
We start with a guess \(a_1\) and then calculate the next guess \(a_2\) by taking the average of the previous guess and the area divided by the previous guess.
\[a_2 = \frac{a_1 + \frac{A}{a_1}}{2} \]This can be repeated until the desired accuracy is reached:
\[a_{n+1} = \frac{a_n + \frac{A}{a_n}}{2} \]As we can see this method actually produces a sequence of approximations. However, rather then the sequence being some formula like \(a_n = n^2\) it is defined recursively. So the question is then does this sequence converge to the square root of \(A\) as \(n\) goes to infinity? This should obviously be the case as we are getting closer and closer to the square root of \(A\) with each iteration but we can also prove this formally.
This proof uses an important technique of finding the limit based on the knowledge of it existing. We will assume that the limit exists and then show that it is equal to \(\sqrt A\). To show that it exists we could use the monoton convergence theorem, by first showing that the sequence is bounded by 1 and then showing that it is monotonically decreasing.
Let \(L = \lim_{n \to \infty} a_n\). Then we can use the recursive definition of the sequence to write:
\[\begin{align*} \lim_{n \to \infty} a_{n+1} &= \lim_{n \to \infty} \frac{a_n + \frac{A}{a_n}}{2} \\ L &= \lim_{n \to \infty} \frac{1}{2} \left(\lim_{n \to \infty} a_n + \lim_{n \to \infty} \frac{A}{a_n}\right) \\ L &= \frac{1}{2} \left(L + \frac{A}{L}\right) \\ 2L &= L + \frac{A}{L} \\ L &= \frac{A}{L} \\ L^2 &= A \\ L &= \sqrt A \end{align*} \]So we have shown that the limit of the sequence is indeed \(\sqrt A\) and therefore the approximation as \(n\) goes to infinity converges to the square root of \(A\).
To approximate \(\sqrt{5}\) we start with a guess of \(a_1=5\). We then calculate the next approximation:
\[a_2 = \frac{5 + \frac{5}{5}}{2} = \frac{5 + 1}{2} = 3 \]If we then repeat this process we get for \(a_4 = 2.234\) which is a good approximation of \(\sqrt{5}=2.236\).
Limes Superior and Inferior
Using the monoton-convergence theorem we can perform a very important operation. If we are given a bounded sequence \(a_n\) we can define two new sequences \(b_n\) and \(c_n\) as follows for all \(n \geq 1\):
\[b_n = \inf\{a_k | k \geq n\} \text{ and } c_n = \sup\{a_k | k \geq n\} \]Because a_n is bounded we know that an infimum and supremum exist for all \(n \geq 1\). We also notice that for all \(n \geq 1\) the following holds:
\[b_{n+1} \subseteq b_n \text{ and } c_{n+1} \supseteq c_n \]So because \(a_n\) is bounded, the sequences \(b_n\) and \(c_n\) are also bounded. The sequence \(b_n\) is bounded below by the infimum of the sequence and the sequence \(c_n\) is bounded above by the supremum of the sequence.
Let’s look at the sequence \(a_n = (-1)^n (1 + \frac{1}{n})\). This sequence is bounded between -2 and 2 and does not converge as it oscillates between positive and negative values. However, we can define the two sequences \(b_n\) and \(c_n\) as follows:
\[\begin{align*} b_1 &= \inf\{a_k | k \geq 1\} = \inf\{-2, 1.5, -1.333, 1.25 \ldots\} = -2 \\ b_2 &= \inf\{a_k | k \geq 2\} = \inf\{1.5, -1.333, 1.25, -1.2 \ldots\} = -1.333 \\ b_3 &= \inf\{a_k | k \geq 3\} = \inf\{-1.333, 1.25, -1.2 \ldots\} = -1.333 \\ b_4 &= \inf\{a_k | k \geq 4\} = \inf\{1.25, -1.2 \ldots\} = -1.2 \\ \ldots \\ c_1 &= \sup\{a_k | k \geq 1\} = \sup\{-2, 1.5, -1.333, 1.25 \ldots\} = 1.5 \\ c_2 &= \sup\{a_k | k \geq 2\} = \sup\{1.5, -1.333, 1.25, -1.2 \ldots\} = 1.5 \\ c_3 &= \sup\{a_k | k \geq 3\} = \sup\{-1.333, 1.25, -1.2 \ldots\} = 1.25 \\ c_4 &= \sup\{a_k | k \geq 4\} = \sup\{1.25, -1.2, -1.2 \ldots\} = 1.25 \\ \ldots \end{align*} \]From the example we can see that the sequence \(b_n\) and \(c_n\) are monotonic. This comes from the following properties where if \(A \subseteq B\) and \(B\) is bounded from above then we have:
\[\sup A \leq \sup B \]and if \(B\) is bounded from below then we have:
\[\inf A \geq \inf B \]This makes sense because as values are taken away from the set \(A\) to create the set \(B\), the supremum can only decrease or stay the same and the infimum can only increase or stay the same.
In this case the set \(A\) corresponds to the sequence at time \(k+1\) and the set \(B\) corresponds to the sequence at time \(k\). So we can see that the infimum of the set at time \(k+1\) is always larger than or equal to the infimum of the set at time \(k\) and the supremum of the set at time \(k+1\) is always less than or equal to the supremum of the set at time \(k\). This means that the sequence \(b_n\) is monotonically decreasing and the sequence \(c_n\) is monotonically increasing.
\[\begin{align*} b_n &\geq b_{n+1} \\ c_n &\leq c_{n+1} \end{align*} \]Because they are both monotonic and bounded we can apply the monotone convergence theorem and say that they converge to a limit. We call these limits of these specially created sequences the Limes Superior and Limes Inferior of the original sequence. The Limes Superior is the limit of the sequence \(c_n\) and the Limes Inferior is the limit of the sequence \(b_n\). We can write this as:
\[\begin{align*} \limsup_{n \to \infty} a_n &= \lim_{n \to \infty} c_n \text{ Limes Superior} \\ \liminf_{n \to \infty} a_n &= \lim_{n \to \infty} b_n \text{ Limes Inferior} \end{align*} \]We can interpret the Limes Superior and Limes Inferior as the largest and smallest limit points of the sequence. So in a way as \(n\) goes to infinity the Limes Superior is like an upper bound that the sequence approaches and the Limes Inferior is like a lower bound that the sequence approaches.
Because we also know that the infimum is always less than or equal to the supremum we can also say that all terms of the \(b_n \leq c_n\) and therefore the limit of the sequence \(b_n\) is less than or equal to the limit of the sequence \(c_n\):
\[\liminf_{n \to \infty} a_n \leq \limsup_{n \to \infty} a_n \]We can also use the Limes Superior and Limes Inferior to determine if a sequence converges or diverges. First let’s just look at a bounded sequence. We have already seen that we can create two sequences \(b_n\) and \(c_n\) that are monotonic and bounded and therefore converge to a limit. Using these two sequences we can define the Limes Superior and Limes Inferior of the original sequence which are like upper and lower bounds of the sequence but as \(n\) goes to infinity. So if the Limes Superior and Limes Inferior converge to the same limit, then it is as if these bounds are slowly squeezing the sequence together. I.e they are both getting closer to a value, sounds like a limit.
So we can say that if the Limes Superior and Limes Inferior of a bounded sequence converge to the same limit, then the original sequence also converges. That the sequence is bounded is important as otherwise the Limes Superior and Limes Inferior could diverge to infinity and would be the same but the original sequence would not converge. So we can say that:
\[\text{If } \limsup_{n \to \infty} a_n = \liminf_{n \to \infty} a_n \text{ and } a_n \text{ is bounded then } a_n \text{ converges} \]We can also prove this. Let’s assume that the Limes Superior and Limes Inferior converge to the same limit \(L\). Then we know that \(b_n\) is monotonically increasing and converges to \(L\) and \(c_n\) is monotonically decreasing and converges to \(L\). So we can say that:
\[L - \epsilon < b_n \leq a_n \leq c_n < L + \epsilon \text{ for all } n \geq N_{\epsilon} \]This would then imply that:
\[L - \epsilon < a_n < L + \epsilon \equiv |a_n - L| < \epsilon \text{ for all } n \geq N_{\epsilon} \]We can also show the other way around. If the sequence converges to a limit \(L\) then we know that for all \(\epsilon > 0\) there exists an index \(N_{\epsilon}\) such that for all \(n \geq N_{\epsilon}\) the following holds:
\[|a_n - L| < \epsilon \]So eventually all terms are within the epsilon neighborhood around \(L\), \((L - \epsilon, L + \epsilon)\). This means that the terms of the sequence are also within the epsilon neighborhood around the supremum and infimum.
Let’s look at the sequence \(a_n = (-1)^n + \frac{1}{n}\). This sequence is bounded between -1 and 2 so we have:
\[-1 \leq a_n \leq 2 \]Because the sequence is bounded we can create the two sequences \(b_n\) and \(c_n\) as follows:
\[\begin{align*} b_n &= \inf\{a_k | k \geq n\} = \inf\{a_n, a_{n+1}, a_{n+2}, \ldots\} \\ b_1 &= \inf\{0, 1 + \frac{1}{2}, -1 + \frac{1}{3}, 1 + \frac{1}{4}, \ldots\} = -1 \\ b_2 &= \inf\{1 + \frac{1}{2}, -1 + \frac{1}{3}, 1 + \frac{1}{4}, \ldots\} = -1 \\ b_{2n} &= \inf\{1 + \frac{1}{2n}, -1 + \frac{1}{2n+1}, 1 + \frac{1}{2n+2}, \ldots\} = -1 + \frac{1}{2n+1} = -1\\ b_{2n+1} &= \inf\{-1 + \frac{1}{2n+1}, 1 + \frac{1}{2n+2}, -1 + \frac{1}{2n+3}, \ldots\} = -1 + \frac{1}{2n+1} = -1\\ \ldots \\ c_n &= \sup\{a_k | k \geq n\} = \sup\{a_n, a_{n+1}, a_{n+2}, \ldots\} \\ c_1 &= \sup\{0, 1 + \frac{1}{2}, -1 + \frac{1}{3}, 1 + \frac{1}{4}, \ldots\} = 1 + \frac{1}{2} \\ c_2 &= \sup\{1 + \frac{1}{2}, -1 + \frac{1}{3}, 1 + \frac{1}{4}, \ldots\} = 1 + \frac{1}{2} \\ c_{2n} &= \sup\{1 + \frac{1}{2n}, -1 + \frac{1}{2n+1}, 1 + \frac{1}{2n+2}, \ldots\} = 1 + \frac{1}{2n} \\ c_{2n+1} &= \sup\{-1 + \frac{1}{2n+1}, 1 + \frac{1}{2n+2}, -1 + \frac{1}{2n+3}, \ldots\} = 1 + \frac{1}{2n+2} \\ c_{n} &= \{1 + \frac{1}{2}, 1 + \frac{1}{2}, \ldots, 1 + \frac{1}{2n}, 1 + \frac{1}{2n+2}, \ldots\} \end{align*} \]So we can see that we get the following limits:
\[\liminf_{n \to \infty} a_n = -1 \text{ and } \limsup_{n \to \infty} a_n = 1 \]And because the Limes Superior and Limes Inferior do not converge to the same limit, we can say that the orginal sequence \(a_n\) does not converge.
From the exercise what is limes superior and limes inferior of the sequence \(a_n = 2^n(1 + (-1)^n) + 1\)?
Then also limes super and inferior if b_n = a_n+1/a_n
Cauchy Criterion
We have seen a few ways now how to calculate the limit of a sequence or determine if a sequence converges based on certain properties that the sequence has, such as being bounded and monotonic. However, there is another way to determine if a sequence converges or diverges. This is called the Cauchy criterion.
Previously we looked to see if the Limes Superior and Limes Inferior of a sequence converge to the same limit. Cauchy’s idea is similar to this but instead of looking at the Limes Superior and Limes Inferior we look at the distance between two terms of the sequence. The idea is that if the terms of the sequence get closer and closer together, then they must converge to a limit.
This is what the Cauchy criterion states. A sequence is convergent if it is a so called Cauchy sequence or the sequence is Cauchy and a sequence is Cauchy if the following holds:
\[\forall \epsilon > 0 \exists N_{\epsilon} \in \mathbb{N} \text{ such that } \forall n, m \geq N_{\epsilon} \text{ we have } |a_n - a_m| < \epsilon \]So if we can find an index \(N_{\epsilon}\) such that for all terms after this index the distance between any two terms is less than \(\epsilon\), then the sequence converges. So this leads to the following statements:
- \((a_n)_{n \geq 1} \text{ is Cauchy} \implies \text{ the sequence converges}\)
- \(\text{the sequence converges} \implies (a_n)_{n \geq 1} \text{ is Cauchy}\)
- Therefore a sequence is Cauchy if and only if it converges so \((a_n)_{n \geq 1} \text{ is Cauchy} \iff \text{ the sequence converges}\).
This also means that we can use the reverse to show that a sequence diverges, so \((a_n)_{n \geq 1} \text{ is not Cauchy} \implies \text{ the sequence diverges}\) and \(\text{the sequence diverges} \implies (a_n)_{n \geq 1} \text{ is not Cauchy}\).
Lastly a further important property of Cauchy sequences is that they are bounded. This means that if a sequence is Cauchy, then it is also bounded. However, the reverse is not true so just because a sequence is bounded does not mean that it is Cauchy and therefore converges. This makes sense as otherwise the monotone convergence theorem would be unnecessarily complicated. But why are Cauchy sequences bounded?
We can prove that the cauchy criterion implies that the sequence converges. Let’s assume that the sequence converges, then we know that there exists a limit \(L\) such that for all \(\epsilon > 0\) there exists an index \(N_{\epsilon}\) such that for all \(n \geq N_{\epsilon}\) the following holds:
\[|a_n - L| < \epsilon \]Now because it counts for all \(\epsilon > 0\) we can also manipulate and use cauchy to get the following:
\[\begin{align*} |a_n - L| < \epsilon \\ |a_n - L| < \frac{\epsilon}{2} \\ |a_m - a_n| &= |a_m - L + L - a_n| \\ &\leq |a_m - L| + |L - a_n| \text{ by the triangle inequality} \\ &< \frac{\epsilon}{2} + \frac{\epsilon}{2} \\ &= \epsilon \end{align*} \]As an example let’s look at the harmonic sequence \(a_n = \frac{1}{n}\). We know that this sequence converges to 0. But we can also use the Cauchy criterion to show that it converges. Let’s assume that we have a sequence \(a_n\) and we want to show that it is Cauchy. We can do this by showing that the distance between two terms of the sequence is less than \(\epsilon\).
\[\begin{align*} |a_n - a_m| < \epsilon \\ \frac{1}{n} - \frac{1}{m} < \epsilon \\ \frac{1}{k} < \epsilon \end{align*} \]So depending on how we set the epsilon we can find an index \(N_{\epsilon}\) such that for all terms after this index the distance between any two terms is less than \(\epsilon\).
Cauchy-Cantor Theorem
Weird stuff with intervals that can then be used to show that real numbers are uncountable.
Bolzano-Weierstrass Theorem
The Bolzano-Weierstrass theorem is a very important theorem in real analysis like the monotone convergence theorem and the squeeze theorem. It states that every bounded sequence of real numbers has a convergent subsequence. In other words, if you have a sequence that does not “escape” to infinity (is bounded), then there exists a subsequence that converges to some real number.
First let’s define what a subsequence is. A subsequence of a sequence \(a_n\) is a sequence \(b_k\) that is formed by taking some of the terms of the original sequence \(a_n\) and keeping the order of the terms. Or by removing some of the terms of the original sequence \(a_n\) while keeping the order of the remaining terms. Importantly with both approaches the resulting subsequence must still be infinite. So we can say a subsequence \(b_n\) is a function just like the original sequence \(a_n\) so \(b_n: N \to R\) but where there exists a strictly increasing function \(k: N \to N\) such that:
\[b_n = a_n \circ k \text{so} b_n = a_{k(n)} \text{ for all } n \in N \]If the sequence \(a_n = n\) so we have \((1, 2, 3, 4, \ldots)\) then we can create the subsequence \(b_n = (2, 4, 6, 8, \ldots)\) by taking every second term of the original sequence. However, the subsequence \(c_n = (4,2,6,8,\ldots)\) is not a valid subsequence as the order of the terms is not preserved. So we can only take terms from the original sequence and keep the order of the terms.
Suppose \(a_n = (-1)^n + \frac{1}{n}\). If we define \(n_k = 2k\) (i.e., take all the even indices), then the subsequence is \(b_k = a_{2k} = 1 + \frac{1}{2k}\), which converges to \(1\) as \(k \to \infty\). If we take \(n_k = 2k+1\) (odd indices), then \(c_k = a_{2k+1} = -1 + \frac{1}{2k+1}\), which converges to \(-1\). So the sequence has two subsequential limits, \(1\) and \(-1\).
Suppose \((a_n)\) is a bounded sequence. Thus, there exist real numbers \(m, M\) such that \(m \leq a_n \leq M\) for all \(n\). We construct a nested sequence of closed intervals \(I_k\) containing infinitely many terms of the sequence and with lengths tending to \(0\). We do this as follows:
- We start with \(I_1 = [m, M]\).
- We then divide \(I_1\) in half. At least one half contains infinitely many \(a_n\); call it \(I_2\).
- Repeat this process: bisect \(I_k\) and select the subinterval \(I_{k+1}\) that contains infinitely many \(a_n\).
This gives a nested sequence of intervals with lengths going to zero:
\[I_1 \supseteq I_2 \supseteq \dots \]Then under the assumption of nesting, the intersection of these intervals is non-empty. Thus there is a number \(L\) that is the limit of a convergent subsequence of \((a_n)\) by proving it is an accumulation point of the sequence. (complicated)
If a sequence \(a_n\) is bounded, then we can define the Limes Superior and Limes Inferior of the sequence as we did before. If we then combine this with bolzano weierstrass where we know that every bounded sequence has a convergent subsequence \(b_n\), then we can say that the limit of this subsequence is contained in the interval \([\liminf a_n, \limsup a_n]\):
\[\liminf_{n \to \infty} a_n \leq \lim b_n \leq \limsup_{n \to \infty} a_n \]Subsequence Criterion
The subsequence criterion states a fundamental property of limits. If a sequence \(a_n\) converges to a limit \(L\), then every subsequence \(b_n\) of \(a_n\) also converges to the same limit \(L\). This property is important because it allows us to study sequences by studying their subsequences. In particular, it tells us that convergence is a “global” property. If the whole sequence converges, then any infinite “sample” you take from it, as long as you keep the order, will also converge to the same value.
This is a bit weird but basically by definition a sequence converges to a limit \(L\) if for every \(\epsilon > 0\) there exists an index \(N_{\epsilon}\) such that for all \(n \geq N_{\epsilon}\) we have \(|a_n - L| < \epsilon\).
Now the subsequence \(b_n\) is defined as \(b_n = a_{k(n)}\) where \(k(n)\) is a strictly increasing function. This means that for every \(n \geq N_{\epsilon}\), we have \(k(n) \geq N_{\epsilon}\) at some point. So we can say that for all \(n \geq N_{\epsilon}\) we have:
\[|b_n - L| = |a_{k(n)} - L| < \epsilon \]Suppose \(a_n = \frac{1}{n}\), which converges to \(0\) as \(n \to \infty\). Let’s construct a subsequence \(b_k = a_{2k} = \frac{1}{2k}\). For this subsequence it then follows that:
\[\lim_{k \to \infty} b_k = \lim_{k \to \infty} \frac{1}{2k} = 0 \]The same holds for any other subsequence of \(a_n\), such as \(c_k = a_{k^2} = \frac{1}{k^2}\), which also converges to \(0\):
\[\lim_{k \to \infty} c_k = \lim_{k \to \infty} \frac{1}{k^2} = 0 \]No matter how we select the subsequence (as long as it is infinite and preserves the order), the subsequence always converges to \(0\).
Another way to prove this is by contradiction. Suppose we have a sequence \(a_n\) that converges to a limit \(L\) and a subsequence \(b_n\) that doesn’t converge to \(L\). Then there exists an \(\epsilon > 0\) such that for all \(N_{\epsilon}\) there exists an \(n \geq N_{\epsilon}\) such that \(|b_n - L| \geq \epsilon\). But this contradicts the definition of convergence of the original sequence \(a_n\) as for all \(n \geq N_{\epsilon}\) we have \(|a_n - L| < \epsilon\) and the subsequence \(b_n\) is just a sample of the original sequence \(a_n\). So we can conclude that if a sequence converges to a limit \(L\), then every subsequence also converges to the same limit \(L\).
Suppose we have the following sequence:
\[a_n = \begin{cases} 1 + \sqrt{\frac{k}{12k + 1}} & \text{if } n = 3k + 1 \text{ for } k \in \mathbb{N} \\ \frac{5k^3 + k}{k^3+1} & \text{if } n = 3k + 2 \text{ for } k \in \mathbb{N} \\ \frac{(-1)^k}{k} & \text{if } n = 3k + 3 \text{ for } k \in \mathbb{N} \end{cases} \]First let’s look at the subsequences and how they behave. Starting with the first subsequence \(b_n = a_{3k+1}\), we have:
\[\begin{align*} b_n &= 1 + \sqrt{\frac{k}{12k + 1}} \\ \lim_{k \to \infty} 1 + \sqrt{\frac{k}{12k + 1}} &= 1 + \sqrt{\frac{1}{12}} \end{align*} \]Next, we look at the second subsequence \(c_n = a_{3k+2}\):
\[\begin{align*} c_n &= \frac{5k^3 + k}{k^3+1} \\ \lim_{k \to \infty} \frac{5k^3 + k}{k^3+1} &= \frac{5 + \frac{1}{k^2}}{1 + \frac{1}{k^3}} = 5 \end{align*} \]Finally, we look at the third subsequence \(d_n = a_{3k+3}\):
\[\begin{align*} d_n &= \frac{(-1)^k}{k} \\ \lim_{k \to \infty} d_n &= \lim_{k \to \infty} \frac{(-1)^k}{k} = 0 \end{align*} \]Because the subsequences converge to different limits, we can conclude that the original sequence \(a_n\) does not converge. This is because if a sequence converges, then all its subsequences must converge to the same limit.
What about the limes superior and limes inferior? To see if these exist we must first check if the sequence is bounded. Because the highest limit of the subsequences is \(5\) we can conclude that the sequence is bounded above by \(5\). We can also quickly see that the first two subsequences are always positive and that the third subsequence can be negative with the lowest value being \(-1\). So we can say that the sequence is bounded below by \(-1\). So we can conclude that the sequence is bounded and therefore the Limes Superior and Limes Inferior exist.
From the above it then follows that if a sequence converges to \(L\), then the odd indexed subsequence converges to \(L\) and the even indexed subsequence converges to \(L\). This is because both subsequences are just a sample of the original sequence and therefore must converge to the same limit.
We can also use this vice versa. If we have a sequence \(a_n\) and we know that both the odd indexed subsequence \(b_n\) and the even indexed subsequence \(c_n\) converge to the same limit \(L\), then we can say that the original sequence \(a_n\) converges to \(L\). The intuition behind this is that if both subsequences converge to the same limit, then the original sequence must also converge to that limit as we have covered all the terms of the original sequence. We can also generalize this to any subsequence. If we have a sequence \(a_n\) and we know that every subsequence \(b_n\) converges to the same limit \(L\), then we can say that the original sequence \(a_n\) converges to \(L\).
Suppose we have the following sequence:
\[a_n = \frac{1}{n} + (-1)^n \cdot \frac{1}{n} \]Let’s examine its even- and odd-indexed subsequences.
- Even-indexed subsequence: For \(n = 2k\) as \(k \to \infty\), \(b_k \to 0\).
- Odd-indexed subsequence: For \(n = 2k+1\) as \(k \to \infty\), \(c_k \to 0\).
Both the even- and odd-indexed subsequences converge to \(0\). Therefore, by the criterion, the original sequence \((a_n)\) also converges to \(0\).
Let’s check this directly:
\[\begin{align*} \lim_{n \to \infty} a_n &= \lim_{n \to \infty} \left(\frac{1}{n} + (-1)^n \cdot \frac{1}{n}\right) \\ \begin{cases} \frac{2}{n} & \text{if $n$ is even} \\ 0 & \text{if $n$ is odd} \end{cases} \end{align*} \]As \(n \to \infty\), \(\frac{2}{n} \to 0\) and the odd terms are already \(0\). Thus, \(\lim_{n \to \infty} a_n = 0\).
We know that the sequence \(a_n = (1 + \frac{1}{n})^n\) converges to \(e\). If we then look at the subsequence \(b_n = a_{2n} = (1 + \frac{1}{2n})^{2n}\), then using this theorem we also know that this subsequence converges to \(e\). The same holds for the subsequence \(c_n = a_{n^2} = (1 + \frac{1}{n^2})^{n^2}\), which also converges to \(e\) etc.
Reordering of Sequences
We have seen that if a sequence converges to a limit \(L\), then every subsequence converges to the same limit \(L\). A similar idea is to reorder a sequence rather then taking a subsequence. So in other we can show that if \(a_n\) converges to \(L\), then any permutation \(\sigma(n)\), i.e. a bijective mapping of the natural numbers to itself, of the sequence \(a_n\) also converges to \(L\). Formally if \(\sigma: \mathbb{N} \to \mathbb{N}\) is a bijection and \(a_n\) converges to \(L\), then we can say that:
\[\lim_{n \to \infty} a_{\sigma(n)} = L \]Let \((a_n)\) be a sequence converging to \(L\), and let \(\sigma: \mathbb{N} \to \mathbb{N}\) be a bijection. Then \((a_{\sigma(n)})\) also converges to \(L\). Then let \(\epsilon > 0\). Since \(a_n \to L\), there exists \(N \in \mathbb{N}\) such that for all \(n \geq N\), \(|a_n - L| < \epsilon\).
Because \(\sigma\) is a bijection, only finitely many \(n\) satisfy \(\sigma(n) < N\). Thus, there exists \(M \in \mathbb{N}\) such that for all \(n \geq M\), \(\sigma(n) \geq N\). For such \(n\):
\[|a_{\sigma(n)} - L| < \epsilon. \]Thus, \(a_{\sigma(n)} \to L\).
Vector Sequences
So far we have looked at sequences of real numbers, often called real sequences. However, we can also look at sequences where the elements are vectors, these are called vector sequences. More formally we can define a vector sequence in \(\mathbb{R}^d\) as:
\[a: N \to R^d, n \mapsto a_n = (a_{n1}, a_{n2}, \ldots, a_{nd}) \text{ with } a_{ni} \in R \]We can define the limit of a vector sequence in a similar way as we did for real sequences, we just need to replace the absolute value with the norm of the vector. So we can say that a vector sequence converges if there exists a vector \(L \in \mathbb{R}^d\) such that:
\[\forall \epsilon > 0 \exists N_{\epsilon} \in \mathbb{N} \text{ such that } \forall n \geq N_{\epsilon} \text{ we have } ||a_n - L|| < \epsilon \]Just like with real sequences, this limit is unique and is written as:
\[\lim_{n \to \infty} a_n = L \]At first you might think that limits of vectors could be rather complicated as we are now working with multiple dimensions. However, it turns out that the limit of a vector sequence is rather simple. The limit of a vector sequence is simply the limit along each dimension or coordinate/component.
If we have the vector \(L=(l_1, l_2, \ldots, l_d)\) and a vector sequence \(a_n\), think of the vector sequence as a matrix with \(d\) rows and \(n\) columns, then if each row \(i\) is a sequence itself, it’ll converge to the limit \(l_i\) of that sequence. So the following two statements are equivalent:
- The vector sequence \(a_n\) converges to the vector \(L\), \(\lim_{n \to \infty} a_n = L\).
- \(\lim_{n \to \infty} a_{n,i} = l_i\) for all \(i=1,2,\ldots,d\).
She has a proof that these two statements are equivalent. Seems weird and complicated,
Let’s define a vector sequence as follows:
\[a_n = (\frac{1}{n}, 1 + \frac{1}{n}, (1 + \frac{1}{n})^2) \text{ with } n \geq 1 \]If we now look at the first component of each term of the sequence we get:
\[(a_{n,1})_{n \geq 1} = (\frac{1}{n})_{n \geq 1} = (1, \frac{1}{2}, \frac{1}{3}, \ldots) \]We already know this sequence as the harmonic sequence and we know that it converges to 0. The same holds for the sequence of the second components and the third component. So we can say that the vector sequence converges to the vector \(L=(0, 1, 1)\) as the limit of the vector sequence is simply the limit of each component. So we can write:
\[\lim_{n \to \infty} a_n = (\lim_{n \to \infty} a_{n,1}, \lim_{n \to \infty} a_{n,2}, \lim_{n \to \infty} a_{n,3}) = (0, 1, e) \]We can also look at a vector sequence that does not converge. For example let’s look at the following sequence:
\[a_n = (\frac{1}{n}, (-1)^n, n) \text{ with } n \geq 1 \]This sequence does not converge as the second component oscillates between -1 and 1 and the third component diverges to infinity.
We already know that for real convergent sequences we can perform certain operations on the sequences and the limits of these sequences. The same holds for vector sequences. We can perform the same operations on vector sequences as we did for real sequences. So for the convergent vector sequences \(a_n\) and \(b_n\) we can say that:
\[\begin{align*} \lim_{n \to \infty} (a_n \pm b_n) &= \lim_{n \to \infty} a_n \pm \lim_{n \to \infty} b_n \\ \lim_{n \to \infty} (c a_n) &= c \lim_{n \to \infty} a_n \end{align*} \]Where \(c\) is a constant. This is rather intuitive as if each of the components of the vector converges to a limit, then the sum of the vector sequences is as if we would shift the limit of the vector sequence by the limit of the other vector sequence. The same holds for the product of a constant and a vector sequence.
Bounded Vector Sequences
For real sequences we were able to say that a sequence is bounded if it is bounded above and below. So for some upper bound \(u\) and lower bound \(l\) we had for a bounded real sequence:
\[a_n \in [l, u] \text{ for all } n \in \mathbb{N} \]In other words, no term ever became infinitely large or small. For vector sequences we can define the same concept. A vector sequence is bounded if there exists a vector \(R \in \mathbb{R}^d\) such that:
\[||a_n|| \leq R \text{ for all } n \in \mathbb{N} \]An example of a bounded vector sequence is the following:
\[a_n = (\frac{1}{n}, \sin(n)) \text{ with } n \geq 1 \]Intuitively As \(n\) goes to infinity the first component converges to 0 and the second component oscillates between -1 and 1. So we can say that the vector sequence is bounded. We can also show this by calculating the norm of the vector sequence:
\[||a_n|| = \sqrt{(\frac{1}{n})^2 + (\sin(n))^2} \leq \sqrt{(\frac{1}{n})^2 + 1} \leq \sqrt{2} \text{ for all } n \geq 1 \]An example of an unbounded vector sequence is the following:
\[a_n = (n, (-1)^n) \text{ with } n \geq 1 \]Again intuitively we can see that the first component diverges to infinity and the second component oscillates between -1 and 1. So we would say that the vector sequence is unbounded. We can also show this by calculating the norm of the vector sequence:
\[||a_n|| = \sqrt{n^2 + (-1)^2} = \sqrt{n^2 + 1} \geq n \mapsto \infty \text{ as } n \to \infty \]Because we know that vector sequences can be bounded it mean can also use the Cauchy criterion and the Bolzano-Weierstrass theorem to show that a vector sequence converges. However, we can not use the monotone convergence theorem as we can not just simply define an order on the vector space. So we can not say that a vector sequence is monotonic.
Complex Sequences
Complex sequences are similar to vector sequences but with complex numbers. What are the rules?
She showed:
- \(\lim_{n \to \infty} z_n = z\) then \(\lim_{n \to \infty} \overline{z_n} = \overline{z}\)
- \(\lim_{n \to \infty} z_n = z\) then \(\lim_{n \to \infty} |z_n| = |z|\)
- \(\lim_{n \to \infty} (z_n + w_n) = z + w\) if \(z_n \to z\) and \(w_n \to w\)
- \(\lim_{n \to \infty} (z_n * w_n) = z * w\) if \(z_n \to z\) and \(w_n \to w\)
- \(\lim_{n \to \infty} (z_n / w_n) = z / w\) if \(z_n \to z\) and \(w_n \to w\) and \(w \neq 0\) and \(w_n \neq 0\) for all \(n \geq N_{\epsilon}\)
Example:
\[\lim_{n \to \infty} (\frac{n^2 + 2}{n^3 + 1} + i \frac{n^3 + 2n + 1}{n^3 + n + 1}) = 0 + i = i \]