Does the sequence $(\frac{1}{n})_{n=1}^\infty$ converge to $0$ effectively?

Question

Question: Does the sequence $(\frac{1}{n})_{n=1}^\infty$ converge to $0$ effectively?

The definition of effective convergence that I am using is:

There exists a computable function $e:\mathbb{N}\to \mathbb{N}$ such that for any $N,$ $$k\geq e(N) \quad\text{implies}\quad |\frac{1}{k}|<2^{-N}.$$

I think the sequence converges to $0$ effectively. However, I am unable to find such recursive function $e.$ In real analysis, one can find $N$ by using Archimedean property.

Answer 1

You're thinking much too hard about this: the sequence does indeed converge to $0$ effectively, and we can find an "effective modulus" $e$ by ... just thinking about how the sequence behaves. For completeness let me recall the fully general definition of effective convergence:

A sequence $(a_k)_{k\in\mathbb{N}}$ effectively converges to $c$ if there is some computable function $e$ such that for all $N$ we have $$\forall k\ge e(N),\quad \vert a_k-c\vert<2^{-N}.$$

• We have: our sequence is $a_n={1\over n}$, and the value it's (hopefully!) effectively converging to is $c=0$.

• We want: A function $e$ such that for all $N$ we have $$\forall k\ge e(N),\quad\vert a_k-c\vert <{2^{-N}}.$$

The trick now is to not think too hard. You mention the Archimedean property, and more generally the existence of a "nonconstructive" proof of the existence of such an $e$, which obviously won't help us here; but is that really necessary? Forget about computability theory for the moment - let's just try to "solve for $e$" (or some $e$) directly.

From what we have, we can rewrite what we want as: $$\forall k\ge e(N),\quad \vert {1\over k}\vert<{1\over 2^N}.$$ Well, this suggests an immediate guess for $e(N)$ - namely, $e(N)=2^N+1$. If $k\ge 2^{N}+1$ then we have $$a_k\ge{1\over 2^N+1}$$ and of course we know that $$\vert {1\over 2^N+1}\vert<{1\over 2^N}.$$ So we probably want $e(N)=2^N+1$ (or, if you'd like, we could do something like $e(N)=3^N+17$ - overshooting isn't a problem!).

Now technically we're not yet done: we don't just want such an $e$, we want such an $e$ which is computable. But it should be clear that $N\mapsto 2^N+1$ is computable; if it's not, it's a good exercise to show this.

The following is a good motto:

Often the "obvious" bound - if such exists - is computable.

(And even if it's not, it's always a good starting point for finding a computable bound).

---

Note that actually this would be a little bit easier if we tweaked the definition of effective convergence to replace "$\ge$" with "$>$" (basically, this would get rid of the "$+1$" incongruity). It's a good exercise to show that this would yield exactly the same definition of effective convergence. Similarly, it's a good exercise to check that we could replace "$2^{-N}$" with "$3^{-N}$" or (in light of this problem) "$1\over N$" in the definition of effective convergence.