Convergence of a recursevely defined sequence x 0 = 0, x n + 1 = 1 − ( 1 / 2 ) x n 2

Question

Convergence of a recursevely defined sequence       x    0    =  0,       x          n      +      1        =  1  −  (  1      /    2  )      x    n    2

Cristopher Barrera · Accepted Answer

First, we try a loose bound. Notice that

x_{0} = 0, x_{1} = 1

and

x_{n} \in [0, 1]

. Also we can say that

x_{n} = 1 - 1 / 2 x_{n}^{2} \Rightarrow (x_{n} - (\sqrt{3} - 1)) = - (x_{n - 1} - (\sqrt{3} - 1)) \frac{\sqrt{3} - 1 + x_{n - 1}}{2}

. Therefore we have

| x_{n} - (\sqrt{3} - 1) | = | x_{n - 1} - (\sqrt{3} - 1) | | \frac{\sqrt{3} - 1 + x_{n - 1}}{2} | \leq | x_{n - 1} - (\sqrt{3} - 1) | \frac{\sqrt{3}}{2}

So we can know that

| x_{n} - \sqrt{3} + 1 | \leq (\sqrt{3} - 1) (\frac{\sqrt{3}}{2})^{n}

Now we refine our estimation: we know that

\begin{aligned} | x_{n} - (\sqrt{3} - 1) | = | x_{n - 1} - (\sqrt{3} - 1) | | \frac{\sqrt{3} - 1 + x_{n - 1}}{2} | \\ = & | x_{0} - (\sqrt{3} - 1) | \prod_{i = 0}^{n - 1} | \frac{\sqrt{3} - 1 + x_{i}}{2} | \\ = & (\sqrt{3} - 1) \prod_{i = 0}^{n - 1} | \sqrt{3} - 1 + \frac{x_{i} - (\sqrt{3} - 1)}{2} | \\ = & (\sqrt{3} - 1) \prod_{i = 0}^{n - 1} (\sqrt{3} - 1) | 1 + \frac{x_{i} - (\sqrt{3} - 1)}{2 (\sqrt{3} - 1)} | \\ \leq & (\sqrt{3} - 1)^{n + 1} \exp (\sum_{i = 0}^{n - 1} | \frac{x_{i} - (\sqrt{3} - 1)}{2 (\sqrt{3} - 1)} |) & by 1 + x \leq e^{x} \\ \leq & (\sqrt{3} - 1)^{n + 1} \exp (\sum_{i = 0}^{n - 1} \frac{(\sqrt{3} - 1) (\frac{\sqrt{3}}{2})^{i}}{2 (\sqrt{3} - 1)}) \\ \leq & (\sqrt{3} - 1)^{n + 1} \exp (\sum_{i = 0}^{\infty} \frac{(\sqrt{3} - 1) (\frac{\sqrt{3}}{2})^{i}}{2 (\sqrt{3} - 1)}) = (\sqrt{3} - 1)^{n + 1} \exp (2 + \sqrt{3}) \end{aligned}

Take

C = \exp (2 + \sqrt{3}) (\sqrt{3} - 1)

suffice.
Similarly, we have (notice that

x_{n} > 0

so

\frac{x_{n} - (\sqrt{3} - 1)}{2 (\sqrt{3} - 1)} > - \frac{1}{2}

. For

x > - 1 / 2

we know that

1 + x \geq e^{- 2 | x |}

\begin{aligned} | x_{n} - (\sqrt{3} - 1) | = | x_{n - 1} - (\sqrt{3} - 1) | | \frac{\sqrt{3} - 1 + x_{n - 1}}{2} | \\ = & (\sqrt{3} - 1) \prod_{i = 0}^{n - 1} (\sqrt{3} - 1) | 1 + \frac{x_{n - 1} - (\sqrt{3} - 1)}{2 (\sqrt{3} - 1)} | \\ \geq & (\sqrt{3} - 1)^{n + 1} \exp (\sum_{i = 0}^{n - 1} - 2 | \frac{x_{n - 1} - (\sqrt{3} - 1)}{2 (\sqrt{3} - 1)} |) \\ \geq & (\sqrt{3} - 1)^{n + 1} \exp (- 2 \sum_{i = 0}^{n - 1} \frac{(\sqrt{3} - 1) (\frac{\sqrt{3}}{2})^{i}}{2 (\sqrt{3} - 1)}) \\ \geq & (\sqrt{3} - 1)^{n + 1} \exp (- 2 \sum_{i = 0}^{\infty} \frac{(\sqrt{3} - 1) (\frac{\sqrt{3}}{2})^{i}}{2 (\sqrt{3} - 1)}) = (\sqrt{3} - 1)^{n + 1} \exp (- 4 - 2 \sqrt{3}) \end{aligned}

Take

c = (\sqrt{3} - 1) \exp (- 4 - 2 \sqrt{3})

suffice.

Convergence of a recursevely defined sequence x 0 </msub> = 0 , x <mro

Answered question

Answer & Explanation

New Questions in Precalculus