© h.hofstede (h.hofstede@hogeland.nl)

De Stern-Brocot boom.
       
Dit is een alternatieve manier om breuken op te schrijven.

Het gaat zo:   begin met de breuken 0/1 en 1/0    (OK, ik weet ook wel dat die laatste geen echte breuk is, maar laten we even doen alsof, en hem voor zolang even ∞ noemen)

Zet daar de breuk tussenin die je krijgt door de tellers op te tellen en de noemers ook  (dat heet de mediant van beide breuken).
Zet daarna tussen elke twee breuken weer op dezelfde manier een nieuwe breuk.
Dus tussen de breuken  a/b  en  c/d  komt steeds de breuk  (a + c)/(b + d)
Ga zo alsmaar door.....

Dat geeft de volgende breukenrijen:
       
       
Enzovoorts.
(De "nieuwelingen"  in een rij vergeleken met de vorige rij zijn steeds rood;  alhoewel ik ze als groentjes eigenlijk groen had moeten maken natuurlijk).

Als je het nou ook nog op een beetje mooie systematische manier noteert krijg je een soort van boom vol breuken:  De Stern-Brocot boom.
       

       
Bedenk dat hier onderaan dus eigenlijk van klein naar groot (van links naar rechts)  de volgende breukenrij staat:
 0/1 - 1/5 - 1/4 - 2/7 - 1/3 - 3/8 - 2/5 - 3/7 - 1/2 - 4/7 - 3/5 - 5/8 - 2/3 - 5/7 - 3/4 -  enz.

Het leuke is:  daar komen alle rationale getallen uiteindelijk precies één keer in voor! En ook nog allemaal in de meest vereenvoudigde vorm!
't Is gewoon een mooie manier om ze systematisch allemaal te noemen.

En als je een breuk uit de boom bekijkt, dan geeft de tak vanaf  1/1 erheen een steeds nauwkeuriger benadering van die breuk.  Zo kun je bijvoorbeeld  5/8 steeds nauwkeuriger benaderen met de serie  1/1 - 1/2 - 2/3 - 3/5 - 5/8 

Soort van stamboom?
       
Je kunt deze boom als een soort stamboom zien. Dan heeft een breuk twee kinderen en een ouder.
Zo heeft  3/4  als kinderen  5/7 en 4/5  en andersom heeft  8/5 als ouder 5/3.  Zie de figuur.

Dan is er een onverwacht verband tussen de kinderen en hun ouders, en dat heeft weer te maken met kettingbreuken!
Even je geheugen opfrissen:  de kettingbreuk {a0;  a1, a2, a3....}  wordt gegeven door:
       

       
In deze les staat daarover meer.
Nou is zo'n kettingbreuknotatie niet eenduidig: 
De breuk  {a0;  a1, a2, a3, ...an, 1)  is hetzelfde als   {a0;  a1, a2, a3, ...,an + 1)   immers  an + 1/1 = an + 1
Als je dat nou gebruikt om ervoor te zorgen dat het laatste getal uit de kettingbreuk groter dan 1 is,
dan is  {a0; a1 , a2, ..., an - 1} in de stamboom de "ouder"  van   {a0; a1 , a2, ..., an}

voorbeeld.

{2; 1,1}  is dan de ouder daarvan:

Klopt! Kijk maar in de boom.
       
En andersom kun je ook de kinderen uit de ouders produceren:
De ouder   {a0;  a1, a2, a3, ...an, 1)  heeft kinderen   {a0;  a1, a2, a3, ...an, 2)    en   {a0;  a1, a2, a3, ...an + 2}
       
Omdat de breuken in de boom van links naar rechts steeds groter worden (dat komt natuurlijk door het nemen van de mediant) kun je in één keer het pad van de boom berekenen dat naar een bepaalde breuk toeloopt (dus al zijn voorouders langsgaan).

Hier is een voorbeeldje:
Stel dat we het pad naar  8/13 zoeken, dan gaan we die 8/13 gewoon steeds verder inklemmen:
• Zoek tussen de grenzen  0/1 en 1/0
De mediant daarvan is  1/1 en dat is groter dan 8/13 vervang de grens 1/0 door 1/1
• Zoek tussen de grenzen 0/1 en 1/1
De mediant daarvan is 1/2 en dat is kleiner dan 8/13;  vervang de grens 0/1 door 1/2
• Zoek tussen de grenzen 1/2 en 1/1
De mediant daarvan is  2/3 en dat is groter dan 8/13;  vervang de grens 1/1 door 2/3.
Enzovoorts.
Dat geeft het pad:   1/1  →  1/2  →  3/5 →  5/8 →  8/13
Zo kun je aan elke breuk een soort code toekennen van hoe je er in de boom vanaf  1/1 komt:  R = naar rechts, L = naar links).  8/13 zou dan code LRRL hebben.
Zo krijg je een soort binaire code voor een breuk (in plaats van L en  R kun je net zo goed 0 en 1 nemen).


