A pattern sequence approach to Stern’s sequence

AbstractSuppose that w∈1{0,1}∗ and let aw(n) be the number of occurrences of the word w in the binary expansion of n. Let {s(n)}n⩾0 denote the Stern sequence, defined by s(0)=0, s(1)=1, and for n⩾1, s(2n)=s(n),ands(2n+1)=s(n)+s(n+1). In this note, we show that s(n)=a1(n)+∑w∈1{0,1}∗s([w¯]2)aw1(n) where w¯ denotes the complement of w (obtained by sending 0↦1 and 1↦0) and [w]2 denotes the integer specified by the word w∈{0,1}∗ interpreted in base 2