# A Cauchy sequence has a rapidly Cauchy subsequence

I am trying to fill in the details of a proof related to the Riesz-Fischer Theorem. We need to show that every Cauchy sequence $\{f_n\}$ has a rapidly Cauchy subsequence. My text claims that we can inductively choose a strictly increasing sequence of natural numbers $\{n_k\}$ for which

$$\|f_{n_{k+1}}-f_{n_k}\|\le (1/2)^k.$$

I am not sure how that induction process goes.

MY ATTEMPT: Let $k\in\mathbb{N}$ and since $\{f_n\}$ is Cauchy, there exists $n_k$ such that for all $m'>n_k$ we have $\|f_{m'}-f_{n_k}\|\le (1/4)^k$ and there exists $n_{k+1}$ such that for all $m''>n_{k+1}$ we have $\|f_{m''}-f_{n_{k+1}}\|\le (1/4)^{k+1}$. Thus for all $m>\max\{n_k,n_{k+1}\}$ we have $$\|f_{n_{k+1}}-f_{n_k}\|=\|f_{n_{k+1}}-f_m+f_m-f_{n_k}\|\le\|f_{n_{k+1}}-f_m\|+\|f_m-f_{n_k}\|<(1/4)^{k+1}+(1/4)^k<(1/2)^k.$$

I am not convinced that $\{n_k\}$ sequence I choose is strictly increasing. Am I on the right track?

Yes, basically your idea is correct, but so far it is not an induction (you choose $n_k$ and $n_{k+1}$ in one step whereas in the induction, $n_k$ is given). Let's show that we can choose a strictly increasing sequence $(n_k)_{k \in \mathbb{N}}$ such that $$\|f_{n_{k+1}}-f_{n_k}\| \leq \frac{1}{2^k} \tag{1}$$ and $$\|f_{n_k}-f_n\| \leq \frac{1}{2^{k+1}} \tag{2}$$ for all $n \geq n_k$.

Say we have already chosen $n_1,\ldots,n_k$ for some $k \in \mathbb{N}$. Since $(f_n)_{n \in \mathbb{N}}$ is a Cauchy sequence, there exists $N \in \mathbb{N}$ such that for all $m,n \geq N$:

$$\|f_m-f_n\| \leq \frac{1}{2^{k+2}}. \tag{3}$$

Choose $n_{k+1} := m > \max\{N,n_k\}$. Then

$$\|f_{n_{k+1}}-f_{n_k}\| \leq \underbrace{\|f_{n_{k+1}}-f_n\|}_{\stackrel{(3)}{\leq} \frac{1}{2^{k+2}}} + \underbrace{\|f_n-f_{n_k}\|}_{\stackrel{(2)}{\leq} \frac{1}{2^{k+1}}} \leq \frac{1}{2^k}$$

for all $n \geq n_{k+1}$ and, by (3),

$$\|f_{n_{k+1}}-f_n\| \leq \frac{1}{2^{k+2}}$$

for all $n \geq n_{k+1}$. This shows that (1) and (2) are satisfied (for $k+1$).