Theorem 3.5.1 Recursive Limits as Fixed Points
If a sequence is defined recursively with a continuous projection function \(f\text{,}\) \(x_{n}=f(x_{n-1})\text{,}\) and \(x_n\) has a limit, then the limit must be a fixed point of \(f\text{.}\)
The limit of a sequence describes its end behavior. Some sequences converge to a particular value, meaning that the values of the sequence keep getting closer and closer to that value. Other sequences grow without bound. Still other sequences alternate between values or behave chaotically. Limits allow us to establish some mathematical language that characterizes some of these behaviors.
The objectives for this section are as follows. We will focus on what it means for a sequence to have a limit. Much of our intuition will focus on graphs and tables. As we do this, we will learn about limits of sequences defined recursively in terms of fixed points of the projection function. We will then discuss limit arithmetic involving infinity and how this can be used to find limits of some sequences defined explicitly.
Consider the sequence defined recursively by \(x_{n} = 0.8 x_{n-1} + 1\) and initial value \(x_0 = 1\text{.}\) The next ten values (to the nearest ten-thousandth) are shown in a table and the first twenty values are illustrated in a graph.
\(n\) | \(x_n\) |
0 | 1 |
1 | 1.8 |
2 | 2.44 |
3 | 2.952 |
4 | 3.3616 |
5 | 3.68928 |
6 | 3.951424 |
7 | 4.161139 |
8 | 4.328911 |
9 | 4.463129 |
10 | 4.570503 |
The graph illustrates that the sequence \(x\) is increasing and concave down. It appears that the values of the sequence might be leveling off at some value. A cobweb diagram, shown below, suggests that this sequence has values that are converging to a fixed point of the projection function \(f(x) = 0.8x+1\text{,}\) where \(f(x)=x\text{.}\)
The fixed point corresponds to an equilibrium of the recursively defined sequence. We find the equilibrium value by solving the fixed point equation.
Now, let us compare the decimal approximations to the sequence with higher index values with the equilibrium.
\(n\) | \(x_n\) |
20 | 4.953883140 |
25 | 4.984888427 |
30 | 4.995048240 |
35 | 4.998377407 |
40 | 4.999468309 |
45 | 4.999825775 |
50 | 4.999942910 |
55 | 4.999981293 |
60 | 4.999993870 |
Notice that the values for the sequence have decimal approximations that are converging to the equilibrium value \(x=5\text{.}\) The greater the index value, the closer the sequence value is to equilibrium. Consequently, we say that our sequence has a limit of 5 and write \(x_n \to 5\) or
Next consider another example—a recursive sequence \(x\) defined by a recurrence relation \(x_{n} = 1.2 x_n - 1\) and initial value \(x_0=4\text{.}\) The projection function \(f(x) = 1.2x-1\) has the same fixed point \(x=5\) because
\(n\) | \(x_n\) |
0 | 4 |
1 | 3.8 |
2 | 3.56 |
3 | 3.272 |
4 | 2.9264 |
5 | 2.51168 |
6 | 2.014016 |
7 | 1.416819 |
8 | 0.700183 |
9 | -0.1597804 |
10 | -1.191736 |
However, this time the sequence is decreasing and concave down, moving away from the equilibrium value. Instead, the value of the sequence is becoming more and more negative. The cobweb diagram illustrates that this will continue forever. For a sequence like this, we say \(x_n \to -\infty\) or
For the same recursive definition \(x_{n} = 1.2x_{n-1}-1\) with an initial value above the equilibrium, \(x_0=6\text{,}\) the sequence is increasing and concave up, shown below. The values become more and more positive. For a sequence like this, we say \(x_n \to \infty\) or
\(n\) | \(x_n\) |
0 | 6 |
1 | 6.2 |
2 | 6.44 |
3 | 6.728 |
4 | 7.0736 |
5 | 7.48832 |
6 | 7.985984 |
7 | 8.583181 |
8 | 9.299817 |
9 | 10.15978 |
10 | 11.19174 |
We have seen that a recursive sequence sometimes converges to a fixed point and sometimes it diverges away from a fixed point. We might wonder if a recursive sequence can have a limit that is not a fixed point of the projection function. The answer is no, so long as the projection function is continuous.
If a sequence is defined recursively with a continuous projection function \(f\text{,}\) \(x_{n}=f(x_{n-1})\text{,}\) and \(x_n\) has a limit, then the limit must be a fixed point of \(f\text{.}\)
We have to wait for a definition of continuity before this can be proved.
Note some things that this theorem does not guarantee. First, just because a function has a fixed point does not mean that it will be a limit. (The sequence might not have a limit.) Second, the projection function needs to be continuous. If a function is not continuous, then it is possible to have a limit that is not a fixed point. Fortunately, functions defined by simple algebraic formulas will be continuous everywhere they are defined. For any continuous projection functions, the only limits will be fixed points. Finally, if the sequence is not defined recursively, then we will need other methods to find the limits.
In practice, we first observe that a sequence defined recursively has a limit (perhaps through a graph or a table). If we find all of the fixed points for the projection function, then we can determine which of those is the appropriate limit. The limit may depend on the initial value of the sequence, so we compare approximate values from the table with the approximate (decimal) values of the fixed points.
We consider some additional examples. As you attempt the examples or exercises, take advantage of technology to generate tables and graphs. Refer back to Section 2.3 for guidance as needed.
Use a table and a graph of the sequence defined explicitly as
to estimate the limit of \(x_n\text{.}\)
The explicit definition of the sequence allows us to create a table. Because we are looking for the decimal approximation to converge, we need to show quite a few decimal places. Once the table is generated, we can create a plot.
\(n\) | \(x_n\) |
\(0\) | \(1.0\) |
\(1\) | \(0.714285714286\) |
\(2\) | \(0.538461538462\) |
\(3\) | \(0.44\) |
\(4\) | \(0.387755102041\) |
\(5\) | \(0.360824742268\) |
\(6\) | \(0.347150259067\) |
\(7\) | \(0.34025974026\) |
\(8\) | \(0.336801040312\) |
\(9\) | \(0.335068314899\) |
\(10\) | \(0.334201106411\) |
\(11\) | \(0.33376729048\) |
\(12\) | \(0.333550329563\) |
\(13\) | \(0.333441835863\) |
\(14\) | \(0.333387585702\) |
\(15\) | \(0.333360459793\) |
The plot for the sequence shows that the sequence appears to be leveling off. Looking at the table, we see that more and more of the digits are converging to a 3. If this pattern is real and continues, the limiting value would be the repeating decimal \(0.3333\ldots\) which is the rational number \(\frac{1}{3}\text{.}\) We would say that this sequence has a limit \(x_n \to \frac{1}{3}\text{:}\)
Use a table and a graph of the sequence defined explicitly as
to estimate the limit of \(u_n\text{.}\)
We generate a table of sequence values and plot the results.
\(n\) | \(u_n\) |
\(0\) | \(1.5\) |
\(1\) | \(0.75\) |
\(2\) | \(1.28125\) |
\(3\) | \(0.6650390625\) |
\(4\) | \(1.38623809814\) |
\(5\) | \(0.573392406106\) |
\(6\) | \(1.45491835196\) |
\(7\) | \(0.526711160622\) |
\(8\) | \(1.48458696224\) |
\(9\) | \(0.508720709959\) |
\(10\) | \(1.49513858939\) |
\(11\) | \(0.502678999959\) |
\(12\) | \(1.4985371216\) |
\(13\) | \(0.500792876146\) |
\(14\) | \(1.49957292337\) |
\(15\) | \(0.500228832948\) |
Notice that for this sequence, the graph appears to level off to two different values. However, this is because the sequence is actually approaching two alternating values. This is an example of approaching a repeating pattern rather than a value, most easily seen in the table. As we look further down the table, the odd index values correspond to a sequence value that is getting closer to 0.5 while the even index values correspond to a sequence value that is getting closer to 1.5.
This sequence does not have a limit because the sequence is not approaching a single value. We say \(\displaystyle \lim_{n \to \infty} x_n\) does not exist.
Use a table and a graph of the sequence defined recursively by
and an initial value \(z_0 = 1\) to estimate the limit of \(z_n\text{.}\)
We can use the recursive definition and a computer to generate approximate values and then graph the sequence.
\(n\) | \(z_n\) |
\(0\) | \(1.00000000000000\) |
\(1\) | \(2.00000000000000\) |
\(2\) | \(2.60000000000000\) |
\(3\) | \(2.28800000000000\) |
\(4\) | \(2.51313920000000\) |
\(5\) | \(2.36436779299635\) |
\(6\) | \(2.47062849869924\) |
\(7\) | \(2.39789332147854\) |
\(8\) | \(2.44938730115809\) |
\(9\) | \(2.41369700737469\) |
\(10\) | \(2.43882864952499\) |
\(11\) | \(2.42131772649675\) |
\(12\) | \(2.43361218868805\) |
\(13\) | \(2.42502511000601\) |
\(14\) | \(2.43104504810447\) |
\(15\) | \(2.42683561174279\) |
\(16\) | \(2.42978439120944\) |
\(17\) | \(2.42772132482997\) |
\(18\) | \(2.42916599531699\) |
\(19\) | \(2.42815498439281\) |
\(20\) | \(2.42886281809844\) |
Graphically, you should see that the plot shows the sequence values appears to level off to a single value. However, the graph also shows that the values are alternately above and below that limit. We look in the table to determine the limiting value, but it is not obvious from the table what the limiting value should be. Because the values are alternately above and then below whatever the limit should be, we can conclude that the limit must be between the last two values listed.
The limit is approximately 2.428 but we do not know the next decimal place without computing more values in the sequence. With additional computation (not shown), we find \(z_{39} = 2.42857109636261\) and \(z_{40} = 2.42857166111753\) so that our approximation for the limit (a value between \(z_{39}\) and \(z_{40}\)) can be estimated as close to 2.428571,
To find a better approximation using data would require more computation.
Because the sequence is defined recursively, the limit will be a fixed point of the projection function. If we solve the fixed point equation, we can find the exact value of the limit.
The factored equation indicates there are two fixed points: \(x=0\) and \(x=\frac{17}{7}\text{.}\) The decimal approximation for \(x=\frac{17}{7}\) is 2.4285714286, which is precisely where our sequence is converging,
With these examples, we can introduce the mathematical definition for the limit of a sequence. The idea of a limit \(x_n \to L\) is that the value of the sequence \(x_n\) approximates the value of \(L\) closer and closer as \(n\) increases. Recall that we measure the quality of approximation using the error of approximation, \(|x_n - L|\text{.}\) The sequence successfully approximates the limit \(L\) if the error eventually become smaller than any desired accuracy of approximation.
For a real number \(L\text{,}\) a sequence \(x\) has a limit \(L\) if for any desired accuracy of approximation \(\epsilon \gt 0\text{,}\) the error of approximation is eventually \(|x_n - L| \lt \epsilon\) and we write
This means that for every \(\epsilon \gt 0\text{,}\) there is a threshold index \(N\) so that \(|x_n-L| \lt \epsilon\) whenever \(n \gt N\text{.}\)
In most cases, verifying the definition directly will be too challenging. We will usually learn to apply rules that guarantee that this definition will be satisfied rather than directly show that the approximation rule is satisfied. However, for sequences defined by sufficiently simple explicit formulas, we can determine how far down the table we would need to go to reach a desired accuracy. In these cases, we use strategies for solving inequalities to find the interval of integers where the error of approximation is sufficiently small.
Consider the sequence \(\displaystyle x_n = \frac{n}{2n+1}\text{,}\) for \(n=0,1,2,\ldots\text{.}\) Find numerical evidence that \(\displaystyle \lim_{n \to \infty} x_n = \frac{1}{2}\text{.}\) Then determine the index threshold \(N\) so that \(|x_n - \frac{1}{2}| \lt 0.001\) for index values \(n \gt N\text{.}\)
Using the following simple Sage script, we can generate a plot and table quickly. This script includes some modifications so that only a portion of the table is printed. We also have modified the format code to include more decimal values.
It appears that the sequence is leveling out to a value near 0.5. However, at index \(n=100\text{,}\) the value is at approximately \(x_{100} \approx 0.49751244\) (8 decimal places). If the limit really is \(x_n \to 0.5\text{,}\) then the error of approximation for \(n=100\) is
We need to ensure that the error continues to go down. At index \(n=1000\) (by modifying the script and running again), we have \(x_{1000} \approx 0.49975012\) with an error of approximation
The explicit formula for the sequence uses the function \(\displaystyle f(n)=\frac{n}{2n+1}\) for integer values of \(n\text{.}\) We can think of the mapping \(n \overset{f}\mapsto x\) for arbitrary values of \(n\) and not just integers. The inverse \(f^{-1}: x \mapsto n\) can inform us of when the sequence passes different values. We solve for \(n\) as the dependent variable.
This function, \(\displaystyle f^{-1}(x)=\frac{x}{1-2x}\text{,}\) gives the relation \(x \mapsto n\text{.}\)
From our graph, we have seen that \((n,x_n)\) is increasing and concave down. The sequence will always be below the limit. Given any desired error of approximation \(\epsilon \gt 0\text{,}\) we can use our inverse function to see exactly when the sequence rises above \(x_n \gt \frac{1}{2}-\epsilon\text{.}\) For example, with \(\epsilon = 0.001\text{,}\) we want to find when \(x_n \gt 0.5-0.001=0.499\text{.}\) We find
The sequence, which requires integer index values, will therefore be above \(x_n \gt 0.499\) for \(n \ge 250\text{.}\) In the definition of a limit, this corresponds to an index threshold \(N=249\) for accuracy \(\epsilon=0.001\text{.}\)
We can verify this numerically by running the script to show a table and graph for index values surrounding \(n=250\text{.}\) The table and graph show that the sequence value is below 0.499 for \(n \le 249\) and above 0.499 for \(n \ge 250\text{,}\) agreeing with our calculation.
\(n\) | \(x_n\) |
235 | 0.49893843 |
236 | 0.49894292 |
237 | 0.49894737 |
238 | 0.49895178 |
239 | 0.49895616 |
240 | 0.49896050 |
241 | 0.49896480 |
242 | 0.49896907 |
243 | 0.49897331 |
244 | 0.49897751 |
245 | 0.49898167 |
246 | 0.49898580 |
247 | 0.49898990 |
248 | 0.49899396 |
249 | 0.49899800 |
250 | 0.49900200 |
251 | 0.49900596 |
252 | 0.49900990 |
253 | 0.49901381 |
254 | 0.49901768 |
255 | 0.49902153 |
The inverse function, \(\displaystyle f^{-1}(x)=\frac{x}{1-2x}\text{,}\) is undefined for \(x=\frac{1}{2}\text{.}\) For values \(x \gt \frac{1}{2}\text{,}\) we will have negative values for \(n\text{,}\) \(f^{-1}(x) \lt 0\text{.}\) The sequence therefore will never reach or surpass the value \(x=\frac{1}{2}\text{.}\) But we will be able to identify when the function rises above every value below \(x=\frac{1}{2}\text{.}\) This is how we know that
A sequence has a limit, \(x_n \to L\text{,}\) if the values of the sequence get closer and closer to the value of \(L\text{.}\) The graph of the sequence \((n,x_n)\) approaches a horizontal line \(x=L\text{.}\)
If \(x_n \to L\text{,}\) then a table of values for the sequence \(x\) should have decimal approximations that converge to the decimal approximation of \(L\text{.}\)
Sequences defined recursively using a continuous projection function \(f\) can only have limits that are fixed points of \(f\text{.}\) (See Theorem 3.5.1)
The formal definition of a sequence limit \(x_n \to L\text{,}\) written
is that for any desired threshold of approximation error \(\epsilon \gt 0\text{,}\) there is an index threshold \(N\) so that \(|x_n - L| \lt \epsilon\) whenever \(n \gt N\text{.}\) (See Definition 3.5.5)
Use a computer-generated table to approximate the limit of the following sequences to at least four decimal places. If the limit does not exists, state why.
\(\displaystyle x_n = \sqrt{n} \cdot (\sqrt{3n+1} - \sqrt{3n})\)
\(\displaystyle x_n = n \cdot (\sqrt{3n+1} - \sqrt{3n})\)
\(\displaystyle x_n = \left(1+\frac{1}{3n}\right)^n\)
\(\displaystyle x_n = n^2 \cdot \left(\frac{1}{4n+5}-\frac{1}{4n}\right)\)
\(\displaystyle x_{n+1} = \frac{x_n}{5} + \frac{2}{x_n}\) with \(x_0 = 2\text{.}\)
\(\displaystyle x_{n+1} = \frac{x_n}{5} - \frac{2}{x_n}\) with \(x_0 = 2\text{.}\)
\(\displaystyle x_{n+1} = 5x_n e^{-x_n}\) with \(x_0 = 0.5\text{.}\)
\(\displaystyle x_{n+1} = 8x_n e^{-x_n/3}\) with \(x_0 = 0.5\text{.}\)
For each of the following functions, find all fixed points. Then, using a sequence defined recursively \(x_{n} = f(x_{n-1})\) and the given initial value, test if the sequence has a limit and give its exact value.
\(f(x) = 1.3 x + 12\text{;}\) \(x_0=1\)
\(f(x) = 0.8 x + 6\text{;}\) \(x_0=5\)
\(f(x) = 1.2x - 0.04x^2\text{;}\) \(x_0=3\)
\(\displaystyle f(x) = \frac{4x}{1+x^2}\text{;}\) \(x_0=3\)
For each of the following sequences, explore the definition of a limit by finding the index threshold associated with the approximation error threshold.
The sequence \(x_n = \frac{1}{2n+1}\) has a limit \(x_n \to 0\text{.}\) For \(\epsilon = 0.01\text{,}\) find \(N\) so that \(|x_n-0| \lt \epsilon\) for \(n \gt N\text{.}\)
The sequence \(x_n = \frac{n}{2n+1}\) has a limit \(x_n \to \frac{1}{2}\text{.}\) For \(\epsilon = 0.01\text{,}\) find \(N\) so that \(|x_n-\frac{1}{2}| \lt \epsilon\) for \(n \gt N\text{.}\)
The sequence \(x_n = \left(-\frac{2}{3}\right)^n\) has a limit \(x_n \to 0\text{.}\) For \(\epsilon = 0.01\text{,}\) find \(N\) so that \(|x_n-0| \lt \epsilon\) for \(n \gt N\text{.}\)