A Digit Reversal Property for an Analogue of Stern’s Sequence

Lukas Spiegelhofer^{1} Institute of Discrete Mathematics and Geometry Vienna University of Technology Wiedner Hauptstraße 8–10 Wien Austria

                lukas.spiegelhofer@tuwien.ac.at

Abstract We consider a variant of Stern’s diatomic sequence, studied recently by Northshield. We prove that this sequence b is invariant under digit reversal in base 3, that is, b(n) = b(n^{R}), where n^{R} is obtained by reversing the base-3 expansion of n.

1 Introduction

Stern’s diatomic sequence s is defined by s(0) = 0, s(1) = 1 and

s(2n) = s(n), s(2n + 1) = s(n) + s(n + 1)

for all n ≥ 1. Northshield [13] introduced the following analogue having values in ℤ[\sqrt{2}]: b(0) = 0, b(1) = 1 and

b(3n) = b(n),
b(3n + 1) = τ · b(n) + b(n + 1),
b(3n + 2) = b(n) + τ · b(n + 1)

1The author acknowledges support by the Austrian Science Fund (FWF), project F5502-N26, which is a part of the Special Research Program “Quasi Monte Carlo Methods: Theory and Applications”.

for n ≥ 0, where τ = \sqrt{2}. The first values of the sequence b are therefore as follows.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ b(n) & 0 & 1 & \sqrt{2} & 1 & 2\sqrt{2} & 3 & \sqrt{2} & 3 & 2\sqrt{2} & 1 & 3\sqrt{2} & 5 & 2\sqrt{2} & 7 \\ n & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 \\ b(n) & 5\sqrt{2} & 3 & 4\sqrt{2} & 5 & \sqrt{2} & 5 & 4\sqrt{2} & 3 & 5\sqrt{2} & 7 & 2\sqrt{2} & 5 & 3\sqrt{2} & 1 \end{matrix}

(for a longer list consult Northshield’s paper [13], for example). Northshield proved that

lim sup_{n→∞} \frac{2b(n)}{(2n)^{log_{3}(\sqrt{2}+1)}} ≥ 1

(where log_{3} denotes the base-3 logarithm) and conjectured that equality holds. This conjecture was recently proved by Coons [3], using the method employed by Coons and Tyler [5]. The same method was also used in the paper by Coons and the author [4].

Considering the first values of Northshield’s sequence, we note the following apparent symmetry, proved by Northshield [13]: b(3^{k} + m) = b(3^{k+1} − m) for m ≤ 3^{k}. Moreover, a less apparent property is present, which is the subject of this paper: for example, we have b(11) = b(19) = 5 and b(29) = b(55) = 7. The indices on both sides of these identities are related via digit reversal in base 3. More precisely, for the proper base-q expansion of an integer n ≥ 1, n = ε_{ν}q^{ν} + ⋯ + ε_{0}, we define n^{R} = ε_{0}q^{ν} + ⋯ + ε_{ν−1}q^{1} + ε_{ν}. (We will always indicate the base in which the digit reversal is performed.) We are going to prove the following theorem.

Theorem 1. We have

b(n) = b(n^{R}),

where the digit reversal is performed in base 3.

In fact, we prove the more general Theorem 2 below. For the Stern sequence s, such a digit reversal property (in base 2) was found by Dijkstra and given as a problem in the Nieuw Archief voor Wiskunde [7]. Moreover, Dijkstra [6, pp. 230–232] restated and proved this property, writing fusc(n) instead of s(n). It can be seen as the statement that the continued fractions [k_{0}; k_{1}, …, k_{r}] and [k_{r}; k_{r−1}, …, k_{0}] have the same numerator. The close connection between Stern’s sequence and continued fractions is well known. We refer the reader to the articles by Lehmer [10], Lind [11], Stern [15] and also to the book by Graham, Knuth, and Patashnik [9, Exercise 6.50]: if n = (1^{k_{0}}0^{k_{1}} ⋯ 1^{k_{r−2}}0^{k_{r−1}}1^{k_{r}})_{2}, then s_{n} is the numerator of the continued fraction [k_{0}; k_{1}, …, k_{r}].

Morgenbesser and the author [12] proved an analogous digit reversal property for the correlation

γ_{t}(ϑ) = lim_{N→∞} \frac{1}{N} ∑_{0≤n<N} e(ϑσ_{q}(n + t) − ϑσ_{q}(n)),

where e(x) = exp(2πix) and σ_{q}(n) is the sum of digits of n in base q (q ≥ 2 an integer). That is, we proved that γ_{t}(ϑ) = γ_{t^{R}}(ϑ), where the digit reversal is in base q. We note that the quantity γ_{t}(ϑ) satisfies the following recurrence, proved by Bésineau [2]: γ_{0}(ϑ) = 1 and for 0 ≤ k < q and t ≥ 0,

