# $\lim_{n \to \infty}\frac{d(x_{n+1}, x_\star)}{d(x_n, x_\star)} = 0$, show that $d(x_n, x_\star)\leq K\varepsilon^n \quad \text{for all }n\geq 0$

Let $$(\mathcal{X}, d)$$ be a metric space and $$(x_n)_{n = 0}^\infty$$ a sequence in $$\mathcal{X}$$ converging to $$x_\star \in \mathcal{X}$$, meaning that $$\lim_{n \to \infty}d(x_n, x_\star) = 0$$

We suppose that $$\lim_{n \to \infty}\frac{d(x_{n+1}, x_\star)}{d(x_n, x_\star)} = 0$$ Show that, for all $$\varepsilon \in (0,1)$$, there exists $$K = K(\varepsilon)\in (0,\infty)$$ s.t. $$d(x_n, x_\star)\leq K\varepsilon^n \quad \text{for all }n\geq 0$$

answer: We suppose that $$\lim_{n \to \infty}\frac{d(x_{n+1}, x_\star)}{d(x_n, x_\star)} = 0$$ $$\forall \varepsilon \in (0,1), \exists n_0 \in \mathbb{N}, \forall n\geq n_0,\frac{d(x_{n+1}, x_\star)}{d(x_n, x_\star)} \leq \varepsilon$$ \newline Then $$d(x_{n +1}, x_\star)\leq \varepsilon d(x_n, x_\star)$$ \newline However $$\forall n > n_0, \exists k\in \mathbb{N}^\star$$, $$n = n_0 + k$$. And then: \begin{align*} d(x_n, x_\star) &= d(x_{n_0 + k}, x_\star)\\ &\leq \varepsilon d(x_{n_0 + k-1}, x_\star) \qquad (1)\\ &\leq \varepsilon^2 d(x_{n_0 + k-2}, x_\star) \qquad (2)\\ &\leq \varepsilon^{(k_0)} d(x_{n_0}, x_\star)\cdot \frac{\varepsilon^{(k_0)}}{\varepsilon^{(k_0)}} \qquad (3)\\ &\leq \varepsilon^n\underbrace{\frac{d(x_{n_0}, x_\star)}{\varepsilon^{(n_0)}}}_{K_1} \end{align*} And for $$n \leq n_0$$: The set $$\Big\{\frac{d(x_{n_0}, x^\star)}{\varepsilon^{(n_0)}}; n is finite and therefore it has a maximum noted $$K_2$$

Then for $$n \leq n_0$$: $$d(x_n, x_\star) = \frac{d(x_{n}, x^\star)}{\varepsilon^{n}}\varepsilon^n \leq K_2\varepsilon^n$$ We take $$K(\varepsilon) = \max (K_1, K_2)$$ and we have the result: \newline $$\forall n \in \mathbb{N}$$

• if $$n \leq n_0$$; $$d(x_n, x_\star) \leq \varepsilon^n K_2 \leq \varepsilon^n K(\varepsilon)$$
• else ; $$d(x_n, x_\star) \leq \varepsilon^n K_1 \leq \varepsilon^n K(\varepsilon)$$

$$\rightarrow \forall n \in \mathbb{N} d(x_n, x^\star) \leq \varepsilon^n K(\varepsilon)$$

My question

How can we justify that the inequality still remains valid when going from (1 : "$$\leq \varepsilon d(x_{n_0 + k-1}, x_\star)$$" to (2: "$$\leq \varepsilon^2 d(x_{n_0 + k-2}, x_\star)$$")

For all $$n \ge n_0$$ we have $$d(x_{n+1},x_*) \le \varepsilon d(x_{n},x_*)$$.

Then if $$k \ge 2$$ we have $$n_0 + k-2 \ge n_0$$ so

$$\varepsilon d(x_{n_0 + k-1}, x_*) = \varepsilon d(x_{(n_0 + k-2)+1}, x_*) \le \varepsilon\cdot \varepsilon d(x_{n_0+k-2}, x_*) = \varepsilon^2 d(x_{n_0+k-2}, x_*)$$

• Thanks a lot for your clear answer @mechanodroid. One more notation point: how could we best spell out the expression $d(x_{n+1}, x_\star)$? Is it correct to say: "the distance between the real number $x_{n+1}$ and $x_\star$"
– ecjb
Jul 22, 2019 at 9:48
• @ecjb Those are elements of $\mathcal{X}$, not real numbers. It is e.g. distance between $x_{n+1}$ and $x_\star$ in $(\mathcal{X}, d)$. Jul 22, 2019 at 9:50
• Ok, many thanks @mechanodroid
– ecjb
Jul 22, 2019 at 9:52

Let us re-write the inequalities as follows: let $$b_i=d(x_{n_0+i},x_{*})$$. Then $$b_k \leq \epsilon b_{k-1} \leq \epsilon^{2}b_{i-2} \leq \cdots \leq \epsilon^{n}b_0$$. Hence $$d(x_{n},x_{*})\leq \epsilon^{k} d(x_{n_0},x_{*})=\epsilon^{n-n_0} d(x_{n_0},x_{*})$$. This is the final inequality.