Let $(X,d)$ be a metric space and let $(x_n)_{n\in\mathbb{N}}$ be an infinite Cauchy sequence on $X$. Then there exists a subsequence $(x_{n_k})_{k\in\mathbb{N}}:=(y_k)_{k\in\mathbb{N}}$ such that $$ d(y_{p+1},y_{q+1})\leq \frac{d(y_p,y_q)}{2}$$ for all $p,q\in\mathbb{N}$.
My question: how to extract such a subsequence?
Context: this answer on MO.
Let $Tx_p = \{x_k : k>p\}$ be the "tail" of $(x_k)$, and similarly for $Ty_p$. It suffices to construct $(y_k)$ such that $$ \operatorname{diam} Ty_p\le \frac12\operatorname{dist}(y_p, Ty_p)\quad \forall \ p \tag1$$ Indeed, if (1) holds then, taking WLOG $p<q$, we get $$ d(y_{p+1},y_{q+1})\leq \operatorname{diam} Ty_p\le \frac12\operatorname{dist}(y_p, Ty_p) \le \frac12 {d(y_p,y_q)} $$ as desired.
If the sequence $(x_n)$ is eventually constant, then we can make $(y_k)$ a constant sequence, which trivially satisfies (2).
Let $x = \lim x_n$ (if it exists; otherwise ignore the clauses involving $x$). Passing to a subsequence, we may assume $x_n\ne x$ for all $n$.
Let $y_1=x_1$. Suppose $y_1,\dots, y_k$ are chosen. Observe that:
So, there exists $m$ such that $\operatorname{diam} Tx_m \le \frac12 \operatorname{dist}(y_k, Tx_m)$. Let $y_{k+1}=x_{m+1}$; then $Ty_k\subset Tx_m$, which implies $$\operatorname{diam} Ty_k \le \operatorname{diam} Tx_m \le \frac12 \operatorname{dist}(y_k, Tx_m) \le \operatorname{dist}(y_k, Ty_k)$$ as desired.
The argument could be simplified by passing to the completion of $X$, where we have $x_n\to x$. Then all we need to do is pick a subsequence $y_{k}$ such that $$ 0<d(y_{k+1} , x) \le \frac16 d(y_k, x) $$ since then $\operatorname{diam} Ty_k \le \frac13d(y_k, x)$ and $$\operatorname{dist}(y_k, Ty_k)\ge \frac56 d(y_k, x) \ge 2\operatorname{diam} Ty_k$$