$\lim_{n\to\infty} \frac{n}{a_n} = \lim_{x\to\infty} \frac{1}{x}\sharp \{n \leq x: n \in A\}$ when the limit exists.

This question is about natural density $d(A) = \lim_{x\to\infty}\frac{1}{x}\sharp\{n \leq x: n \in A\}$. I'm trying to prove that when either that limit or this limit:

$\lim_{n\to \infty} \frac{n}{a_n}$ exists, then the other exists and they're equal.

I've got, working backwards, that I'm trying to prove $\forall \epsilon \gt 0, \exists n_{\epsilon} : \forall n \geq n_{\epsilon}, |\frac{n}{a_n} - d(A)| \lt \epsilon$. But I'm not seeing what to do next.

($a_n$ is the ordered sequence that is $A$: $a_1 \lt a_2 \lt \dots$. In other words take the set $A$ and retrieve its elements in order to generate the sequence.)

• Take care of $x$ in $a_n < x < a_{n+1}$. – Sungjin Kim Aug 19 '15 at 22:02

For $A$ finite, $d(A) = 0$ and $\lim_{n\to \infty} \frac{n}{a_n}$, let a finite sequence be defined such that $a_k = 0$ for all remaining indexes $k$. Done.

For $A$ infinite, thanks to i707107's comment, I considered $$a_{n-1} \lt x \leq a_{n}$$ ie. for every $x$ there exists an $n$ such that the above holds since $A$ is infinite in number of elements. So let $x = m \in \Bbb{N}$, then write:

$$m \leq a_{n}$$

Since $x \gt 0$ (we're concerned only with $x \to +\infty$) we have $\frac{m}{a_n} \leq 1$.

We need an example. Say $A = {1, 3, 7, 11, 17, \dots}$

Then as $x$ takes on values from $\Bbb{N}$, the sequence is: $$1/1, 2/3, 4/7, 5/7, 6/7, 7/7, 8/11, 9/11, \dots$$

In other words this approach wont work. What we did learn though is that $n \leq a_n \implies \frac{n}{a_n} \leq 1$. Which is more importantly, a decreasing bounded sequence (bounded below by $0$) so has a limit.

I can't seem to prove what this limit equals though.