Home » Blog » Prove that the recursive sequence xn+1 = (1+xn)1/2 converges

Prove that the recursive sequence xn+1 = (1+xn)1/2 converges

Prove that the sequence \{ x_n \} whose terms are defined recursively by

    \[ x_1 = 1, \qquad x_{n+1} = \sqrt{1+x_n} \]

converges, and compute the limit of the sequence.


Proof. To show the sequence converges we show that it is monotonically increasing and bounded above. To see that it is monotonically increasing we use induction to prove that

    \[ x_{n+1} > x_n \qquad \text{for all } n \in \mathbb{Z}_{>0}. \]

For the case n = 1 we have

    \[ x_{n+1} = x_2 = \sqrt{2}, \qquad \text{and} \qquad x_n = x_1 = 1. \]

Since \sqrt{2}  >1, the statement holds in the case n =1. Assume then that the statement holds for some positive integer k. Then,

    \begin{align*}  x_{k+2} - x_{k+1} &= \sqrt{1+x_{k+1}} - \sqrt{1+x_k}\\[9pt]  &> 0 \end{align*}

since x_{k+1} > x_k by the induction hypothesis. Hence, x_{k+2} > x_{k+1} so by induction x_{n+1} > x_n for all positive integers n. Hence, the sequence is monotonically increasing.
Next we use induction again to prove the sequence is bounded above by 2. For n = 1 we have x_1 = 1 < 2 so the hypothesis holds. Assume then that x_k < 2 for all positive integers up to k. Then,

    \begin{align*}  x_{k+1} &= \sqrt{1+x_k} \\  &\leq \sqrt{1+2} \\  &\leq 2. \end{align*}

Hence, x_n < 2 for all positive integers n.
This shows that the sequence converges.\qquad \blacksquare

To compute the limit, assume the sequence converges to a number L (we just proved that it converges, so this assumption is valid). Then we have

    \begin{align*}  \lim_{n \to \infty} x_{n+1} &= L & \implies && \lim_{n \to \infty} \sqrt{1+x_n} &= L \\[9pt]  && \implies && \sqrt{1+L} &= L \\[9pt]  && \implies && L^2 - L - 1 &= 0 \\[9pt]  && \implies && L &= \frac{1 + \sqrt{5}}{2}. \end{align*}

(We can discard the negative solution since to the quadratic at the end since the sequence is certainly all positive terms.)

Point out an error, ask a question, offer an alternative solution (to use Latex type [latexpage] at the top of your comment):