Does This Recursion Converge

An interviewer defines $a_1 = 1$ and $a_{n+1} = \tfrac{1}{2}\left(a_n + \tfrac{2}{a_n}\right)$, then asks: does this converge, and if so, to what? Simulating the sequence on paper for a few terms is a fine start, but the fast, reliable method is to assume it converges, solve for the limit algebraically, and separately check the assumption is valid.

Step 1: assume a limit exists and solve for it

If the sequence $a_{n+1} = f(a_n)$ converges to some value $L$, then as $n$ grows both $a_n$ and $a_{n+1}$ approach the same number $L$. Taking the limit of both sides of the recurrence gives $L = f(L)$ — the limit, if it exists, must be a fixed point of $f$. For $f(x) = \tfrac{1}{2}(x + 2/x)$, solving $L = \tfrac{1}{2}(L + 2/L)$ gives $2L = L + 2/L$, so $L = 2/L$, so $L^2 = 2$, so $L = \sqrt{2}$ (taking the positive root, since every term of the sequence is positive). In plain English: whatever the sequence settles on, that value has to reproduce itself under the recursion — which is a much easier equation to solve than tracking the sequence term by term.

Step 2: check convergence actually happens

Finding a candidate limit doesn't prove the sequence gets there — you need to verify the sequence is well-behaved near $L$. Two checks cover almost every interview case:

• Monotone + bounded. If you can show the sequence is always decreasing (or always increasing) and stays bounded below (or above), it must converge by the monotone convergence theorem — sequences that move in one direction and can't escape a boundary have nowhere to go but their limit.
• Contraction near the fixed point. If $|f'(L)| < 1$, nearby points get pulled closer to $L$ at each step, so the iteration is locally stable and converges once it's close enough. If $|f'(L)| > 1$, nearby points get pushed away — the fixed point is real but unstable, and the sequence would only reach it from an exact starting value, never approximately.

Worked example: verifying $\sqrt{2}$

For $f(x) = \tfrac12(x + 2/x)$, compute $f'(x) = \tfrac12(1 - 2/x^2)$, so $f'(\sqrt{2}) = \tfrac12(1 - 1) = 0$. Since $|f'(\sqrt2)| = 0 < 1$, the fixed point is strongly attracting — this is Newton's method for $\sqrt2$, famous for doubling the number of correct digits every step. Tracing the numbers confirms it: $a_1 = 1$, $a_2 = \tfrac12(1+2) = 1.5$, $a_3 = \tfrac12(1.5 + 1.333\ldots) = 1.41\overline{6}$, $a_4 = \tfrac12(1.41\overline6 + 1.41176\ldots) \approx 1.41421\overline{568}$ — already matching $\sqrt2 \approx 1.41421356$ to four decimal places by the fourth term.

Drag the sample size and watch how a running sequence value settles onto its limit, with the gap shrinking inside a shaded envelope — exactly the "settling down" behavior you're checking for algebraically above, just made visible instead of computed by hand.

What this means in practice

This two-step method — solve $L = f(L)$, then check monotonicity or the derivative at $L$ — turns "does this recursive sequence converge" from a simulation exercise into an algebra-plus-calculus check you can do at a whiteboard. It's also exactly the reasoning behind fixed-point iteration schemes used to solve implied-volatility equations and other places where a model input has to be backed out from an equation that can't be inverted directly: you're relying on the same contraction argument to know the iteration will actually land somewhere.