For a sequence given by a recursive rule, such as $a_{n+1} = \sqrt{2 + a_n}$, there may be no formula for $a_n$ at all. You can still prove that it converges, and then find the limit, using one of the most important facts about the real numbers.
Why it works
Suppose the terms only go up ($a_1 \le a_2 \le \cdots$) and never pass some ceiling $M$. The set of terms has a least upper bound $L$ (this is the completeness of the real numbers: the number line has no gaps). For any $\varepsilon > 0$, the number $L - \varepsilon$ is not an upper bound, so some term $a_N$ is above it. Every later term is at least $a_N$ (the terms only rise) and at most $L$. So from $N$ on, all terms are within $\varepsilon$ of $L$: the sequence converges to $L$.
Key idea
Monotone convergence theorem: a sequence that is increasing and bounded above converges; so does one that is decreasing and bounded below. For a recursive rule $a_{n+1} = g(a_n)$ with $g$ continuous, once you know the sequence converges, its limit satisfies $L = g(L)$.
Worked example: A recursive sequence
Let $a_1 = 0$ and $a_{n+1} = \frac{a_n}{2} + 3$. Show it converges and find the limit.
- The first terms are $0, 3, 4.5, 5.25, \ldots$: they seem to rise toward 6.
- Bounded: if $a_n < 6$ then $a_{n+1} < \frac{6}{2} + 3 = 6$. So by induction every term is below 6.
- Increasing: $a_{n+1} - a_n = 3 - \frac{a_n}{2} > 0$ because $a_n < 6$.
- So it converges, and the limit satisfies $L = \frac{L}{2} + 3$, giving $L = 6$.
Answer: It converges to $6$.
Worked example: Nested roots
Let $a_1 = 0$ and $a_{n+1} = \sqrt{2 + a_n}$. Find the limit.
- The terms $0, \sqrt{2}, \sqrt{2 + \sqrt{2}}, \ldots$ increase and stay below 2 (if $a_n < 2$, then $a_{n+1} < \sqrt{4} = 2$).
- So the limit exists and $L = \sqrt{2 + L}$, that is $L^{2} - L - 2 = 0$, so $L = 2$ or $L = -1$.
- The terms are not negative, so $L = 2$.
Answer: $2$
Common mistake
Solving $L = g(L)$ before knowing the limit exists. For $a_1 = 1$, $a_{n+1} = 2a_n$, the equation $L = 2L$ gives $L = 0$, but the sequence is $1, 2, 4, 8, \ldots$, which diverges. The equation only finds the limit if there is one. Also, bounded alone is not enough ($(-1)^{n}$ is bounded and diverges); you need monotone and bounded.
Worked example: An explicit sequence
Does $a_n = \frac{n}{n + 1}$ converge?
- $a_n = 1 - \frac{1}{n + 1}$, and the subtracted part shrinks, so the terms increase.
- Every term is less than 1, so the sequence is bounded above.
- By the theorem it converges (here we can also see the limit directly: 1).
Answer: Yes, to 1.