Stern-Brocot Tree
0/1 is a fraction while 1/0 is not. However, using it as such helps describe a way to get all possible positive fractions arranged in a very nice manner. So disguising 1/0 as a fraction has a very good excuse.
We already know how to obtain the mediant of two given fractions. The mediant of two fractions m1/n1 and m2/n2 is, by definition, the fraction
A remarkable thing about Stern-Brocot tree is that it contains all possible non-negative fractions expressed in lowest terms and each exactly once. Just to remind, a fraction m/n is in lowest terms iff m and n are coprime, i.e, iff gcd(n,m) = 1. To prove this we'll need a series of facts of which the following is the most fundamental: if m1/n1 and m2/n2 are two consecutive (consecutive in the sense that one of them is a direct descendant of the other) fractions at any stage of the construction then
(1) | m2n1 - m1n2 = 1 |
This relation is true for the initial fractions: 1·1 - 0·0 = 1. Also, assuming (1) holds for two fractions m1/n1 and m2/n2, their mediant should satisfy the following two:
n1(m1 + m2) - (n1 + n2)m1 = 1, and
m2(n1 + n2) - (m1 + m2)n2 = 1
both of which are equivalent to (1).
Also, if m1/n1 < m2/n2 then
m1/n1 < (m1 + m2)/(n1 + n2) < m2/n2 ,
from which it follows that the construction of the tree preserves the natural order between the rationals. Therefore, it's impossible to obtain the same fraction twice.
And there is the last point: let a/b be a fraction in lowest terms with a and b positive. I wish to show that this fraction will appear somewhere on the tree. So long as it did not, we shall have
m1/n1 < a/b < m2/n2
for a couple of fractions m1/n1 and m2/n2 satisfying (1). These are rewritten as
n1a - m1b > 0 and m2b - n2a > 0,
which imply
n1a - m1b ≥ 1 and m2b - n2a ≥ 1.
from where
(m2 + n2)(n1a - m1b) + (m1 + n1)(m2b - n2a) ≥ m1 + n1 + m2 + n2.
An application of (1) yields
a + b ≥ m1 + n1 + m2 + n2.
with inevitable conclusion that after at most a+b steps of computing mediants one of them will be equal to a/b.
P.S.
Prof. W.McWorter has offered the following clarification to the proof:
At the root of the tree the minimum numerator-denominator sum (nd sum) is 2. At the first level of the tree the minimum nd sum is 3, and at the n-th level of the tree the minimum nd sum is
Thus, if a/b is a fraction in lowest terms not equal to any fraction in the tree, then it lies strictly between two consecutive fractions, one of which is at level a+b-1 of the tree (consecutive here is restricted to all fractions constructed up to and including level
Remark
Pierre Lamothe from Canada informed me recently of a property of the Stern-Brocot tree I was unaware of. Pierre discovered that property in his research on music and harmony.
Let's associate with any irreducible fraction p/q the number
Row number | Tree members | Sum of simplicities | ||
---|---|---|---|---|
0 | 1/1 | 1/1 | ||
1 | 1/2, 2/1 | 1/2 + 1/ 2 | ||
2 | 1/3, 2/3, 3/2, 3/1 | 1/3 + 1/6 + 1/6 + 1/3 | ||
3 | 1/4, 2/5, 3/5, 3/4, 4/3, 5/3, 5/2, 4/1 | 1/4 + 1/10 + 1/15 + 1/12 + 1/12 + 1/15 + 1/10 + 1/4 |
The inductive proof is based on a fact (proved on later pages) that, for any fraction p/q, two fractions
w(p/(p + q)) + w((p + q)/q) = 1/p(p+q) + 1/q(p + q) = 1/pq = w(p/q),
from which it follows that if the assertion holds for one row, it holds for the next one as well.
Pierre also introduced another function W defined for the members of the tree. For an irreducible fraction p/q, Let N(p/q) denote the row of the tree that contains p/q. We start with
W(p/q) = w(p/q)·2-N(p/q)-1
From the previous statement it then follows that the sum of all weighted simplicities of the fractions on the tree is equal to 1!
References
- R.Graham, D.Knuth, O.Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
- Brian Hayes, Computing Science On the Teeth of Wheels, American Scientist, July-August, Volume 88, No. 4,
- Modular Arithmetic
- Chinese Remainder Theorem
- Euclid's Algorithm
- Pick's Theorem
- Fermat's Little Theorem
- Wilson's Theorem
- Euler's Function
- Divisibility Criteria
- Examples
- Equivalence relations
- A real life story
|Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny
72010195