## Farey Sequence

#### Problem

Starting with F1={0/1, 1/1}, Fn is generated by comparing adjacent fractions in Fn–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:

F1={0/1, 1/1}
F2={0/1, 1/2, 1/1}
F3={0/1, 1/3, 1/2, 2/3, 1/1}
F4={0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1}
F5={0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1}
F6={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, Fn represents the ordered list of reduced fraction for which the denominator does not exceed n, and is called the Farey sequence.

1. What fraction is the immediate predecessor of 2/5 in F100?
2. Given that a/b and c/d are two consecutive fractions in Fn, prove,
2. when a new fraction of the form, (a+c)/(b+d), is inserted, then a/b (a+c)/(b+d) c/d.

#### Solution

1. We note that 2/5 first makes its appearance in F5, 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+2m)/(3+5m).

In F100 no denominator exceeds 100, and as 3+519=98, we can deduce that m=19. Hence the immediate predecesor of 2/5 in F100 will be 39/98.

What will be the successor of 2/5 in F100?

2. Given two consecutive fractions, a/b and c/d, we are hoping to prove that bcad=1.

Clearly it is true for F1 = {0/1, 1/0}: 11–00 = 1.

Let us assume that bcad=1 is true for all elements in Fk, and let us consider Fk+1. If no fraction is inserted then it follows that bcad=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)]:

Case 2 [(a+c)/(b+d) and c/d]:

In other words, if it is true for Fk it is true for Fk+1, and as it is true for F1, 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.

Problem ID: 181 (Oct 2004)     Difficulty: 4 Star

Only Show Problem