γ_{qt+k}(ϑ) = \frac{q − k}{q} e(ϑk)γ_{t}(ϑ) + \frac{k}{q} e(−ϑ(q − k))γ_{t+1}(ϑ).  (1)

We will use this recurrence later. With the help of these correlations, we proved that c_{t} = c_{t^{R}}, where

c_{t} = lim_{N→∞} \frac{1}{N} |\{n < N : σ_{2}(n + t) ≥ σ_{2}(n)\}|

and the digit reversal is in base 2. These quantities arise in a seemingly simple conjecture due to Cusick (private communication, 2015) stating that c_{t} > 1/2; see the paper [8] by Drmota, Kauers, and the author for partial results on this conjecture.

Moreover, the author [14] recently proved a digit reversal property for Stern polynomials. In that paper, we define polynomials s_{n}(x, y) by s_{1}(x, y) = 1 and

\begin{aligned}s_{2n}(x, y) & = s_{n}(x, y) \\ s_{2n+1}(x, y) & = xs_{n}(x, y) + ys_{n+1}(x, y) \end{aligned}  (2)

for n ≥ 1 and prove that s_{n^{R}}(x, y) = s_{n}(x, y), where the digit reversal is in base 2. We note that this is a generalization of the case q = 2 from the above-cited paper by Morgenbesser and the author, and also implies the digit reversal symmetry for Stern’s diatomic sequence.

The recurrence relations for the sequences discussed above imply that we are dealing with q-regular sequences in the sense of Allouche and Shallit [1], where q ∈ {2, 3} and the underlying rings are ℤ, ℤ[\sqrt{2}], ℂ, and ℤ[x, y] respectively.

2 Results

We will derive the digit reversal property stated in the introduction as a corollary of the following theorem.

Theorem 2. Let q ≥ 2 be an integer. Assume that (x(n))_{n≥0} is a sequence of complex numbers having the following properties:

1. There exist complex 2 × 2-matrices A(0), …, A(q − 1) and complex numbers α, β such that for all n ≥ 1 we have the representation

x(n) = (1 , 0)A(ε_{0}) ⋯ A(ε_{ν−1}) (\begin{matrix}α \\ β \end{matrix}) ,

where (ε_{ν−1} ⋯ ε_{0})_{q} is the proper q-ary expansion of n.

2. Write

A(ε) = (\begin{matrix}a_{1}(ε) & a_{2}(ε) \\ a_{3}(ε) & a_{4}(ε) \end{matrix}) .

There exist complex numbers a ≠ 0, b ≠ 0, c, d such that ad − bc = 1 and

ab(a_{1}(ε)β − a_{3}(ε)α − a_{4}(ε)β) + a_{2}(ε)(β + 2bcβ − cdα) = 0  (3)

for all ε ∈ {0, …, q − 1}.

Then x(n) = x(n^{R}), where the digit reversal is in base q.

From this, we derive a digit reversal property for a family of (3-regular) sequences, among which we find Northshield’s sequence.

Corollary 3. Let τ, σ be complex numbers and set ω = 1−σ^{2}+τσ. Assume that the sequence (a(n))_{n≥0} satisfies a(0) = 0, a(1) = 1, and for n ≥ 0, a(3n) = a(n) and

a(3n + 1) = τ · a(n) + a(n + 1),
a(3n + 2) = ω · a(n) + σ · a(n + 1).

Then a(n) = a(n^{R}), where the digit reversal is in base 3.

In particular, τ = σ = \sqrt{2} yields Theorem 1.

Proof of Corollary 3. We note that we can express the sequence a in the form given in the theorem: set A(0) = ( \begin{matrix}1 & 0 \\ τ & 1 \end{matrix} ) , A(1) = ( \begin{matrix}τ & 1 \\ ω & σ \end{matrix}) , A(2) = ( \begin{matrix}ω & σ \\ 0 & 1 \end{matrix} ). Then

(a(3n + ε) , a(3n + ε + 1)) = A(ε) (\begin{matrix}a(n) \\ a(n + 1) \end{matrix})

for all n ≥ 0 and ε ∈ {0, 1, 2}. Choosing α = a(0) = 0 and β = a(1) = 1, we see that the first condition in Theorem 2 is satisfied. To verify equation (3), we set

(\begin{matrix}a & b \\ c & d \end{matrix}) = ( 1 1_{\frac{σ−τ−1}{2} \frac{σ−τ+1}{2}})

