Stern Brocot tree sequence

Question

For every positive real number, there exists an infinite sequence in the Stern Brocot tree (beggining at its root 1/1) that converges to the real number.

Can you please help me find the proof of this theorem?

My idea is to use the fact that every real number is present exactly once in the tree, and there are theoretically infinitely many ways how to "create" the branch, however I do not know how to proof the convergence.

Answer 1

Prerequisite / recommended reading:

• Stern-Brocot tree
• Computing Ancestors of # for Stern-Brocot Tree

For every positive real number, there exists an infinite sequence in the Stern Brocot tree [ .. ] that converges to the real number. And the OP asks us to prove this.
Without loss of generality, attention shall be restricted to the (open) interval $]0,1[$. So let $0 \lt g \lt 1$ such a real number. For numbers $g > 1$, simply take $1/g < 1$ and turn fractions upside down in the end. At a certain level in the tree we have fractions with numerators $(m_1,m_2)$ and denominators $(m_2,n_2)$ such that: $$ \frac{m_1}{n_1} \lt g \lt \frac{m_2}{n_2} $$ Lemma. $$ m_2 n_1 - m_1 n_2 = 1 $$ Proof by mathematical induction.
The tree is rooted by the fractions $0/1$ and $1/1$, hence: $1\cdot 1 - 0\cdot 1 = 1$. And it may be continued in exactly two ways, namely
1. By tightening the lower bound $m_1/n_1$: $$ \frac{m_1+m_2}{n_1+n_2} \lt g \lt \frac{m_2}{n_2} \quad \Longrightarrow \quad m_2(n_1+n_2) - (m_1+m_2)n_2 = m_2 n_1 - m_1 n_2 = 1 $$ 2. By tightening the upper bound $m_2/n_2$: $$ \frac{m_1}{n_1} \lt g \lt \frac{m_1+m_2}{n_1+n_2} \quad \Longrightarrow \quad (m_1+m_2)n_1 - m_1(n_1+n_2) = m_2 n_1 - m_1 n_2 = 1 $$ This already proves the Lemma.
In practice, the tree search for $g$ is ended when its fractional approximation is within certain error bounds: $$ \left|\, g - \frac{m_1+m_2}{n_1+n_2}\, \right| < \epsilon $$ With help of the above Lemma we easily derive: $$ \frac{m_1}{n_1} \lt g \lt \frac{m_2}{n_2} \\ \frac{m_1}{n_1} - \frac{m_1+m_2}{n_1+n_2} \lt g - \frac{m_1+m_2}{n_1+n_2} \lt \frac{m_2}{n_2} - \frac{m_1+m_2}{n_1+n_2} \\ - \frac{1}{n_1(n_1+n_2)} \lt g - \frac{m_1+m_2}{n_1+n_2} \lt \frac{1}{(n_1+n_2)n_2} $$ It follows that convergence to $g$ is quadratically with the inverse of the denominators. Another consequence is: $$ \frac{m_1}{n_1} \lt \frac{m_1+m_2}{n_1+n_2} \lt \frac{m_2}{n_2} $$ That's where the name mediant comes from.
The above may be implemented in a computer program. The sample code below is written in my favorite programming language (Delphi) Pascal. An approximation is sought for $g = \ln(2)/\ln(3)$, which indeed is a real number between zero and one.

program proef23;

procedure Stern_Brocot(getal,eps : double);
{
  Walk through Stern-Brocot tree
  until |fraction - getal| < eps
}
var
  m1,m2,n1,n2,m,n : integer;
begin
{ Initialize tree }
  m1 := 0; n1 := 1;
  m2 := 1; n2 := 0;
  m := m1+m2; n := n1+n2;
  while true do
  begin
    if getal < (m1+m2)/(n1+n2) then
  { Tightening }
    begin
    { Upper Bound }
      m2 := m1+m2;
      n2 := n1+n2;
    end else begin
    { Lower Bound }
      m1 := m1+m2;
      n1 := n1+n2;
    end;
    Writeln(m1/n1:12:10,' = ',m1,'/',n1,
    ' < ',getal:12:10,' < ',m2,'/',n2,' = ',m2/n2:12:10);
    m := m1+m2; n := n1+n2;
    if abs(getal - m/n) < eps then Break;
  end;
  Writeln;
  Writeln('-1/',n1*n,' < ',getal:12:10,' - ',m,'/',n,' < 1/',n*n2);
end;

begin
  Stern_Brocot(ln(2)/ln(3),1.E-6);
end.

Output:

0.0000000000 = 0/1 < 0.6309297536 < 1/1 = 1.0000000000
0.5000000000 = 1/2 < 0.6309297536 < 1/1 = 1.0000000000
0.5000000000 = 1/2 < 0.6309297536 < 2/3 = 0.6666666667
0.6000000000 = 3/5 < 0.6309297536 < 2/3 = 0.6666666667
0.6250000000 = 5/8 < 0.6309297536 < 2/3 = 0.6666666667
0.6250000000 = 5/8 < 0.6309297536 < 7/11 = 0.6363636364
0.6250000000 = 5/8 < 0.6309297536 < 12/19 = 0.6315789474
0.6296296296 = 17/27 < 0.6309297536 < 12/19 = 0.6315789474
0.6304347826 = 29/46 < 0.6309297536 < 12/19 = 0.6315789474
0.6307692308 = 41/65 < 0.6309297536 < 12/19 = 0.6315789474
0.6307692308 = 41/65 < 0.6309297536 < 53/84 = 0.6309523810
0.6308724832 = 94/149 < 0.6309297536 < 53/84 = 0.6309523810
0.6309012876 = 147/233 < 0.6309297536 < 53/84 = 0.6309523810
0.6309148265 = 200/317 < 0.6309297536 < 53/84 = 0.6309523810
0.6309226933 = 253/401 < 0.6309297536 < 53/84 = 0.6309523810
0.6309278351 = 306/485 < 0.6309297536 < 53/84 = 0.6309523810
0.6309278351 = 306/485 < 0.6309297536 < 359/569 = 0.6309314587
-1/511190 < 0.6309297536 - 665/1054 < 1/599726