Polynomials Whose Coefficients Are Stern Numbers

Karl Dilcher^{1} Department of Mathematics and Statistics Dalhousie University Halifax, Nova Scotia B3H 4R2 Canada

                dilcher@mathstat.dal.ca

Larry Ericksen 1212 Forest Drive Millville, NJ 08332-2512 USA

                   LE22@cornell.edu

Abstract

The main object in this paper is the sequence of polynomials P_{n}(z) that have Stern numbers as their coefficients; that is, the terms of Stern’s diatomic sequence. We derive certain basic properties of these polynomials, investigate the distribution of their real and complex zeros, and prove some results concerning factorizations and resultants. We also consider the (0, 1)-polynomials obtained from P_{n}(z) by taking their coefficients modulo 2. In spite of its simple form, the polynomial sequence is shown to possess some interesting algebraic and analytic properties. Finally, we discuss combinatorial interpretations of the polynomials P_{n}(z) and indicate ways of generalizing them.

1Research supported in part by the Natural Sciences and Engineering Research Council of Canada, Grant # 145628481.

1 Introduction

The Stern sequence, also known as Stern’s diatomic sequence [?], is one of the most remarkable integer sequences in number theory and combinatorics. It can be defined by s(0) = 0, s(1) = 1, and

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

The first 30 Stern numbers, starting with n = 1, are

1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4.  (2)

The definition (1) gave rise to two different concepts of Stern polynomials, introduced in [?] and [?], respectively. Both preserve the “binary structure” of the sequence (1) and have various combinatorial interpretations. Subsequently these sequences of polynomials were generalized by the present authors [?], then unified as special cases of a class of polynomials in two variables [?], and more generally extended to polynomials in an arbitrary number of variables and with an underlying base b ≥ 2 [?]. All this has applications to counting and classifying restricted binary and b-ary partitions of integers.

In the current paper we will, in the first place, consider polynomials of a very different type, namely those having the Stern numbers s(n), and later some of their generalizations, as coefficients. Thus, we define

P_{n}(z) := s(1)z^{n} + s(2)z^{n−1} + ⋯ + s(n)z + s(n + 1),  (3)

and as a specific example we have, with (2),

P_{8}(z) = z^{8} + z^{7} + 2z^{6} + z^{5} + 3z^{4} + 2z^{3} + 3z^{2} + z + 4.  (4)

The polynomials P_{n}(z), as well, have a combinatorial interpretation which is related to binary overpartitions, and this leads to generalizations in different directions. The main purpose of this paper, however, is to derive various properties of the polynomials P_{n}(z) and of a closely related polynomial sequence.

In the process we will encounter combinatorial objects, including recurrence relations, Fibonacci numbers, generating functions, and various b-ary partitions. From classical analysis we will come across several well-known theorems on the distribution of zeros of polynomials, and the algebraic topics occurring in this paper include cyclotomic polynomials, resultants, and divisibility and irreducibility.

We begin in Section 2 by recalling certain properties of the Stern sequence that will be needed later, followed by some basic properties of the polynomials P_{n}(z). In Sections ?? and ?? we study the complex and real zeros, respectively, of these polynomials. Section ?? is devoted to algebraic properties of the polynomials P_{n}(z), including factors and resultants. In Section ?? we consider a (0,1)-polynomial sequence whose coefficients are those of P_{n}(z) taken modulo 2; we completely determine all factors of these polynomials and investigate their zeros. Section ?? deals with binary and b-ary overpartitions and with a combinatorial interpretation of the polynomials P_{n}(z), including some generalizations.

2 Some basic properties

In this section we derive several basic properties of the polynomials P_{n}(z), most of which will be required in later sections. We begin by recalling some easy facts about the Stern sequence.

2.1 Properties of the Stern sequence

Although at first sight the Stern sequence appears to behave rather erratically, it does in fact have a great deal of structure. First, we have the special values

s(2^{m}) = 1, s(2^{m} + 1) = m + 1, s(2^{m} + 2) = m, s(2^{m} + 3) = 2m − 1  (5)

(m ≥ 2), where the first three also hold for m = 1, and the first two for m = 0. All four identities are easy to prove by induction. The sequence s(n) is also symmetric between two powers of 2, that is,

s(2^{m} + j) = s(2^{m+1} − j),  0 ≤ j ≤ 2^{m}.  (6)

In particular, with (5), this leads to values for s(2^{m} − j), j = 1, 2, 3. Another identity that will be needed later is

s(3 · 2^{m} + 1) = s(3 · 2^{m} − 1) = 2m + 1,  m ≥ 0;  (7)

this, too, is easy to prove by induction. More properties like these are known, but they will not be needed here.

Next, combining the two identities in (1), we have s(2n + 1) = s(2n) + s(2n + 2); this implies that for n ≥ 1 each odd-index Stern number s(2n + 1) is strictly larger than its two neighbors. The Stern sequence is therefore a strict up-down sequence, beginning with the second term. This leads us to consider the ratio of neighboring terms. First, it is clear from (5) and by symmetry that ratios of neighboring terms can be arbitrarily large or arbitrarily small rational numbers. This is consistent with the well-known fact that the sequence s(n + 1)/s(n) is a one-to-one enumeration of all positive rationals; see, e.g., [?, ?].