and evaluate the left hand side of (3) for each of the three matrices A(ε). This yields 0 in each case after a short calculation.

Moreover, we want to re-prove the known digit reversal properties presented in the introduction. Whereas the proof of Corollary 4 is essentially the same as the one given by Morgenbesser and the author [12], the proof of Corollary 5 is different from the one given by the author [14].

Corollary 4. Let ϑ ∈ ℝ and assume that

γ_{t}(ϑ) = lim_{N→∞} \frac{1}{N} ∑_{0≤n<N} e(ϑσ_{q}(n + t) − ϑσ_{q}(n))

for all integers t ≥ 0. Then γ_{t}(ϑ) = γ_{t^{R}}(α).

Proof. Set

A(ε) = (\begin{matrix}\frac{q−ε}{q} e(ϑε) & \frac{ε}{q} e(−ϑ(q − ε)) \\ \frac{q−ε−1}{q} e(ϑ(ε + 1)) & \frac{ε+1}{q} e(−ϑ(q − ε − 1)) \end{matrix})

and α = γ_{0}(ϑ) = 1, β = γ_{1}(ϑ) = (q − 1)/(q e(−ϑ) − e(−ϑq)). Then by (1) the first condition in Theorem 2 is satisfied. As in the paper [12] by Morgenbesser and the author, set

(\begin{matrix}a & b \\ c & d \end{matrix}) = (\begin{matrix}1 & \overline{β} \\ 0 & 1 \end{matrix}) .

Inserting these values into (3) completes the proof after a straightforward calculation.

Corollary 5. Assume that x and y are complex numbers and that the sequence (z(n))_{n≥0} satisfies z(2n) = z(n) and z(2n + 1) = xz(n) + yz(n + 1) for all n ≥ 1. Then z(n) = z(n^{R}), where the digit reversal is in base 2. In particular, Stern’s diatomic sequence and the Stern polynomials defined by equation (2) satisfy a digit reversal symmetry.

Proof. Without loss of generality we may assume that z(1) = 1. The general case follows from rescaling the sequence z if z(1) ≠ 0; if z(1) = 0, then z(n) = 0 for all n ≥ 1 and the statement is trivial. Moreover, we may assume that x, y ∉ {0, 1}. For the other cases, note that z(n), for a given n, depends in a continuous way on both x and y, so that the statement follows by approximation.

Set A(0) = ( \begin{matrix}1 & 0 \\ x & y \end{matrix} ) and A(1) = ( \begin{matrix}x & y \\ 0 & 1 \end{matrix} ) and α = (1 − y)/x, β = 1. Then z satisfies the first condition in Theorem 2. Let γ be a root of 4γ^{2} = \frac{y}{x} \frac{1−y}{1−x} and set

(\begin{matrix}a & b \\ c & d \end{matrix}) = (\begin{matrix}γ & 1 \\ −\frac{1}{2} & \frac{1}{2γ} \end{matrix} ) .

The verification of (3) is straightforward.

3 Proof of Theorem 2

We closely follow the proof of Theorem 1 in the paper [12] by Morgenbesser and the author. Consider the 2 × 2 matrix S = ( \begin{matrix}a & b \\ c & d \end{matrix}) and the following property: Assume that ν ≥ 0 and ε_{i} ∈ {0, …, q − 1} for 0 ≤ i < ν. Then

(a , 0)S^{−1}A(ε_{0}) ⋯ A(ε_{ν−1}) (\begin{matrix}α \\ β \end{matrix}) = (1 , 0)A(ε_{ν−1}) ⋯ A(ε_{0})S (\begin{matrix}dα − bβ \\ 0 \end{matrix})

and

(0 , b)S^{−1}A(ε_{0}) ⋯ A(ε_{ν−1}) (\begin{matrix}α \\ β \end{matrix}) = (1 , 0)A(ε_{ν−1}) ⋯ A(ε_{0})S (\begin{matrix}0 \\ −cα + aβ \end{matrix}) ,

where the empty product is to be interpreted as the identity matrix. Summing these equations and noting that (a , b)S^{−1} = (1 , 0) and S(dα−bβ , −cα+aβ)^{T} = (α , β)^{T}, which follows from ad − bc = 1, we obtain the statement of Theorem 2.

We will show the above identities by induction on ν. For ν = 0 we have (a , 0)S^{−1}(α , β)^{T} = (1 , 0)S(dα − bβ , 0) and (0 , b)S^{−1}(α, β)^{T} = (1 , 0)S(0 , −cα + aβ)^{T}, which is trivial to check. Assume now that ν ≥ 1. We set

