A pattern sequence approach to Stern’s sequence

Suppose that w∈1{0,1}∗w∈1{0,1}∗ and let aw(n)aw(n) be the number of occurrences of the word ww in the binary expansion of nn. Let {s(n)}n⩾0{s(n)}n⩾0 denote the Stern sequence, defined by s(0)=0s(0)=0, s(1)=1s(1)=1, and for n⩾1n⩾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 ww (obtained by sending 0↦10↦1 and 1↦01↦0) and [w]2[w]2 denotes the integer specified by the word w∈{0,1}∗w∈{0,1}∗ interpreted in base 22.