From: "David Wilson" <davidwwilson@comcast.net> To: "math-fun" <math-fun@mailman.xmission.com> Subject: [math-fun] Observation on Stern-Brocot tree
It appears that the sum of the nth row of the Stern-Brocot Tree is (3*2^(n-2) - 1)/2. I assume this is known, but I don't know how to prove it.
http://en.wikipedia.org/wiki/Stern-Brocot_tree seems to think the first row is the single number 1/1, so n starts at n=2? I would prefer to start at n=0 in which case change the formula to (3*2^n - 1)/2. Next row 2/1+1/2=5/2=(3*2-1)/2, check. Next 1/3+2/3+3/2+3/1=11/2=(3*4-1)/2, check. Next (3*8-1)/2=23/2. "The Stern-Brocot sequence of order i is the sequence formed by inserting a mediant between each consecutive pair of values in the Stern-Brocot sequence of order i-1." The picture in wikipedia http://en.wikipedia.org/wiki/Stern-Brocot_tree#mediaviewer/File:SternBrocotT... illustrates this, where the sequences are the horizontal rows of the picture, which include the tree nodes on that level as a subsequence, but also include additional values (on the dotted lines), and for example to obtain 3/5 on the bottom row you "add" 1/2 and 2/3. So Wilson's conjecture is equivalent to: the Nth stern-brocot sequence (ignoring the two endpoints 0/1 and 1/0) would sum to 3*2^N - 2 - N/2 beginning 1, 7/2, 9, 41/2 for N=0,1,2,3. [Because the backward difference of this formula is Wilson's.]