# How to prove from scratch that there exists $q^2\in(n,n+1)$?

Given $n$ a positive integer, how would you prove from scratch that there exists a rational number $q$ such that $n<q^2<n+1$?

By "from scratch" I mean by not using any "advanced" tools like the density of the rational numbers in the real numbers. Just using the definition of rational numbers, how to prove that?

I faced this problem while trying to verify that the Dedekind cut $(A,B)$ cannot be determined by a rational number, where:

• $B=\{x \in Q^+: x^2>2\}$

• $A=Q\setminus B$

where $Q^+$ denotes the positive rationals.

So, for the purposes of the problem, I still don't even know what the real numbers are.

• Are we allowed to use the archimedian property? – gambler101 Sep 28 '16 at 18:21
• @JonathanRichardLombardy yes – Cauchy Sep 28 '16 at 18:22

As $1<(\frac54 )^2<2<(\frac32 )^2<3$, we may assume wlog. that $n\ge 3$.

With $q=\frac ab$, our task is to find $a,b$ such that $nb^2<a^2<(n+1)b^2$. Pick $b=2n^2$; so we want $4n^5<a^2<4n^5+4n^4$. The set $\{\,k\in\Bbb N\mid k^2>4n^5\,\}$ is a non-empty (contains $3n^3$) subset of $\Bbb N$, hence has a minimal element $a$. Clearly, $a>2n^2>1$. Then $$(a-1)^2=a^2-2a+1>a^2\left(1-\frac 2a\right)>a^2\left(1-\frac 1{n^2}\right)$$ If we assume $a^2\ge 4n^5+4n^4$, this leads to $$(a-1)^2>4n^5+4n^4-4n^3-4n^2=4n^5+4n^2((n-1)^2-2)>4n^5$$ contradicting minimality of $a$. Hence $a^2<4n^5+4n^4$, as desired.

One idea: It's easy enough to find a $q_0 \in \mathbb{Q}$ that satisfies $q_0^2 > n$. Now use Newton's method to approximate a solution to $q^2 - n = 0$. This gives a recurrence $$q_{i+1} = q_i - \frac{q_i^2 - n}{2q_i}.$$ It can be shown that $$q_{i+1}^2 - n = \left(\frac{q_i^2 - n}{2q_i}\right)^2 \le \frac{q_i^2 - n}{4}$$ so that eventually $q_i^2 - n < 1$.

• This method is very good in OP's context since it avoids refering to irrational numbers. – Olivier Moschetta Sep 28 '16 at 18:50
• @OlivierMoschetta agreed. I picked Hagne's answer because it's very easy to follow. Though I up-voted this (thank you by the way) – Cauchy Sep 28 '16 at 18:56

Notice that for $n > 4$

$$n\sqrt{n + 1} - n \sqrt{n} = \frac{n}{\sqrt{n + 1} + \sqrt{n}}\geq \frac{n}{2\sqrt{n + 1}} > 1$$

so there is an integer $k$ such that

$$n\sqrt{n} \leq k <n \sqrt{n + 1}$$ so

$$n \leq \frac{k^2}{n^2} <n + 1$$ hence $q := \frac{k}{n}$ is a rational number with the property you are looking for.

The problem is reduced to showing that there exists a rational number between $\sqrt{n}$ and $\sqrt{n+1}$.

Let $q=a/b$ where $a,b\in\mathbb{N}$ (as $\sqrt n >0)$.

Archimedian property (modified) : Given any real number $y>0$ there exists an $n\in\mathbb{N}$ such that $1/n<y$.

Thus there exists an integer $b$ with $\frac 1b <\sqrt{n+1}-\sqrt n$. We can pick another integer $a$ such that $a-1\le b\sqrt n<a$. Now $\sqrt n<\sqrt{n+1}-1/b\Rightarrow b\sqrt n<b\sqrt{n+1}-1\Rightarrow b\sqrt{n+1}>b\sqrt{n}+1\ge a$. Thus $\sqrt{n+1} >a/b$.

Now from choice of $a$ we conclude that $a/b>\sqrt{n}$.