$\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$

Question

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 <n_0\Big\}$ 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)$")

Answer 1

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_*)$$

Answer 2

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.