Every Cauchy sequence has a subsequence with the property $d(y_{p+1}, y_{q+1})\le d(y_p, y_q)/2$ 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.
 A: 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: 


*

*$\operatorname{dist}(y_k, Tx_m)$ is nondecreasing with $m$, and is not always zero — otherwise $y_k$ would be equal to $x$.

*$\operatorname{diam} Tx_m$ is nonincreasing and tends to zero, because $(x_n)$ is Cauchy.


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