Logo
Published on

Recursive sequence and limiting value

Authors
  • avatar
    Name
    Vu Hung
    Twitter

Problem Statement

Let (xn)(x_n) be defined by

x1=16,xn+1=2+1xn(n≥1).x_1=16,\qquad x_{n+1}=2+\frac{1}{x_n}\quad (n\ge 1).
  • Find exact values of x2,x3,x4x_2,x_3,x_4.
  • Assuming xn→L>0x_n\to L>0, show that L=1+2L=1+\sqrt{2}.
  • Prove that
∣xn+1−L∣=∣xn−L∣Lxn,|x_{n+1}-L|=\frac{|x_n-L|}{Lx_n},

and deduce that for n≥2n\ge 2,

∣xn+1−L∣<14∣xn−L∣.|x_{n+1}-L|<\frac14|x_n-L|.
  • Hence show xn→1+2x_n\to 1+\sqrt{2}.

Solutions

(i)

x2=2+116=3316,x3=2+1633=8233,x4=2+3382=19782.x_2=2+\frac1{16}=\frac{33}{16},\quad x_3=2+\frac{16}{33}=\frac{82}{33},\quad x_4=2+\frac{33}{82}=\frac{197}{82}.

For n≥2n\ge 2, we have xn>2x_n>2 because each term is 2+1xn−12+\frac{1}{x_{n-1}} with positive second part.

(ii) If xn→Lx_n\to L, then taking limits in the recurrence gives

L=2+1L  ⟹  L2−2L−1=0.L=2+\frac1L \implies L^2-2L-1=0.

So L=1±2L=1\pm\sqrt2. Since terms are positive and >2>2 from n≥2n\ge2, we take

L=1+2.L=1+\sqrt2.

(iii)

xn+1−L=(2+1xn)−(2+1L)=L−xnLxn,x_{n+1}-L=\left(2+\frac1{x_n}\right)-\left(2+\frac1L\right) =\frac{L-x_n}{Lx_n},

thus

∣xn+1−L∣=∣xn−L∣Lxn.|x_{n+1}-L|=\frac{|x_n-L|}{Lx_n}.

Now L=1+2>2L=1+\sqrt2>2 and xn>2x_n>2 for n≥2n\ge2, so Lxn>4Lx_n>4. Hence

∣xn+1−L∣<14∣xn−L∣,n≥2.|x_{n+1}-L|<\frac14|x_n-L|,\quad n\ge2.

(iv) Repeatedly applying the inequality gives geometric decay of the error:

∣xn−L∣≤(14)n−2∣x2−L∣→0.|x_{n}-L|\le \left(\frac14\right)^{n-2}|x_2-L|\to 0.

Therefore xn→L=1+2x_n\to L=1+\sqrt2.

Takeaways

  • For recursive limits, first solve the fixed-point equation.
  • A contraction inequality gives a rigorous convergence proof.
  • The same method works for many rational recursions.
  • The sequence xnx_n is related to the continued fraction of 1+21+\sqrt{2}. It can be expressed as

xn+1=2+1xn=2+12+1xn−1=⋯=2+12+12+⋯+1x1x_{n+1} = 2 + \frac{1}{x_n} = 2 + \frac{1}{2 + \frac{1}{x_{n-1}}} = \dots = 2 + \frac{1}{2 + \frac{1}{2 + \dots + \frac{1}{x_1}}}

Further Readings

Connect with me