Content deleted Content added
No edit summary |
→Method of proof: add proof outline for the pigeonhole principle |
||
Line 16:
==Method of proof==
===Proof By The Pigeonhole Principle===
This theorem is a consequence of the [[pigeonhole principle]]. [[Peter Gustav Lejeune Dirichlet]] who proved the result used the same principle in other contexts (for example, the [[Pell equation]]) and by naming the principle (in German) popularized its use, though its status in textbook terms comes later.<ref>http://jeff560.tripod.com/p.html for a number of historical references.</ref> The method extends to simultaneous approximation.<ref>{{Springer|id=d/d032940|title=Dirichlet theorem}}</ref>
'''Proof Outline''': Let <math>\alpha</math> be a rational number and <math>n</math> be an integer. For every <math>k=0, 1, ..., n</math> we can write <math>k\alpha=m_k + x_k</math> such that <math>m_k</math> is an integer and <math>0\le x_k <1</math>.
One can divide the interval <math>[0, 1)</math> into <math>n</math> smaller intervals of measure <math>\frac{1}{n}</math>. Now, we have <math>n+1</math> numbers <math>x_0,x_1,...,x_n</math> and <math>n</math> intervals. Therefore, by the pigeonhole principle, at least two of them are in the same interval. We can call those <math>x_i,x_j</math> such that <math>i < j</math>. Now:
: <math>|(j-i)\alpha-(m_j-m_i)|=|j\alpha-m_j-(i\alpha-m_i)|=|x_j-x_i|\le \frac{1}{n}</math>
Dividing both sides by <math>j-i</math> will result in:
: <math>\left|\alpha-\frac{m_j-m_i}{j-i}\right|\le \frac{1}{(j-i)n}\le \frac{1}{\left(j-i\right)^2}</math>
And we proved the theorem.
===Proof By Minkowski's theorem===
Another simple proof of the Dirichlet's approximation theorem is based on [[Minkowski's theorem]] applied to the set
|