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)$")


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

| cite | improve this answer | |
  • $\begingroup$ 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$" $\endgroup$ – ecjb Jul 22 '19 at 9:48
  • $\begingroup$ @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)$. $\endgroup$ – mechanodroid Jul 22 '19 at 9:50
  • $\begingroup$ Ok, many thanks @mechanodroid $\endgroup$ – ecjb Jul 22 '19 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.