Sequences that feed on themselves
Tonight's idea
A recursive sequence gives a starting term and a rule that makes each term from the one before: \(x_{n+1} = f(x_n)\). Take \(x_0 = 0\) and \(x_{n+1} = 0.5x_n + 3\). The terms run 0, 3, 4.5, 5.25, 5.625. They close in on 6.
You can predict the 6 without computing a term. Suppose the terms settle on a limit \(L\). Then \(x_n\) and \(x_{n+1}\) both end up as close to \(L\) as you like, so a rule with no jumps forces
\(L = f(L)\). Here \(L = 0.5L + 3\), so \(L = 6\).
The catch is the word "suppose". The equation says where a limit must be if there is one. The rule \(x_{n+1} = 2x_n - 6\) also gives \(L = 6\), but from \(x_0 = 7\) the terms run 7, 8, 10, 14, 22.
To tell which happens, subtract \(L\) from both sides. For \(x_{n+1} = ax_n + b\) this leaves \(x_{n+1} - L = a(x_n - L)\): every step multiplies the gap by \(a\). If \(|a| \lt 1\) the gap shrinks to zero and the sequence settles. If \(|a| \gt 1\) every nonzero gap grows, while a start exactly at \(L\) stays there. If \(a = -1\) the gap only changes sign: the terms alternate between two values, unless you start at \(L\), where they stay. The case \(a = 1\) is different, because \(L = a L + b\) cannot be solved the same way: \(b = 0\) makes every sequence constant, and \(b \ne 0\) gives a steady drift, and no value of \(L\) works.
Watch one: \(x_{n+1} = \sqrt{2 + x_n}\), starting at \(x_0 = 0\)
The terms run 0, 1.414, 1.848, 1.962, 1.990. If they settle, \(L = \sqrt{2 + L}\), so \(L^2 - L - 2 = 0\) and \(L = 2\) or \(-1\). No term is negative, so \(L = 2\).
Is "if they settle" justified? Whenever \(0 \le x \lt 2\), the next term \(\sqrt{2 + x}\) is bigger than \(x\) and still below \(\sqrt4 = 2\). So the terms climb for ever under a ceiling of 2. Such a sequence must settle; take that as a fact for now.
The demo runs a curved rule, \(x_{n+1} = r\,x_n(1 - x_n)\), met in grade 10. Press 2.8 and it settles. Press 3.2 and it flips between two values. Press 4 and it never settles: mathdetours.com/demos/logistic.html.
Your turn
- Let \(x_0 = 10\) and \(x_{n+1} = 0.8x_n + 1\). Find \(x_1\), \(x_2\) and \(x_3\). Then find the limit by solving \(L = f(L)\), and say why the sequence does settle.
- Each rule starts from \(x_0 = 1\). Solve \(L = f(L)\), then decide whether the sequence settles, runs away or cycles: (a) \(x_{n+1} = -0.5x_n + 9\); (b) \(x_{n+1} = 3x_n - 4\); (c) \(x_{n+1} = -x_n + 10\).
- Let \(x_0 = 3\) and \(x_{n+1} = \tfrac12\left(x_n + \dfrac{10}{x_n}\right)\). Find \(x_1\) and \(x_2\) to four decimal places. Assuming the terms settle, find \(L\) exactly. What is this rule computing?
- Each year 30% of the pollutant in a lake is flushed out, and then a factory adds 6 tonnes. The lake holds 50 tonnes now. Write the rule and find the long-run level. After how many years is the level within 1 tonne of it? The owners want a long-run level of 12 tonnes: how much may they add each year?
Stretch: a limit almost nobody reaches
For the rule \(x_{n+1} = x_n^2\), the equation \(L = L^2\) gives \(L = 0\) or \(L = 1\). For which starting values \(x_0\) does the sequence settle on 0? On 1? What happens for every other start?
Answers
- \(x_1 = 9\), \(x_2 = 8.2\), \(x_3 = 7.56\). \(L = 0.8L + 1\) gives \(L = 5\). It settles because each step multiplies the gap from 5 by 0.8: the gaps are 5, 4, 3.2, 2.56, shrinking to zero.
- (a) \(L = 6\); \(a = -0.5\), so the gap halves and changes sign each step. It settles on 6, hopping from side to side: 1, 8.5, 4.75, 6.625. (b) \(L = 2\), but \(a = 3\), so the gap triples: 1, \(-1\), \(-7\), \(-25\). It runs away. (c) \(L = 5\), but \(a = -1\): 1, 9, 1, 9. It cycles and never reaches 5.
- \(x_1 = \tfrac{19}{6} \approx 3.1667\), \(x_2 = \tfrac{721}{228} \approx 3.1623\). \(L = \tfrac12\left(L + \tfrac{10}{L}\right)\) gives \(2L^2 = L^2 + 10\), so \(L^2 = 10\). The terms are positive, so \(L = \sqrt{10} = 3.16228\ldots\) The rule computes square roots, and two steps already give four correct decimal places.
- \(x_{n+1} = 0.7x_n + 6\). \(L = 0.7L + 6\) gives \(L = 20\) tonnes, and \(|0.7| \lt 1\) so the level does settle there. The gap starts at 30 and is \(30 \times 0.7^n\) after \(n\) years. \(30 \times 0.7^9 \approx 1.21\) and \(30 \times 0.7^{10} \approx 0.85\), so 10 years. For a limit of 12: \(12 = 0.7 \times 12 + b\), so \(b = 3.6\) tonnes a year.
Stretch. Squaring again and again gives \(x_n = x_0^{\,2^n}\). If \(-1 \lt x_0 \lt 1\) the terms shrink to 0. If \(x_0 = 1\) or \(-1\) the sequence is 1 from the first step on. Every other start has \(|x_0| \gt 1\) and runs away. So \(L = 1\) solves the equation, yet only two starting values reach it. Solving \(L = f(L)\) lists the candidates; it does not say which one you get.