Ana səhifə

Farey Sequences Definition


Yüklə 23.4 Kb.
tarix24.06.2016
ölçüsü23.4 Kb.

Farey Sequences




Definition

A Farey sequence is a complete sequence of reduced form rational fractions in the range of the form with for . The sequence is complete in the sense that, given a Farey sequence as defined above, we can find no rational fraction with such that .



Theorem

Given a Farey sequence , the following equality holds for :



where , , , .

Proof

Proof is by induction. For , we have the trivial Farey sequence where the above equality holds for . Given a Farey sequence , the sequence comprises a merge of and the sequence . If some is not in reduced form then it can be represented as a reduced form rational fraction with . But this fraction will already be a member of since is complete. Thus only reduced form fractions will be members of and will be merged with . The merge is such that all elements of are inserted in their correct position in the sequence in order to produce . (This observation enables an algorithm for the construction of for any to be designed.)


The complete proof will use the following 4 lemmas.

Lemma 1


There exists integers ,, and such that for

Proof

Choose . It is easy to verify that .


Lemma 2

After merging, no two consecutive members of will be consecutive members of . Thus we can always find some fraction such that and where .




Proof

This follows directly from Lemma 1 since .




Lemma 3

Given a Farey sequence , for any , .



Proof

This follows directly from the theorem .




This applies for all and can be applied successively to create a sequence .
But and hence for .
From Lemma 2 we have some such that are consecutive members of and where and are consecutive members of and is in reduced form.
Consider the rational fractions . We can prove the following lemma.


Lemma 4






Proof



Assume



which follows from Lemma 3. But
Since is an integer, our original assumption is false and . Since , because there is no rational fraction such that as is complete.
The second equality can be proved using a similar technique

Assume



which follows from Lemma 3. But
Since is an integer, our original assumption is false and . Since , because there is no rational fraction such that as is complete.
This proves Lemma 4.

From Lemmas 3 and 4, the proof of the theorem follows directly.




This shows that the rational fraction inserted into obeys the equality given in the Theorem. However, we still have to consider preceding values to check whether the Theorem is generally applicable to .


There are 2 possibilities:and where are consecutive terms in sequence .

Taking the first possibility,



for some integer .
because

Thus the equality holds for when is the third term in the triplet. An identical proof shows that the equality holds when is the first term of the triplet and so



Taking the second possibility ,

for some integer .



Thus the equality holds in this case also.
We have thus proved by induction that if the equality holds for , then it must hold for which completes the proof of the Theorem.


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©atelim.com 2016
rəhbərliyinə müraciət