## Farey Sequence

#### Problem

Starting with F_{1}={0/1, 1/1}, F_{n} is generated by comparing adjacent fractions in F_{n–1}: `a/b` and `c/d`. If `b`+`d`=`n`, then the mediant, (`a`+`c`)/(`b`+`d`), is placed between them. Consider the first six sets:

F_{1}={0/1, 1/1}

F_{2}={0/1, **1/2**, 1/1}

F_{3}={0/1, **1/3**, 1/2, **2/3**, 1/1}

F_{4}={0/1, **1/4**, 1/3, 1/2, 2/3, **3/4**, 1/1}

F_{5}={0/1, **1/5**, 1/4, 1/3, **2/5**, 1/2, **3/5**, 2/3, 3/4, **4/5**, 1/1}

F_{6}={0/1, **1/6**, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, **5/6**, 1/1}

Remarkably, F_{n} represents the ordered list of reduced fraction for which the denominator does not exceed `n`, and is called the Farey sequence.

- What fraction is the immediate predecessor of 2/5 in F
_{100}? - Given that
`a/b`and`c/d`are two consecutive fractions in F_{n}, prove,`bc`–`ad`=1.- when a new fraction of the form, (
`a`+`c`)/(`b`+`d`), is inserted, then`a/b`(`a`+`c`)/(`b`+`d`)`c/d`.

#### Solution

- We note that 2/5 first makes its appearance in F
_{5}, with 1/3 being its immediate predecessor. The next fraction to appear between them will be (1+2)/(3+5)=3/8. As we are considering fractions to the left of 2/5, it can be seen that for each new fraction, the numerator continues to increase by 2 and the denominator increases by 5. Moreover, because we know that 1/3 was to the left, each new fraction will be of the form (1+2`m`)/(3+5`m`).In F

_{100}no denominator exceeds 100, and as 3+519=98, we can deduce that`m`=19. Hence the immediate predecesor of 2/5 in F_{100}will be 39/98.What will be the successor of 2/5 in F

_{100}? - Given two consecutive fractions,
`a/b`and`c/d`, we are hoping to prove that`bc``ad`=1.Clearly it is true for F

_{1}= {0/1, 1/0}: 11–00 = 1.Let us assume that

`bc`–`ad`=1 is true for all elements in F_{k}, and let us consider F_{k+1}. If no fraction is inserted then it follows that`bc`–`ad`=1 is still true.If a new fraction, of the form (

`a`+`c`)/(`b`+`d`), is inserted, then we must consider two cases.Case 1 [

`a/b`and (`a`+`c`)/(`b`+`d`)]:`b`(`a`+`c`)–`a`(`b`+`d`) =`ab`+`bc`–`ab`–`ad`=`bc`–`ad`= 1Case 2 [(

`a`+`c`)/(`b`+`d`) and`c/d`]:`c`(`b`+`d`)–`d`(`a`+`c`) =`bc`+`cd`–`ad`–`cd`=`bc`–`ad`= 1In other words, if it is true for F

_{k}it is true for F_{k+1}, and as it is true for F_{1}, inductively we show that it is true for all sets.As we have just shown that

`b`(`a`+`c`)–`a`(`b`+`d`) = 1, it follows that`b`(`a`+`c`)–`a`(`b`+`d`) 0.Therefore,

`b`(`a`+`c`)`a`(`b`+`d`), (`a`+`c`)/(`b`+`d`)`a/b`.Similarly, from

`c`(`b`+`d`)–`d`(`a`+`c`) = 1, we get,`c/d`(`a`+`c`)/(`b`+`d`).Hence,

`a/b`(`a`+`c`)/(`b`+`d`)`c/d`.