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.
 A: 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.
A: 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$.
A: 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.
A: 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}$.
Please notify about any errors committed.  
