On CutTheKnot website there is an alternative proof (Prof. McWorter's Proof ) of this property of Stern-Brocot tree (that no rational numbers are omitted).
I'm having a hard time understanding the second part of this proof - how does he construct the last contradiction, how does he find those consecutive numbers (neighbours of the nonexistent a/b); does it actually contradict the first part of the proof?
Thank you in advance.
It’s not hard to check that the smallest fraction in level $n$ of the Stern-Brocot tree is $\frac1{n+1}$, and the largest is $\frac{n+1}1$. The smallest fraction in level $a+b-1$ is $\frac1{a+b}<\frac{a}b$, and the largest fraction in level $a+b-1$ is $\frac{a+b}1>\frac{a}b$. Let $F$ be the set of fractions in levels $0$ through $a+b-1$; then $|F|=\sum_{k=0}^{a+b-1}2^k=2^{a+b}-1$, and we can list $F$ in increasing order as
$$\frac1{a+b}=\frac{m_1}{n_1}<\frac{m_2}{n_2}<\ldots<\frac{m_{2^{a+b}-1}}{n_{2^{a+b}-1}}=\frac{a+b}1\;,$$
where all of the fractions with odd indices are in level $a+b-1$. Thus, there must be consecutive fractions $\frac{m_k}{n_k}$ and $\frac{m_{k+1}}{n_{k+1}}$ in $F$ such that $\frac{m_k}{n_k}<\frac{a}b<\frac{m_{k+1}}{n_{k+1}}$, and one of these fractions is in level $a+b-1$. Say that $\frac{m_k}{n_k}$ is in level $a+b-1$; then by the first paragraph at the McWhorter link $m_k+n_k\ge a+b+1$.
When the second paragraph there refers to the ‘same calculations’, it appears to be referring to the ones in the main body of the article. Specifically, we know from the fact that $\frac{m_k}{n_k}$ and $\frac{m_{k+1}}{n_{k+1}}$ are consecutive that $m_{k+1}n_k-m_kn_{k+1}=1$, so
$$\begin{align*} a+b&=a(m_{k+1}n_k-m_kn_{k+1})+b(m_{k+1}n_k-m_kn_{k+1})\\ &=am_{k+1}n_k-am_kn_{k+1}+bm_{k+1}n_k-bm_kn_{k+1}\\ &=am_{k+1}n_k\color{red}{+an_{k+1}n_k}\color{blue}{-bm_km_{k+1}}-bm_kn_{k+1}+\\ &\quad\quad+bm_{k+1}n_k\color{blue}{+bm_km_{k+1}}-am_kn_{k+1}\color{red}{-an_{k+1}n_k}\\ &=(m_{k+1}+n_{k+1})(an_k-bm_k)+(m_k+n_k)(bm_{k+1}-an_{k+1})\;. \end{align*}$$
However, $\frac{m_k}{n_k}<\frac{a}b<\frac{m_{k+1}}{n_{k+1}}$, so $an_k-bm_k\ge 1$ and $bm_{k+1}-an_{k+1}\ge 1$, so
$$a+b\ge(m_{k+1}+n_{k+1})+(m_k+n_k)>a+b+1\;,$$
which is absurd.
As it says, this is an attempt to clarify the proof that no positive rational is omitted from the tree; it’s not a substitute for that argument. The argument given in the main body of the article really is pretty minimal, and this addition seems to be an attempt to fill in more detail by showing by exactly which point in the construction of the tree we can be assured of having found $\frac{a}b$.