Recursive sequences
Task number: 2876
Show that the following recursively defined sequences \(\{a_n\}\) have limits, and determine them.
Variant 1
\(a_1=\sqrt c\), where \(c\) is a positive real number, and \(a_{n+1}=\sqrt{a_n+c}\).
Resolution
We will proceed in a sequence of steps. In one step we will show that the sequence must have a limit. In another step we will calculate the limit, given that we know that the limit exists.
We intend to show that the sequence is non-negative, increasing and bounded above. If we can prove this, then from the theorem about the limit of a monotonic sequence it will follow that this particular sequence has a limit.
From a computational standpoint it is easier to swap these steps. We will first calculate the limit, under the assumption that it exists. Only afterward will we prove the existence of the limit, and some steps from the calculation of the limit will also prove useful in the proof of existence. (Keep in mind that the following calculation strongly depends on the assumption that the limit exists. If we could not prove its existence (e.g. in another example), there would be no point in calculuating the limit.)
The limit \(a\) of this sequence must fulfill \(\displaystyle a= \lim_{n\to \infty} a_n = \lim_{n\to \infty} a_{n+1} = \lim_{n\to \infty} \sqrt{a_n+c}= \sqrt{a+c}\)
Squaring, we obtain the equation \(a^2=a+c\), which has one negative and one positive solution. From the definition of the sequence we can see that all its terms are positive, so \(a\) must be non-negative. So we have \(a=\frac12+\sqrt{c+\frac14}\).
Now we proceed to prove the existence of the limit. We begin by proving that the sequence is bounded above. Also bear in mind that we want to show that the sequence is increasing. So it is natural to try to show that the sequence is bounded above by the value of the limit.
So we will show by induction that \(a_n<a\). For \(n=1\) we have \(a_1=\sqrt{c}<\frac12+\sqrt{c+\frac14}=a\). For other values of \(n\), we have \(a_n=\sqrt{a_{n-1}+c}<\sqrt{a+c}=\sqrt{a^2}=a\).
It remains for us to show that \(a_{n+1} > a_n\).
We have \(a_{n+1}=\sqrt{a_n+c}\), and so we want to show that \(\sqrt{a_n+c} > a_n\). The expressions on both sides of the inequality are positive, so squaring both sides yields an equivalent proposition, therefore it suffices to show that \[ a_n + c > a_n^2. \] We have a quadratic inequality in the variable \(a_n\), which has the same roots as the equation for calculating the limit. Solving this inequality, we determine that it holds for \[a_n \in \left( \frac12 - \sqrt{c + \frac14}, \frac12 + \sqrt{c + \frac14}\right) = \left( \frac12 - \sqrt{c + \frac14}, a\right).\] But from the proof of boundedness we already know that \(a_n \in (0, a)\), which is exactly what we need. (This is another reason why we first proved that the sequence is bounded above.)
Note that only now have we shown that the limit exists for all \(c\).
Result
The limit of the sequence is \(\frac12+\sqrt{c+\frac14}\).
Variant 2
\(a_1=0\) and \(a_{n+1}=a_n+\frac12 (x-a_n)^2\), for \(0\le x \le 1\).
Resolution
The sequence is non-decreasing, because \(a_{n+1}-a_n=a_n+\frac12 (x-a_n)^2-a_n=\frac12 (x-a_n)^2\ge 0\). So all terms are non-negative.
A good candidate for the limit is the value \(a\) satisfying \(a=a+\frac12 (x-a_n)^2\), i.e. \(a=x\).
It remains to show by induction that \(a_n\le x\) for all \(n\). First we have \(a_1=0\le x\). Then from the assumption \(a_n\le x\le 1\) we infer \(x-a_n \le 1\). And then \(a_{n+1}=a_n+\frac12 (x-a_n)^2\le a_n+(x-a_n)^2\le a_n+x-a_n=x\).
Result
The limit of the sequence is \(x\).
Variant 3
\(a_1=\sqrt{2}\) and \(a_{n+1}=\sqrt{2-a_n}\).
Hint
The sequence is not monotonic.
Resolution
We can show by induction that \(a_n\in (0,\sqrt 2\rangle\).
If this sequence has a limit \(a\), this limit must satisfy \(a=\sqrt{2-a}\). The solution to this equation is the non-negative solution of the equation \(a^2=2-a\). And so \(a=1\).
We notice from the first few terms of the sequence that it oscillates around the value \(1\). We will show that \(a_{n+1}\) is closer to \(1\) than \(a_n\).
When \(n\) is even \(a_n>1\), so let us verify that \(a_n-1>1-a_{n+1} \Longleftrightarrow a_{n+1}> 2-a_n \Longleftrightarrow 2-a_n > 4-4a_n+a_n^2\), which is satisfied in the interval \((1,\infty)\).
Similarly when \(n\) is odd \(a_n<1\), so we check that \(a_{n+1}< 2-a_n\), which is satisfied when \(a_n\in(-2{,}1)\).
So the subsequence of odd terms has a limit and the subsequence of even terms has a limit. It must be the same limit \(a\), because in both subsequences it is determined by the relationship \(a=\sqrt{2-\sqrt{2-a}}\).
Result
The limit of the sequence is \(1\).
Variant 4
\(a_1=1\) a \(a_{n+1}=\frac1{1+a_n}\)
Hint
Investigate the subsequences of even and odd terms separately.
Resolution
The sequence begins \(1,\frac12,\frac23,\frac35,\frac85,…\), so it is not monotonic. Notice that the terms with odd indices form a descending subsequence, while the tems with even indices are increasing. Of course we will prove this fact.
If the sequence has a limit \(a\), it must satisfy \(a=\frac1{1+a_n} \Longleftrightarrow a^2+a-1=0\), which has two solutions, of which only one is positive, namely \(a=\frac{\sqrt 5-1}2\).
The recurrence for both of the chosen subsequences is given by the relationship \(a_{n+2}=\frac1{1+a_{n+1}}=\frac1{1+\frac1{1+a_n}}=1-\frac1{a_n+2}\).
First, for the subsequence with odd indices we verify that from the assumption \(a_n\ge\frac{\sqrt 5-1}2\) it follows that \(a_n\ge a_{n+2}\ge\frac{\sqrt 5-1}2\).
Namely \(a_n\ge a_{n+2} \Longleftrightarrow a_n\ge1-\frac1{a_n+2} \Longleftrightarrow a_n^2+a_n-1 \ge 0\), which is satisfied when \(a_n\ge\frac{\sqrt 5-1}2\).
Similarly \(a_{n+2}= 1-\frac1{a_n+2}\ge 1-\frac1{\frac{\sqrt 5-1}2+2} = \frac{\sqrt 5-1}2 \).
We can use the same argument for the subsequence with even indices, reversing the direction of the inequalities in every step.
Result
The limit of the sequence is \(\frac{\sqrt 5-1}2\).
Variant 5
\(a_1= c\), where \(c\) is a positive real nuimber, and \(\displaystyle a_{n+1}=\frac12\left(a_n+\frac2{a_n}\right)\).
Hint
Investigate the subsequences of even and odd terms separately.
Resolution
If the sequence has a limit \(a\), it must be that \(a=\frac12\left(a+\frac2{a}\right) \Longleftrightarrow 2a^2-a-2=0\), which has two solutions, of which only one is positive, namely \(a=\sqrt 2\).
First we will rewrite the recurrence \(a_{n+1}=\frac12\left(a_n+\frac2{a_n}\right)=\frac{a_n^2+2}{2a_n}\).
For both of the chosen subsequences, the recurrence is given by the relationship
\(\displaystyle a_{n+2}=\frac{a_{n+1}^2+2}{2a_{n+1}}=\frac{\left(\frac{a_n^2+2}{2a_n}\right)^2+2}{2{\frac{a_n^2+2}{2a_n}}}=\frac{a_n^4+12a_n^2+4}{4a_n^3+8a_n}\).
We will verify that the assumption \(a_n\ge\sqrt 2\) implies that \(a_n\ge a_{n+2}\ge\sqrt 2\).
\( a_n\ge a_{n+2} \Longleftrightarrow a_n\ge \frac{a_n^4+12a_n^2+4}{4a_n^3+8a_n} \Longleftrightarrow 3a_n^4-4a_n^2-4 \ge 0\). The quadratic equation \(3x^2-4x-4 \ge 0\) has roots \(x_{1{,}2}=\frac{2\pm 4}{3}\), so if \(a_n^2\ge 2\) then the original inequality holds.
Similarly, \(a_{n+2} \ge \sqrt2 \Longleftrightarrow \frac{a_n^4+12a_n^2+4}{4a_n^3+8a_n} \ge \sqrt2 \Longleftrightarrow a_n^4+12a_n^2+4 \ge \sqrt2(4a_n^3+8a_n) \ge 32 \Longleftrightarrow a_n^4+12a_n^2-28 \ge 0 \). Now the quadratic equation \(x^2+12x-28 \ge 0\) has the roots \(x_{1{,}2}=6\pm 8\), so again the original inequality holds.
From the assumption \(a_n\le\sqrt 2\) we can infer (almost) the same conclusions, only the inequalities will be reversed in every step.
The only difference is that for small values of \(a_n\) (roughly for \(a_n<1{,}372\)), it is true that \(a_n^4+12a_n^2+4 \le 32\) but not that \(a_n^4+12a_n^2+4 \le \sqrt2(4a_n^3+8a_n)\). Of course, this can only be the case for the first sequence term \(a_1\). Both subsequences beginning with \(a_2\) and \(a_3\) will be descending, which of course does not affect the proof of the existence of the limit.
Result
The limit of the sequence is \(\sqrt 2\).
