Farey Series

Let m₁/n₁ and m₂/n₂ be two successive terms of F_N. Then

(1)	m₂n₁ - m₁n₂ = 1

For three successive terms m₁/n₁, m₂/n₂, and m₃/n₃, the middle term is the mediant of the other two

(2)	m₂/n₂ = (m₁ + m₃)/(n₁ + n₃)

To prove that (1) implies (2), assume we have two identities

(3)	m₂n₁ - m₁n₂ = 1 m₃n₂ - m₂n₃ = 1

Subtract one from the other and recombine the terms:

(4)	(m₃ + m₁)n₂ = m₂(n₃ + n₁)

which leads to (2). Manipulating linear equalities should be working both ways. I'll try to reverse the flow of reasoning from (2) to (1). To prove that (2) implies (1), I'll use mathematical induction.

Assume we are given a series of fractions m_i/n_i, I=1,2,..., with the condition that any three consecutive terms satisfy

(2')	m_i/n_i = (m_i- 1 + m_i+1)/(n_i- 1 + n_i+1)

I want to show that for such a series (1) also holds. But (1) contains only two fractions. Therefore, let's assume that for I=2 (1) indeed holds. This is clearly true for F_N which starts with 0/1, 1/N, ... Assume that for some I > 2

(1')	m_in_i- 1 - m_i- 1n_i = 1

Rewrite (2') as

(4')	(m_i+1 + m_i- 1)n_i = m_i(n_i+1 + n_i- 1)

Subtracting (4') from (1') easily gives
(1') m_i+1n_i - m_in_i+1 = 1

which would appear to complete our inductive proof. Does it mean that the Farey series is infinite? After all, this is what mathematical induction is good for: proving properties of a infinite sequence of successive integers. Let's try to continue the Farey series beyond 1/1.

Consider, for example, F₅ whose last two terms are 4/5 and 1/1. We are looking for a fraction m/n such that (4 + m)/(5 + n) = 1/1. The solution is obviously 5/4. The next fraction should solve the equation (1 + m)/(1 + n) = 5/4. The solution is 4/3. A pattern seems to emerge. The new numbers are the very terms of the Farey series F₅ written upside down and left to right.

0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1, 5/4, 4/3, 3/2, 5/3, 2/1, 5/2, 3/1, 4/1, 5/1, 1/0

The fact becomes obvious when we notice that equations (3)-(4) are symmetric with respect to the indices 1 and 3. They may be solved for m₁/n₁ as well as for m₃/n₃. Equations (3)-(4) also do not change if we turn the fractions involved upside down. Once the first step beyond 1/1 is made, all others are forced to follow symmetrically their left-side-of-1/1 counterparts.

1/0 is a forbidden fraction. However, since it follows ... (N-1)/1, N/1 at the end of the Farey series F_N, there is a good reason to agree that no harm will come from calling it infinity: 1/0 = . This is a big number, indeed. Can we carry our inductive process beyond infinity? No, the process breaks down. Trying to solve (N + m)/(1 + n) = 1/0 leads to n = -1 and an arbitrary m. Is anything wrong with our induction? How come we did not get an infinite sequence of terms?

To answer these questions we have to analyze the proof step by step.

Pick's Theorem
- Pick's Theorem, A Proof
- Farey Series
- Pick's Theorem Applies to the Farey Series
- Stern-Brocot Tree

(4') implies (2') only when n_i0. Division by 0 is employed in other arithmetic "paradoxes".

So the induction did not go through. Does this mean that our proof was wrong? No, it does not. We did proof that, for the Farey series (a series that starts with 0/1 and 1/N), condition (2) implies (1). However, our inductive reasoning (carrying from step "I" to the next step "I+1") broke down just after a finite number of steps. The upshot is that it applies to every Farey series F_N. An additional insight comes from looking down the Stern-Brocot tree.