If $a_{n+f(n)}-a_n\rightarrow 0$ as $n\rightarrow\infty\space \forall$ functions $f:\mathbb{N}\rightarrow\mathbb{N}$, is $(a_n)$ convergent?

Question

If $a_{n+f(n)}-a_n\rightarrow 0$ as $n\rightarrow\infty$ for every function $f$ from the positive integers to the positive integers, does it follow that $(a_n)$ is convergent?

I think the answer is 'yes' but I'm having a hard time proving it. I have tried to show that it is Cauchy but to no avail.

Any help is appreciated, thanks

Answer 1

Assume for the sake of contradiction that $(a_n)$ is not Cauchy. Then there is some $\varepsilon > 0$ such that for all $n \in \mathbb{N}$ there are $k,m > n$ satisfying $|a_k-a_m| \ge \varepsilon$.

For each $n = 1,2,\ldots$ choose some $k(n),m(n)$ as above and denote two functions $f,g \colon \mathbb{N} \to \mathbb{N}$ by $f(n) = k(n)-n$ and $g(n) = m(n)-n$. Then $|a_{n+f(n)}-a_{n+g(n)}| \ge \varepsilon$, but on the other hand $$ |a_{n+f(n)}-a_{n+g(n)}| \le |a_{n+f(n)}-a_{n}| + |a_{n+g(n)}-a_{n}| \xrightarrow{n \to \infty} 0, $$ which yields a contradiction.

Answer 2

It's easier to go the other way: assume $(a_n)$ is not Cauchy, and use this to build a function $f(n)$ such that $a_{n + f(n)} - a_n$ does not approach $0$.

Here, the tricky part is figuring out what "$(a_n)$ is not Cauchy" tells you. Since the definition of a Cauchy sequence is "for all $\epsilon >0$, there is an $N$ such that for all $m,n > N$, $|a_m - a_n| < \epsilon$", a non-Cauchy sequence is a sequence for which there exists some $\epsilon>0$, such that for all $N$, we can find $m,n > N$ with $|a_m - a_n| \ge \epsilon$.

We can use this to define a function $f$, as follows. Choose a value of $\epsilon>0$ for which the above is true, and:

1. Letting $N_1=1$, choose $m_1, n_1 > N_1$ (with $m_1 > n_1$) such that $|a_{m_1} - a_{n_1}| \ge \epsilon$.
2. Define $f(n_1) = m_1 - n_1$.
3. Set $N_2 = m_1 + 1$, and choose $m_2, n_2 > N_2$ (with $m_2 > n_2$) such that $|a_{m_2} - a_{n_2}| \ge \epsilon$.
4. Define $f(n_2) = m_2 - n_2$.
5. Set $N_3 = m_2 + 1$, and repeat.

This specifies some values of $f$; set $f(n)=1$ for all values we haven't specified.

This ensures that when $n = n_i$ for some $i$, $|a_{n + f(n)} - a_n| = |a_{m_i} - a_{n_i}| \ge \epsilon$. So there are infinitely many values of $n$ for which $|a_{n + f(n)} - a_n| \ge \epsilon$, and therefore $a_{n + f(n)} - a_n$ cannot converge to $0$.