We now show that the ratios s(n + 1)/s(n) given by the first two identities in (5), and their reciprocals, are in fact extremal in each interval between two neighboring powers of 2.

Lemma 1. For any integer m ≥ 1 we have

\frac{1}{m} ≤ \frac{s(n + 1)}{s(n)} ≤ m, where 2^{m−1} ≤ n ≤ 2^{m} − 1,  (8)

and the lower and upper bound are attained exactly when n = 2^{m} − 1 and n = 2^{m−1}, respectively.

Proof. We proceed by induction on m. The cases m = 1 and m = 2 are easily seen to be true. Suppose now that (8) holds up to some m ≥ 2, and let n be in the interval 2^{m} ≤ n ≤ 2^{m+1}−1. First, if n is even, we write n = 2k and with (1) we get

\frac{s(n + 1)}{s(n)} = \frac{s(k) + s(k + 1)}{s(k)} = 1 + \frac{s(k + 1)}{s(k)};

by the induction hypothesis we then get the upper bound m + 1. Second, if n is odd, we set n = 2k + 1 and again with (1) we get

\frac{s(n + 1)}{s(n)} = \frac{s(k + 1)}{s(k) + s(k + 1)} = \frac{1}{1 + s(k)/s(k + 1)} ≥ \frac{1}{1 + m},

having used the induction hypothesis. We also implicitly used the “up-down” property which implies that the quotients s(n+1)/s(n) alternate between greater than and less than 1. This proves (8) by induction. The final statement is clear by (5) and (6), and uniqueness comes from the one-to-one enumeration mentioned above.

We also require a remarkable property of the Stern sequence that was apparently first proved by D. H. Lehmer [?].

Lemma 2 (Lehmer). The largest value of s(n) between n = 2^{m−1} and n = 2^{m} is the Fibonacci number F_{m+1}, with the usual definition F_{0} = 0, F_{1} = 1, and F_{n+1} = F_{n} + F_{n−1}. The maximum is attained at

α_{m} := \frac{1}{3} (2^{m+1} + (−1)^{m}) and β_{m} := \frac{1}{3} (5 · 2^{m−1} − (−1)^{m}) (m ≥ 1).  (9)

\begin{matrix}m & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ α_{m} & 1 & 3 & 5 & 11 & 21 & 43 & 85 & 171 & 341 & 683 \\ β_{m} & 2 & 3 & 7 & 13 & 27 & 53 & 107 & 213 & 427 & 853 \\ F_{m+1} & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 \end{matrix}

Table 1: α_{m}, β_{m}, F_{m+1} for 1 ≤ m ≤ 10

2.2 Properties of P_{n}(z)

Now we turn to some basic properties of the polynomials P_{n}(z). First, the definition (3) immediately gives

P_{n}(z) = z · P_{n−1}(z) + s(n + 1).  (10)

By separating even and odd powers of z in (3), we obtain a different class of recurrence relations, as follows.

Lemma 3. For all n ≥ 1 we have

P_{2n}(z) = (1 + z) · P_{n−1}(z^{2}) + P_{n}(z^{2}),  (11)
P_{2n+1}(z) = z · P_{n−1}(z^{2}) + (1 + z) · P_{n}(z^{2}).  (12)

Proof. By (3) we have

P_{2n}(z) = ∑_{j=0}^{n} s(2j + 1)z^{2n−2j} + ∑_{j=1}^{n} s(2j)z^{2n+1−2j}

= ∑_{j=0}^{n} (s(j) + s(j + 1))(z^{2})^{n−j} + z ∑_{j=1}^{n} s(j)(z^{2})^{n−j}

= (1 + j) ∑_{j=0}^{n−1} s(j + 1)(z^{2})^{n−j−1} + ∑_{j=0}^{n} s(j + 1)(z^{2})^{n−j},

where we have used (1) and the fact that s(0) = 0. It is now obvious that this last line is the right-hand side of (11). The identity (12) can be obtained analogously.

The next lemma deals with some special values of P_{n}(z).

Lemma 4. For any integer m ≥ 1 we have

P_{2^{m}−1}(1) = ∑_{j=1}^{2^{m}} s(j) = \frac{1}{2} (3^{m} + 1) ,  (13)

and, for any n ≥ 1,

P_{2n}(−1) = P_{n}(1),  P_{2n+1}(−1) = −P_{n−1}(1).  (14)

Proof. It is a well-known property of the Stern sequence that

∑_{j=2^{ν}+1}^{2^{ν+1}} s(j) = 3^{ν},  ν ≥ 0;  (15)

see, e.g., [?]. Summing (15) over all ν = 0, 1, …, m − 1 and adding s(1) = 1 to both sides, we obtain (13). Finally, if we set z = −1 in (11) and (12), we immediately get the two identities in (14).

To conclude this section, we derive a generating function for the polynomials P_{n}(z).

Proposition 5. With q a complex variable, we have

∑_{n=0}^{∞} P_{n}(z)q^{n} = \frac{1}{1 − zq} ∏_{k=0}^{∞} (1 + q^{2^{k}} + q^{2^{k+1}}) .  (16)