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.