stern-diatomic-sequence.md

Start with the row 1 1. Between every two neighbours write their sum, and leave the old numbers where they are: 1 2 1. Do it again and the row becomes 1 3 2 3 1. Once more gives 1 4 3 5 2 5 3 4 1. Each row keeps the one before it and fills every gap with the sum of the two numbers on either side.

Read the rows one after another, dropping the 1 that ends each row because the next row starts with it, and you get one sequence: s(1) = 1, then 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1 and on, with s(0) = 0 set in front by convention. Row k fills the places from 2^k to 2^(k+1). The same numbers come from a rule with no rows at all: s(2n) = s(n) and s(2n + 1) = s(n) + s(n + 1). Doubling a place moves a number to the same spot in the next row, which is why old numbers stay put, and the odd place in between gets the sum of its two neighbours. For example s(11) = s(5) + s(6) = 3 + 2 = 5.

The figure draws rows 0 to 7 as bars, one row under another, each bar set at its own fraction of the way across, so a number keeps its place when the next row slips new ones in beside it. Each row is scaled so its tallest bar reaches the same height, and those tallest bars are yellow.

Every row reads the same backwards, since the rule treats left and right alike. Its largest number runs 1, 2, 3, 5, 8, 13, 21, 34, from 3 on each the sum of the two before it: the Fibonacci numbers. Its total runs 2, 4, 10, 28, 82, one more than a power of 3 each time. That one is quick to see: a new row adds a sum for every gap, and those sums count every old number twice except the two 1s at the ends, so the new total is three times the old one minus 2.

The sequence also counts something. Write a whole number as a sum of powers of 2, 1, 2, 4, 8 and so on, using each power at most twice. The number 4 can be written three ways, 4, 2 + 2 and 2 + 1 + 1, and s(5) = 3. The number 10 can be written five ways, 8 + 2, 8 + 1 + 1, 4 + 4 + 2, 4 + 4 + 1 + 1 and 4 + 2 + 2 + 1 + 1, and s(11) = 5. In general the count for n is s(n + 1). The reason is the same halving: an odd number must use exactly one 1, and what is left is twice a way of writing half of it, while an even number uses no 1s or two, so its count is the sum of two smaller counts, exactly as in the rule.

Two neighbours in the sequence never share a divisor bigger than 1. Each pair of neighbours is the pair at half the place with one number added to the other, and adding one number to another never changes what divides both, so the question passes down the sequence until it reaches s(0) = 0 and s(1) = 1. That means the fraction s(n)/s(n + 1) is always in lowest terms. Starting at n = 1 the fractions run 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4/1, and every positive fraction turns up in this list exactly once.

Calkin and Wilf 2000 see why with a tree. Put 1/1 at the root and give every fraction a/b two children, a/(a + b) on the left and (a + b)/b on the right. Reading the tree row by row gives exactly the list above, because s(2n)/s(2n + 1) and s(2n + 1)/s(2n + 2) are the two children of s(n)/s(n + 1). Climbing back up is subtracting the smaller of top and bottom from the larger, which is Euclid's algorithm, and for a fraction in lowest terms it always ends at 1/1 along one path. So every such fraction sits at exactly one node.

The same fractions appear again, row by row in a different order, in the Stern-Brocot tree. It starts from two seeds, 0/1 and 1/0, which are not part of the tree. Each new fraction is the mediant of the nearest two already written on either side of it, the tops added and the bottoms added, so the root is 1/1 and the next row is 1/2 and 2/1. Every row lists its fractions from smallest to largest. The fractions below 1 in it are the ones the Farey sequence builds by mediants. Northshield 2010 collects these facts and many more with short proofs.

In the tree

Dilated stacks finds this sequence as the receptive field of a stack of three-tap convolutions spaced 1, 2, 4 and on: over the first half of its reach, the paths that reach back n steps are the ways of writing n above, so there are s(n + 1) of them, with the Fibonacci numbers as the peaks. Beneath a design reads the Calkin-Wilf and Stern-Brocot rows as a base-2 design whose cells carry the pair s(n), s(n + 1), one 2 by 2 table multiplied in per binary digit. The mediant step is the one the Farey sequence grows by, and each mediant stands under the circle that fills the gap between two touching Ford circles. Neighbours sharing no divisor is the greatest common divisor run backwards, and the Thue-Morse sequence is built by the same halving, one bit flipped where this one adds.