# Prove that given any rational number there exists another greater than or equal to it that differs by less than $\frac 1n$

I am currently attempting to prove a claim in Hardy's Course of Pure Mathematics and am currently stuck. I was hoping that someone would be able to provide some assistance on how to go about this.

Claim: Given any rational number r and any positive integer $n$, there exists a rational number on either side of $r$ and differing from $r$ by less than $\frac1n$.

My Proof so far: Any rational number can be written as the ratio of two integers. Let $r = \frac pq$ According to the claim, there exists another rational number, which we will call $r'$ that differs from $r$ by less than $\frac 1n$ Therefore, this can be written as: $|r'- r| < \frac 1n$

And this is where I had become stuck at.

-
Unless I am misunderstanding, you want to prove such an $r^\prime$ exists. You do not yet know it exists. – Austin Mohr Nov 19 '12 at 4:20
$s:=\frac{p}{q}\pm\frac{1}{2n}$, $|s-\frac{p}{q}|<\frac{1}{n}$. – anon Nov 19 '12 at 4:32
I know this is way late, but I prefer letting $s = \frac{2np+1}{2nq}$, with $q \geq 1$ an integer, and then $|r-s| = \frac{1}{2nq} < \frac{1}{n}$. – Brian Tung Nov 26 '15 at 3:20

Here is a sketch of one way to approach this problem.

Let a rational number $r$ and a tolerance $\frac{1}{n}$ be given. We want to produce another rational number that differs from $r$ by less than $\frac{1}{n}$.

Take any rational number $s$ greater than $r$. Let $d = s - r$ (the distance between $s$ and $r$). Define another rational number $r_1 = \frac{1}{2}(r + s)$. One can show that $r_1$ is indeed a rational number and has distance $\frac{d}{2}$ from $r$.

If $r_1$ is close enough to $r$ (i.e. if $\frac{d}{2}< \frac{1}{n}$), we can stop. Otherwise, define $r_2 = \frac{1}{2}(r + r_1)$. As before, $r_2$ is a rational number, but its distance from $r$ is $\frac{d}{4}$.

Continue producing these new rational numbers via $r_{k+1} = \frac{1}{2}(r + r_k)$ until one of them is close enough to $r$ (which is guaranteed to occur, since $\frac{d}{2^k} < \frac{1}{n}$ for some $k$).

-
Yep, you have your r and you have $r\pm 1/n$ on either side so just take their midpoint. Since r is rational, $r\pm 1/n$ is rational and hence the midpoint is rational. Done! – Fixed Point Nov 19 '12 at 4:43
This process of making sequences is instructive, maybe, but the answer provided by anon in the comments is much quicker and uses all the same assumptions, as far as I can tell. – Austin Mohr Nov 19 '12 at 4:49