mathschallenge.net logo

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,
    1. bcad=1.
    2. when a new fraction of the form, (a+c)/(b+d), is inserted, then a/b less than (a+c)/(b+d) less than 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+5times19=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 bcminusad=1.

    Clearly it is true for F1 = {0/1, 1/0}: 1times1–0times0 = 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)]:
    b(a+c)–a(b+d) = ab+bcabad = bcad = 1

    Case 2 [(a+c)/(b+d) and c/d]:
    c(b+d)–d(a+c) = bc+cdadcd = bcad = 1

    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) greater than 0.

    Therefore, b(a+c) greater than a(b+d), (a+c)/(b+d) greater than a/b.

    Similarly, from c(b+d)–d(a+c) = 1, we get, c/d greater than (a+c)/(b+d).

    Hence, a/b less than (a+c)/(b+d) less than c/d.

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

Only Show Problem