A pattern sequence approach to Stern's sequence

作者：Coons Michael; Shallit Jeffrey^*

来源：Discrete Mathematics, 2011, 311(22): 2630-2633.

DOI：10.1016/j.disc.2011.07.029

• Stern sequence
• Pattern sequence expansion

Suppose that w is an element of 1{0, 1}* and let a(w)(n) be the number of occurrences of the word in 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), and s(2n + 1) = s(n) s(n + 1).
In this note, we show that
s(n) = a(1)(n) + Sigma(w is an element of 1{0, 1}*) S([(w) over bar](2))a(w1) (n)
where (w) over bar denotes the complement of w (obtained by sending 0 -> 1 and 1 -> 0) and [w](2) denotes the integer specified by the word w is an element of {0, 1}* interpreted in base 2.

• 出版日期2011-11-28