(\begin{matrix}𝔞 \\ 𝔟 \end{matrix}) = S^{−1}A(ε_{1}) ⋯ A(ε_{ν−1}) (\begin{matrix}α \\ β \end{matrix}) and (𝔞′ , 𝔟′) = (1 , 0)A(ε_{ν−1}) ⋯ A(ε_{1})S.

By the induction hypothesis we obtain

a𝔞 = (dα − bβ)𝔞′ and b𝔟 = (−cα + aβ)𝔟′.  (4)

We need to show that

(a, 0)S^{−1}A(ε_{0})S (\begin{matrix}𝔞 \\ 𝔟 \end{matrix}) = (𝔞′ , 𝔟′)S^{−1}A(ε_{0})S (\begin{matrix}dα − bβ \\ 0 \end{matrix})  (5)

and

(0, b)S^{−1}A(ε_{0})S (\begin{matrix}𝔞 \\ 𝔟 \end{matrix}) = (𝔞′ , 𝔟′)S^{−1}A(ε_{0})S (\begin{matrix}0 \\ −cα + aβ \end{matrix}) .  (6)

For brevity, we set

(\begin{matrix}s_{1}(ε) & s_{2}(ε) \\ s_{3}(ε) & s_{4}(ε) \end{matrix}) = S^{−1}A(ε)S.

It is easily seen, using (4) and the restrictions a ≠ 0, b ≠ 0, that each of equations (5) and (6) follows from

a(−cα + aβ)s_{2}(ε_{0}) = b(dα − bβ)s_{3}(ε_{0}).  (7)

Noting that s_{2}(ε) = bda_{1}(ε) + d^{2}a_{2}(ε) − b^{2}a_{3}(ε) − bda_{4}(ε) and s_{3}(ε) = −aca_{1}(ε) − c^{2}a_{2}(ε) + a^{2}a_{3}(ε) + aca_{4}(ε) and using ad − bc = 1, (7) reduces to (3) after some short calculation. This finishes the proof of Theorem 2.

References

[1] J.-P. Allouche and J. Shallit. The ring of k-regular sequences. Theoret. Comput. Sci. 98 (1992), 163–197.

[2] J. Bésineau. Indépendance statistique d’ensembles liés à la fonction “somme des chiffres”. Acta Arith. 20 (1972), 401–416.

[3] M. Coons. Proof of Northshield’s conjecture concerning an analogue of Stern’s sequence for ℤ[\sqrt{2}]. Preprint, 2017, available at http://arxiv.org/abs/1709.01987.

[4] M. Coons and L. Spiegelhofer. The maximal order of hyper-(b-ary)-expansions. Electron. J. Combin. 24 (2017), Paper 1.15.

[5] M. Coons and J. Tyler. The maximal order of Stern’s diatomic sequence. Mosc. J. Comb. Number Theory 4 (2014), 3–14.

[6] E. W. Dijkstra. Selected Writings on Computing: a Personal Perspective. Texts and Monographs in Computer Science. Springer-Verlag, 1982.

[7] E. W. Dijkstra. Problem 563. Nieuw Arch. Wisk. 27 (1980), 115.

[8] M. Drmota, M. Kauers, and L. Spiegelhofer. On a conjecture of Cusick concerning the sum of digits of n and n + t. SIAM J. Discrete Math. 30 (2016), 621–649.

[9] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics: a Foundation for Computer Science. Addison-Wesley, 1989.

[10] D. H. Lehmer. On Stern’s diatomic series. Amer. Math. Monthly 36 (1929), 59–67.

[11] D. A. Lind. An extension of Stern’s diatomic series. Duke Math. J. 36 (1969), 55–60.

[12] J. F. Morgenbesser and L. Spiegelhofer. A reverse order property of correlation measures of the sum-of-digits function. Integers 12 (2012), Paper No. A47.

[13] S. Northshield. An analogue of Stern’s sequence for ℤ[\sqrt{2}]. J. Integer Sequences 18 (2015), Article 15.11.6.

[14] L. Spiegelhofer. A digit reversal property for Stern polynomials. Preprint, 2017, available

    at http://arxiv.org/abs/1610.00108.

[15] M. A. Stern. Ueber eine zahlentheoretische Funktion. J. reine Angew. Math. 55 (1858), 193–220.

2010 Mathematics Subject Classification: Primary 11A63; Secondary 11B75. Keywords: Stern’s diatomic sequence, digit reversal.

(Concerned with sequences \underline{A002487}, \underline{A277749}, and \underline{A277750}.)

Received September 17 2017; revised version received November 30 2017. Published in Journal of Integer Sequences, December 20 2017.

Return to Journal of Integer Sequences home page.