mathschallenge.net

Problem

Starting with F₁={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₁={0/1, 1/1}
F₂={0/1, 1/2, 1/1}
F₃={0/1, 1/3, 1/2, 2/3, 1/1}
F₄={0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1}
F₅={0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1}
F₆={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.

1. What fraction is the immediate predecessor of 2/5 in F₁₀₀?
2. Given that a/b and c/d are two consecutive fractions in F_n, prove,
   1. bc–ad=1.
   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 F₅, 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 F₁₀₀ no denominator exceeds 100, and as 3+519=98, we can deduce that m=19. Hence the immediate predecesor of 2/5 in F₁₀₀ will be 39/98.

   What will be the successor of 2/5 in F₁₀₀?

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

   Clearly it is true for F₁ = {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 = 1

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

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