If $(a_n)$ is Cauchy it has a subsequence $(a_{n_i})$ such that $d(a_{n_{i+1}},a_{n_i})<2^{-i}$ for all $i$. Let $(X,d)$ be a metric space and $(a_n)$ a Cauchy sequence in $X$. How to show that there exists $n_1<n_2<\cdots$ such that
$$d(a_{n_{i+1}},a_{n_i})<2^{-i},$$
for all $i\in\mathbb{N}$?
I tried to use induction, but it doesn't work. The base case is OK, but if we have
$$d(a_{n_2},a_{n_1})<2^{-1},\ldots,d(a_{n_k},a_{n_{k-1}})<2^{-(k-1)},$$
I don't see any reason for to exist $n_{k+1}>n_k$ such that $d(a_{n_{k+1}},a_{n_k})<2^{-k}$.
 A: What does it mean for a sequence to be Cauchy?  It means for each $\epsilon > 0$, there is some $N \in \mathbb{N}$ such that $n, m \geq N$ implies $d(x_{n}, x_{m}) < \epsilon$.
Since this is true for every $\epsilon > 0$, it is true if $\epsilon = \frac{1}{2}$, for example.  That is, there is some $N_{1} \in \mathbb{N}$ such that $n, m \geq N_{1}$ implies $d(x_{n}, x_{m}) < \frac{1}{2}$.  Let $n_{1} = N_{1}$.
Similarly, we know if $\epsilon= \frac{1}{2^{2}}$, there is some $N_{2} \in \mathbb{N}$ such that $n, m \geq N_{2}$ implies $d(x_{n}, x_{m}) < \frac{1}{2^{2}}$.  But if this is true for all $n, m \geq N_{2}$, then it is true for all $n, m \geq N_{2} + 1$.  And for all $n, m \geq N_{2} + 2$.  And for all $n, m \geq p > N_{2}$ where $p$ is any integer greater than $N_{2}$.  In particular, this is true for $\max \{n_{1}, N_{2} \} + 1$.  So we can let $n_{2} = \max \{n_{1}, N_{2} \} + 1$, and clearly, $n_{2} > n_{1}$, and if $n, m \geq n_{2}$, $d(x_{n}, x_{m}) < \frac{1}{2^{2}}$.
Similarly, we know if $\epsilon = \frac{1}{2^{3}}$, there is some $N_{3} \in \mathbb{N}$ such that $n, m \geq N_{3}$ implies $d(x_{n}, x_{m}) < \frac{1}{2^{3}}$.  If we let $n_{3} = \max \{ n_{2}, N_{3} \} + 1$, then clearly $n_{3} > n_{2}$ and if $n, m \geq n_{3}$, then $d(x_{n}, x_{m}) < \frac{1}{2^{3}}$.
Note that because $n_{1} < n_{2} < n_{3} < \dots$ by our construction, and since we picked $n_{i}$ such that $d(x_{n}, x_{m}) < \frac{1}{2^{i}}$ if $n, m \geq n_{i}$, AND $n_{i + 1}, n_{i} \geq n_{i}$, it follows that $d(x_{n_{i + 1}}, x_{n_{i}}) < \frac{1}{2^{i}}$.
