Approximation of irrationals by fractions If $\alpha$ is an irrational, and I'm trying to judge the suitability of of a rational $p/q$ as its approximation by the error $\Delta = |\alpha - p/q|$. For a given denominator $q$, I am finding a $p$ for which the error $\Delta$ is minimized. Why is this error "certainly less than $1/2q$ " ?
 A: Fix denominator $q$. If $\alpha -p/q$ is greater than $\frac{1}{2q}$ than $\frac{(p+1)}{q}$ is a better approximation.
[EDIT] Equality is impossible since $\alpha$ is assumed irrational.
A: You can find approximations with error less than $\frac{1}{q^2}$ with continued fractions. The following can be proven with a simple pigeonhole proof.
Approximation Lemma: Let $x$ be any real number and $N$ be a positive integer.
Then there are integers $p$ and $q$ with $0 < q \le N$ so that $|p - qx| < \frac{1}{N}$.
Proof: Break up the unit interval $[0,1)$ into $N$ equal subintervals.  Notice
which subinterval contains the residues $\pmod{1}$ of $kx$ for $0\le k\le N$.  There
are $N+1$ residues distributed among $N$ subintervals; thus, there must be at
least one subinterval with at least two residues, $(k_1 x - j_1)$ and
$(k_2 x - j_2)$.  We may assume that $k_2 > k_1$.  Let $q = k_2 - k_1$ and
$p = j_2 - j_1$, then $0 < q \le N$ and, because both residues are in the same
subinterval, $|p - qx| = |(k_1 x - j_1) - (k_2 x - j_2)| < \frac{1}{N}$.  QED