Hoe weet je eigenlijk dat alle breuken er in voorkomen?
       
Dat er geen dubbelen in voorkomen is direct te zien door het feit dat   a/b  <  (a + c)/(b + d)  <  c/d
■  Kijk maar:
 

Omdat a/c < b/d  is de teller van die laatste breuk kleiner dan de noemer, dus is die hele laatste breuk kleiner dan 1,  dus is het totale eindresultaat kleiner dan c/d
Op precies dezelfde manier volgt dat de mediant groter is dan a/b.

Dus je vindt steeds een breuk tussen twee breuken in, die allemaal op volgorde van klein naar groot staan, dus er kan geen dubbele zijn.
■      
       
Nou geldt er tussen ouder-kind paar  a/b en  c/d  van deze boom (en dus tussen elke twee opeenvolgende breuken van een breukenrij)  de erg nuttige relatie:
       

bc - ad = 1
       
Daarbij is  a/b de kleinere breuk van de twee.
 
■ Het bewijs daarvan gaat makkelijk met volledige inductie:
  stap 1:  het geldt voor  0/1 → 1/0  want  1 • 1 - 0 • 0 = 1  
stap 2:  stel dat het voor twee breuken uit een bepaalde  rij geldt (inductie-aanname),  bc - ad = 1
  Kijk nu welke breuken in de volgende rij verschijnen:
De mediant van  a/b en c/d  is  (a + c)/b + d) en die verschijnt nieuw.
Dus de twee opeenvolgende breuken in de volgende rij zijn dan  a/b  en   (a + c)/(b + d)
Dan zou moeten gelden  (a + c) • b - a(b + d) = 1
Dat is hetzelfde als  ab + bc - ab - ad = 1  ofwel  bc - ad = 1  en dat klopte volgende de inductie-aanname.
Ofwel:  die eigenschap blijft gelden!!!
■      
       
Daarmee hebben we trouwens en-passant meteen aangetoond dat alle breuken uit de boom niet meer te vereenvoudigen zijn, zie je dat?
Immers als (a + c) en (b + d) beiden deelbaar door n zouden zijn, dan is b(a + c) - a(b + d)  ook deelbaar door n, maar we zagen net dat dat 1 is, dus dat kan niet!!
       
Terug naar de hoofdvraag graag!!

Stel dat a/b  nog niet in de breukenrij voorkomt.
Dan zijn er dus twee breuken waar a/b tussen in ligt (noem de tellers daarvan  t1,2 en de noemers n1,2).

Het eerste kleiner-dan-teken betekent dat  n1a  >  t1b
Het tweede kleiner-dan-teken betekent  n2a  <  t2b 
Maar omdat het om allemaal gehele getallen gaat betekent dat, dat   n1a - t1b ≥  1  en ook dat t2b  - n2a  ≥ 1
•  Daaruit volgt    (t2 + n2)(n1a - t1b)   ≥  t2 + n2   en  (t1 + n1)(t2b - n2a)  ≥  t1 + n1
•  Tel die bij elkaar op:   (t2 + n2)(n1a - t1b)  + (t1 + n1)(t2b - n2a)  ≥  t1 + n1 +  t2 + n2
•  Haakjes wegwerken:    t2n1a - t2t1b + n2n1a - n2t1b + t1t2b - t1n2a + n1t2b - n1n2a  ≥  t1 + n1 +  t2 + n2
•  Het gekleurde valt weg:  t2n1a - n2t1b - t1n2a + n1t2b ≥  t1 + n1 +  t2 + n2
•  a(t2n1 - t1n2)  +  b(n1t2 - n2t1)  ≥  t1 + n1 +  t2 + n2
Maar die stukken tussen haakjes zijn vanwege die interessante eigenschap bc - ad = 1  hierboven beiden gelijk aan 1.

Dus geldt   a +  b ≥  t1 + n1 +  t2 + n2

Maar in de loop van de boom worden  t1, n1, t2 en  n2  alsmaar groter (er worden alleen maar tellers en noemers bij elkaar opgeteld!). Dus op een gegeven moment zal die rechterkant van de ongelijkheid altijd groter dan a + b worden, en kan deze ongelijkheid niet meer kloppen dus kan a/b  niet meer tussen twee breuken van de boom in liggen.
Het moet dan wel een breuk van de boom zelf zijn!!

q.e.d.

(overigens heeft de Stern-Brocot boom erg veel te maken met de Farey-rijen uit deze les....)
       

© h.hofstede (h.hofstede@hogeland.nl)