A calculational approach to path-based properties of the Eisenstein-Stern and Stern-Brocot trees via matrix algebra

Abstract

This paper proposes a calculational approach to prove properties of two well-known binary trees used to enumerate the rational numbers: the Stern-Brocot tree and the Eisenstein-Stern tree (also known as Calkin-Wilf tree). The calculational style of reasoning is enabled by a matrix formulation that is well-suited to naturally formulate path-based properties, since it provides a natural way to refer to paths in the trees. Three new properties are presented. First, we show that nodes with palindromic paths contain the same rational in both the Stern-Brocot and Eisenstein-Stern trees. Second, we show how certain numerators and denominators in these trees can be written as the sum of two squares $x^2$ and $y^2$, with the rational $x/y$ appearing in specific paths. Finally, we show how we can construct Sierpiński’s triangle from these trees of rationals.

Publication
In Journal of Logical and Algebraic Methods in Programming, 85(5), pp. 906-920
Avatar
Alexandra Mendes
Assistant Professor

My research focuses on innovative user interfaces for formal methods and mathematical approaches to software quality. I am also interested on innovative and fun ways to teach Computer Science. For more details, see selected publications and some of my projects. Follow me on Twitter or add me on LinkedIn.