Polynomials Characterizing Hyper b-ary Representations

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

                dilcher@mathstat.dal.ca

Larry Ericksen P. O. Box 172 Millville, NJ 08332-0172 USA

                   LE22@cornell.edu

Abstract

Given an integer base b ≥ 2, a hyper b-ary representation of a positive integer n is a representation of n as a linear combination of nonnegative powers of b, with integer coefficients between 0 and b. We use a system of recurrence relations to define a sequence of polynomials in b variables and with b parameters, and we show that all hyper b-ary representations of n are characterized by the polynomial with index n + 1. This extends a recent result of Defant on the number of hyper b-ary representations based on a b-ary analogue of Stern’s diatomic sequence. The polynomials defined here extend this numerical sequence, and they can be seen as generalized b-ary Stern polynomials.

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

1 Introduction

A hyperbinary representation of an integer n ≥ 1 is an expansion of n as a sum of powers of 2, each power being used at most twice. For instance, n = 12 can be written as

8 + 4 = 8 + 2 + 2 = 8 + 2 + 1 + 1 = 4 + 4 + 2 + 2 = 4 + 4 + 2 + 1 + 1,

so 12 has five hyperbinary representations.

A useful tool in the study of hyperbinary representations is the Stern (diatomic) sequence which 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)

This sequence, which appears in different notations in the literature, is sequence A002487 in [9], where numerous properties and references can be found. The first few nonzero terms of the sequence (1) are easily seen to be 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5,…, where those with an index that is a power of 2 are shown in bold.

The first complete connection between hyperbinary representations and the Stern sequence was established by Reznick [10, Theorem 5.2] who proved that the number of hyperbinary representations of an integer n ≥ 1 is given by the Stern number s(n + 1). For example, we have s(13) = 5, which is consistent with the introductory example. More recently, Reznick’s result was refined by the introduction of various polynomial extensions of the Stern sequence. We will return to this topic later.

In analogy to hyperbinary representations, a hyperternary representation of an integer n ≥ 1 is an expansion of n as a sum of powers of 3, each power used at most three times. The generalization of this concept to any integer base b ≥ 2 is one of the fundamental concepts of this paper.

Definition 1. For a fixed integer b ≥ 2, a hyper b-ary representation of an integer n ≥ 1 is a representation of n as a sum of powers of b, each power repeated at most b times. In other words, it is an expansion of the form

n = ∑_{j=0}^{ν} d_{j}b^{j}, 0 ≤ d_{j} ≤ b for 0 ≤ j ≤ ν, and d_{ν} ≠ 0.  (2)

Sometimes such a representation is called a base b over-expansion of the integer n; see, e.g., Defant [3].

Example 2. Let b = 3 and n = 36. Then the hyperternary representations of n are 3^{3} + 3^{2}, 3^{3} + 3 + 3 + 3, 3^{3} + 3 + 3 + 1 + 1 + 1, 3^{2} + 3^{2} + 3^{2} + 3 + 3 + 3, 3^{2} + 3^{2} + 3^{2} + 3 + 3 + 1 + 1 + 1.

Thus we have a total of five such representations, the first one being the unique representation of n in base b = 3.

Perhaps not surprisingly, there is a generalized concept of the Stern sequence (1) that plays a similar role in the study of hyper b-ary representations as the numbers s(n) do in relation to hyperbinary expansions. The following definition and notation are based on [3].

Definition 3. For a fixed integer b ≥ 2 we define the generalized Stern sequence s_{b}(n) by s_{b}(0) = 0, s_{b}(1) = 1, and for n ≥ 1 by

s_{b}(bn − j) = s_{b}(n) (j = 0, 1, …, b − 2),  (3)
s_{b}(bn + 1) = s_{b}(n) + s_{b}(n + 1).  (4)

It is clear that the case b = 2 is the original Stern sequence (1). The sequence for b = 3 is listed as A054390 in [9], where various properties are given, including a close connection with hyperternary representations. It is, in fact, stated there that the number of hyperternary representations of n is s_{3}(n + 1). Indeed, using Definition 3 with b = 3, we compute s_{3}(37) = 5, which is consistent with Example 2.

Generalizing this connection between hyperternary representations and a generalized Stern sequence, Defant [3] stated the following result, along with the sketch of a proof.

Theorem 4 (Defant). Given a base b ≥ 2, the number of hyper b-ary representations of an integer n ≥ 1 is equal to s_{b}(n + 1).

It is the main purpose of this paper to introduce a refinement of Theorem 4, where we actually obtain the individual hyper b-ary representations of the integers n ≥ 1. This is achieved by way of a polynomial analogue of the numerical sequence s_{b}(n) of Definition 3. This is a sequence of polynomials in b variables and with b positive integer parameters. It generalizes a sequence of bivariate polynomials that was recently introduced by the authors [4] to characterize all hyperbinary representations of an integer n ≥ 1.

In order to motivate our main results, we recall the definition of this bivariate polynomial sequence in Section 2, along with the characterization of hyperbinary representations. In Section 3 we then define a ternary analogue, followed by the general b-ary case. Finally our main result, characterizing the hyper b-ary representation, and its proof are presented in Section 4.

2 Bivariate Stern polynomials

We begin by recalling the definition of a bivariate polynomial analogue of the Stern sequence (1). It was first introduced in the recent paper [4], and was further studied in [5].

Definition 5. Let s and t be fixed positive integer parameters. We define the two-parameter generalized Stern polynomials in the variables y and z by ω_{s,t}(0; y, z) = 0, ω_{s,t}(1; y, z) = 1, and for n ≥ 1 by

ω_{s,t}(2n; y, z) = y ω_{s,t}(n; y^{s}, z^{t}),  (5)
ω_{s,t}(2n + 1; y, z) = z ω_{s,t}(n; y^{s}, z^{t}) + ω_{s,t}(n + 1; y^{s}, z^{t}).  (6)

Various properties, including an explicit formula, a generating function, and some special cases, can be found in [4, Section 4]. For the sake of completeness and easy comparison with the ternary case, we copied Table 1 from [4]; it contains the first 16 nonzero polynomials ω_{s,t}(n; y, z).

\begin{matrix}n & ω_{s,t}(n; y, z) & n & ω_{s,t}(n; y, z) \\ 1 & 1 & 9 & y^{s^{3}} + y^{s+s^{2}}z + y^{s^{2}}z^{t} + z^{t^{2}} \\ 2 & y & 10 & y^{1+s^{3}} + y^{1+s^{2}}z^{t} + yz^{t^{2}} \\ 3 & y^{s} + z & 11 & y^{s+s^{3}} + y^{s^{3}}z + y^{s^{2}}z^{1+t} + y^{s}z^{t^{2}} + z^{1+t^{2}} \\ 4 & y^{1+s} & 12 & y^{1+s+s^{3}} + y^{1+s}z^{t^{2}} \\ 5 & y^{s^{2}} + y^{s}z + z^{t} & 13 & y^{s^{2}+s^{3}} + y^{s+s^{3}}z + y^{s^{3}}z^{t} + y^{s}z^{1+t^{2}} + z^{t+t^{2}} \\ 6 & y^{1+s^{2}} + yz^{t} & 14 & y^{1+s^{2}+s^{3}} + y^{1+s^{3}}z^{t} + yz^{t+t^{2}} \\ 7 & y^{s+s^{2}} + y^{s^{2}}z + z^{1+t} & 15 & y^{s+s^{2}+s^{3}} + y^{s^{2}+s^{3}}z + y^{s^{3}}z^{1+t} + z^{1+t+t^{2}} \\ 8 & y^{1+s+s^{2}} & 16 & y^{1+s+s^{2}+s^{3}} \end{matrix}

Table 1: ω_{s,t}(n; y, z) for 1 ≤ n ≤ 16

By comparing Definition 5 with (1), we immediately see that for all n ≥ 0 we have

ω_{s,t}(n; 1, 1) = s(n),  (7)

where s and t are arbitrary. We also have

ω_{1,t}(n; y, 1) = B_{n}(y), ω_{1,1}(n; y, q) = B_{n}(q, y), ω_{s,2}(n; 1, z) = a(n; z),  (8)

where s and t are arbitrary, B_{n}(y) is the nth Stern polynomial introduced by Klavžar et al. [7], B_{n}(q, y) is a q-analogue defined by Mansour [8], and a(n; z) is a different type of Stern polynomial introduced in [6]. Finally, the case ω_{s,1}(n; 1, z), with s again arbitrary, is equivalent to sequences of polynomials that were independently introduced in [1] and [11], where they were applied to obtain a refinement of Reznick’s result on hyperbinary representations. A similar refinement was earlier obtained in [7]; see Section 2 of [4] for a summary of these results.

The relevance of the polynomials ω_{s,t}(n; y, z) lies in the following result; see [4, Theorem 4.2].

Theorem 6. For an integer n ≥ 1 let ℍ_{n} be the set of all hyperbinary representations of n. Then we have

ω_{s,t}(n + 1; y, z) = ∑_{h∈ℍ_{n}} y^{p_{h}(s)}z^{q_{h}(t)},  (9)

where for each h in ℍ_{n}, the exponents p_{h}(s), q_{h}(t) are polynomials in s and t respectively, with only 0 and 1 as coefficients. Furthermore, if

p_{h}(s) = s^{σ_{1}} + ⋯ + s^{σ_{μ}}, 0 ≤ σ_{1} < ⋯ < σ_{μ}, μ ≥ 0,  (10)
q_{h}(t) = t^{τ_{1}} + ⋯ + t^{τ_{ν}}, 0 ≤ τ_{1} < ⋯ < τ_{ν}, ν ≥ 0,  (11)

then the hyperbinary representation h ∈ ℍ_{n} is given by

n = 2^{σ_{1}} + ⋯ + 2^{σ_{μ}} + (2^{τ_{1}} + 2^{τ_{1}}) + ⋯ + (2^{τ_{ν}} + 2^{τ_{ν}}).  (12)

By convention we assume that μ = 0 in (10) indicates that p_{h}(s) is the zero polynomial, which in turn means that there is no non-repeated power of 2 in (12). We make a similar assumption for ν = 0 in (11). This theorem also implies that for a given h ∈ ℍ_{n} the exponents σ_{j} and τ_{k} in (10) and (11) are all distinct.

Example 7. From Table 1 we have

ω_{s,t}(15; y, z) = y^{s+s^{2}+s^{3}} + y^{s^{2}+s^{3}}z + y^{s^{3}}z^{1+t} + z^{1+t+t^{2}},

and the four terms of this polynomial correspond, in this order, to the hyperbinary representations of n = 14, namely 2 + 4 + 8, 4 + 8 + 1 + 1, 8 + 1 + 1 + 2 + 2, 1 + 1 + 2 + 2 + 4 + 4.

3 b-ary Stern-type polynomial sequences

Just as we defined the sequence of bivariate polynomials ω_{s,t}(n; y, z) in (5), (6) as a wideranging extension of Stern’s diatomic sequence, we will now introduce a three-parameter sequence of polynomials in three variables. This provides a polynomial extension of the numerical sequence s_{3}(n). For greater ease of notation, we let T denote the triple T = (r, s, t) of positive integer parameters. In analogy to Definition 5 we then define the following polynomial sequence.

Definition 8. Let r, s, t be fixed positive integer parameters. We define the polynomial sequence ω_{T} (n; x, y, z) by ω_{T} (0; x, y, z) = 0, ω_{T} (1; x, y, z) = 1, and for n ≥ 1 by

ω_{T} (3n − 1; x, y, z) = x ω_{T} (n; x^{r}, y^{s}, z^{t}),  (13)
ω_{T} (3n; x, y, z) = y ω_{T} (n; x^{r}, y^{s}, z^{t}),  (14)
ω_{T} (3n + 1; x, y, z) = z ω_{T} (n; x^{r}, y^{s}, z^{t}) + ω_{T} (n + 1; x^{r}, y^{s}, z^{t}).  (15)

The first 27 of the polynomials ω_{T} (n; x, y, z) are listed in Table 2.

Definition 8 suggests that these polynomials can be further extended. We fix a base b ≥ 2 and a b-tuple of positive integer parameters T = (t_{1}, t_{2}, …, t_{b}). Then in analogy to Definitions 5 and 8 we define the following sequence of polynomials in b variables.

Definition 9. Let t_{1}, …, t_{b} be fixed positive integer parameters. We define the polynomial sequence ω_{T} (n; z_{1}, …, z_{b}) in the b variables z_{1}, …, z_{b} by the initial conditions ω_{T} (0; z_{1}, …, z_{b}) = 0, ω_{T} (1; z_{1}, …, z_{b}) = 1, and for n ≥ 1 by

ω_{T} (b(n − 1) + j + 1; z_{1}, …, z_{b}) = z_{j} ω_{T} (n; z_{1}^{t_{1}}, …, z_{b}^{t_{b}}) (1 ≤ j ≤ b − 1),  (16)
ω_{T} (bn + 1; z_{1}, …, z_{b}) = z_{b} ω_{T} (n; z_{1}^{t_{1}}, …, z_{b}^{t_{b}}) + ω_{T} (n + 1; z_{1}^{t_{1}}, …, z_{b}^{t_{b}}).  (17)

\begin{matrix}n & ω_{r,s,t}(n; x, y, z) & n & ω_{r,s,t}(n; x, y, z) & n & ω_{r,s,t}(n; x, y, z) \\ 1 & 1 & 10 & x^{r^{2}} + y^{s}z + z^{t} & 19 & x^{r^{2}}y^{s}z + x^{r^{2}}z^{t} + y^{s^{2}} \\ 2 & x & 11 & x^{1+r^{2}} + xz^{t} & 20 & x^{1+r^{2}}z^{t} + xy^{s^{2}} \\ 3 & y & 12 & x^{r^{2}}y + yz^{t} & 21 & x^{r^{2}}yz^{t} + y^{1+s^{2}} \\ 4 & x^{r} + z & 13 & x^{r+r^{2}} + x^{r^{2}}z + z^{1+t} & 22 & x^{r^{2}}z^{1+t} + x^{r}y^{s^{2}} + y^{s^{2}}z \\ 5 & x^{1+r} & 14 & x^{1+r+r^{2}} & 23 & x^{1+r}y^{s^{2}} \\ 6 & x^{r}y & 15 & x^{r+r^{2}}y & 24 & x^{r}y^{1+s^{2}} \\ 7 & x^{r}z + y^{s} & 16 & x^{r+r^{2}}z + x^{r^{2}}y^{s} & 25 & x^{r}y^{s^{2}}z + y^{s+s^{2}} \\ 8 & xy^{s} & 17 & x^{1+r^{2}}y^{s} & 26 & xy^{s+s^{2}} \\ 9 & y^{1+s} & 18 & x^{r^{2}}y^{1+s} & 27 & y^{1+s+s^{2}} \end{matrix}

Table 2: ω_{T} (n; x, y, z) for 1 ≤ n ≤ 27

We immediately see that for b = 2 and b = 3 we get Definitions 5 and 8, respectively. From Definition 9 we obtain the following easy properties, instances of which can be observed in Tables 1 and 2.

Lemma 10. With b and T as in Definition 9, we have

ω_{T} (j; z_{1}, …, z_{b}) = z_{j−1}  (2 ≤ j ≤ b),  (18)
ω_{T} (b + 1; z_{1}, …, z_{b}) = z_{b} + z_{1}^{t_{1}},  (19)
ω_{T} (b^{ℓ}; z_{1}, …, z_{b}) = z_{b−1}^{1+t_{b−1}+···+t_{b−1}^{ℓ−1}}  (ℓ ≥ 1).  (20)

Proof. The identity (18) follows immediately from (16) with n = 1. We obtain (19) from (17) with n = 1, followed by (18) with j = 2. Finally, (20) is obtained by an easy induction, where (18) with j = b is the induction beginning, and (16) with j = b − 1 provides the induction step.

To conclude this section, we note that by comparing Definition 9 with Definition 3 we see that for any b ≥ 2 and n ≥ 0 we have

ω_{T} (n; 1, …, 1) = s_{b}(n),  (21)

where the b-tuple T is arbitrary. This extends the identity (7).

4 The main result

To state a general b-ary analogue of Theorem 6, we let ℍ_{b,n} denote the set of all hyper b-ary representations of the integer n ≥ 1, and as in Definition 9 we let T = (t_{1}, …, t_{b}) be a b-tuple of positive integer parameters.

Theorem 11. For any integer n ≥ 1 we have

ω_{T} (n + 1; z_{1}, …, z_{b}) = ∑_{h∈ℍ_{b,n}} z_{1}^{p_{h,1}(t_{1})} ⋯ z_{b}^{p_{h,b}(t_{b})},  (22)

where for each h in ℍ_{b,n}, the exponents p_{h,1}(t_{1}), …, p_{h,b}(t_{b}) are polynomials in t_{1}, …, t_{b}, respectively, with only 0 and 1 as coefficients. Furthermore, if for 1 ≤ j ≤ b we write

p_{h,j}(t_{j}) = t_{j}^{τ_{j}(1)} + t_{j}^{τ_{j}(2)} + ⋯ + t_{j}^{τ_{j}(ν_{j})}, 0 ≤ τ_{j}(1) < ⋯ < τ_{j}(ν_{j}), ν_{j} ≥ 0,  (23)

then the powers that are used exactly j times in the hyper b-ary representation of n are

b^{τ_{j}(1)}, b^{τ_{j}(2)}, …, b^{τ_{j}(ν_{j})}.  (24)

If ν_{j} = 0 in (23), we set p_{h,j}(t_{j}) = 0 by convention, and accordingly (24) is the empty set.

By setting z_{1} = ⋯ = z_{b} = 1 and using (21), we immediately obtain Defant’s Theorem 4, and we see that Theorem 6 is the special case b = 2 with z_{1} = y, z_{2} = z, t_{1} = s, and t_{2} = t.

Before proving Theorem 11, we consider the following example.

Example 12. We choose b = 3 and n = 36. As in Definition 8 we use x, y, z for z_{1}, z_{2}, z_{3} and r, s, t for t_{1}, t_{2}, t_{3}. Using (15) and the relevant entries in Table 2, we find

ω_{T} (37; x, y, z) = z ω_{T} (12; x^{r}, y^{s}, z^{t}) + ω_{T} (13; x^{r}, y^{s}, z^{t})
= x^{r^{2}+r^{3}} + x^{r^{3}}y^{s}z^{1} + x^{r^{3}}z^{t} + y^{s}z^{1+t^{2}} + z^{t+t^{2}}.

The five terms in this polynomial correspond to the five hyperternary representations of n = 36 (see Example 2) that are listed in Table 3.

\begin{matrix}h & p_{h,1}(r) & p_{h,2}(s) & p_{h,3}(t) \\ 3^{3} + 3^{2} & r^{2} + r^{3} & 0 & 0 \\ 3^{3} + 3 + 3 + 1 + 1 + 1 & r^{3} & s^{1} & t^{0} \\ 3^{3} + 3 + 3 + 3 & r^{3} & 0 & t^{1} \\ 3^{2} + 3^{2} + 3^{2} + 3 + 3 + 1 + 1 + 1 & 0 & s^{1} & t^{0} + t^{2} \\ 3^{2} + 3^{2} + 3^{2} + 3 + 3 + 3 & 0 & 0 & t^{1} + t^{2} \end{matrix}

Table 3: h ∈ ℍ_{3,36} and ω_{T} (37; x, y, z)

Proof of Theorem 11. We proceed by induction on n, and refer to a hyper b-ary representation as an HBR.

(a) To establish the induction beginning, we first assume that 1 ≤ n ≤ b − 1. In this case the only HBR h of n is b^{0} + ⋯ + b^{0} (n summands).

On the other hand, by (18) we have

ω_{T} (n + 1; z_{1}, …, z_{b}) = z_{n}.

By (22) and (23) this means that

p_{h,n}(t_{n}) = 1 = t_{n}^{0}, p_{h,j}(t_{j}) = 0 (1 ≤ j ≤ b, j ≠ n).

But this, by (24), is consistent with the expansion n = b^{0} + ⋯ + b^{0}.

Second, let n = b. In this case two HBRs are given by h_{1} : n = b^{0} + ⋯ + b^{0} (with b summands) and h_{2} : n = b^{1}.

On the other hand, by (19) we have ω_{T} (b + 1; z_{1}, …, z_{b}) = z_{b} + z_{1}^{t_{1}}, and this time (22) and (23) imply that

p_{h_{1},b}(t_{b}) = 1 = t_{b}^{0}, p_{h_{1},j}(t_{j}) = 0 (1 ≤ j ≤ b − 1),
p_{h_{2},1}(t_{1}) = t_{1} = t_{1}^{1}, p_{h_{2},j}(t_{j}) = 0 (2 ≤ j ≤ b).

This is consistent with the two HBRs, which completes the induction beginning, namely that Theorem 11 holds for 1 ≤ n ≤ b.

(b) We now assume that the theorem is true for all n up to and including bk, for some k ≥ 1. We wish to show that it holds also for n = bk + r, r = 1, 2, …, b. We need to distinguish between the two cases (i) r = 1, 2, …, b − 1, and (ii) r = b.

(i) Let r be such that 1 ≤ r ≤ b − 1. Then each HBR of bk + r consists of exactly one HBR of bk that has no part b^{0}, plus r parts b^{0}. Hence there is a 1-1 correspondence between the HBRs of bk + r and those of \frac{1}{b}bk = k. Using the induction hypothesis and (22), we have

ω_{T} (k + 1; z_{1}, …, z_{b}) = ∑_{h∈ℍ_{b,k}} z_{1}^{p_{h,1}(t_{1})} ⋯ z_{b}^{p_{h,b}(t_{b})},  (25)

with exponents p_{h,1}(t_{1}), …, p_{h,b}(t_{b}) as in (23). Now, in order to lift the HBRs of k to those of bk + r, all powers of t_{j}, 1 ≤ j ≤ b, in (23) are augmented by 1, and in addition we add t_{r}^{0} to p_{h,r}(t_{r}). In other words, we get the polynomial

P := ∑_{h′∈ℍ_{b,n}} z_{1}^{p_{h′,1}(t_{1})} ⋯ z_{b}^{p_{h′,b}(t_{b})},  (26)

where

p_{h′,r}(t_{r}) = 1 + t_{r}p_{h,r}(t_{r}),  p_{h′,j}(t_{j}) = t_{j}p_{h,j}(t_{j}) (1 ≤ j ≤ b, j ≠ r).  (27)

Now with (25) and (27), the sum in (26) becomes

P = z_{r} ∑_{h∈ℍ_{b,k}} (z_{1}^{t_{1}})^{p_{h,1}(t_{1})} ⋯ (z_{b}^{t_{b}})^{p_{h,b}(t_{b})}
= z_{r}ω_{T} (k + 1; z_{1}^{t_{1}}, …, z_{b}^{t_{b}}) = ω_{T} (bk + r + 1; z_{1}, …, z_{b}),

where in the last equation we have used (16). This concludes the induction step in the case 1 ≤ r ≤ b − 1.

(ii) Now let r = b. Then the HBRs of bk + b fall into two categories:

– those with b parts b^{0}, and

– those with no parts b^{0}. For those HBRs that are in the first category, there is a 1-1 correspondence with the HBRs of k. Just as in part (i), the induction hypothesis leads to the polynomial

P_{1} := z_{b}ω_{T} (k + 1; z_{1}^{t_{1}}, …, z_{b}^{t_{b}}).  (28)

Similarly again, there is a 1-1 correspondence between the second category of HBRs of bk +b and the HBRs of \frac{1}{b}(bk + b) = k + 1. Using the induction hypothesis again, followed by an analysis similar to part (i), we get the polynomial

P_{2} := ω_{T} ((k + 1) + 1; z_{1}^{t_{1}}, …, z_{b}^{t_{b}}).  (29)

Finally, with (28) and (29), the polynomial corresponding to all HBRs of bk + b is

P_{1} + P_{2} = z_{b}ω_{T} (k + 1; z_{1}^{t_{1}}, …, z_{b}^{t_{b}}) + ω_{T} ((k + 1) + 1; z_{1}^{t_{1}}, …, z_{b}^{t_{b}})
= ω_{T} (bk + b + 1; z_{1}, …, z_{b}),

where in the last equation we have used (17). This concludes the induction step in the case r = b, and the proof is complete.

Independently of this paper, and in fact preceding our work, M. Ulas of Jagiellonian University (private communication) used generating functions to define a sequence of b-ary Stern polynomials that are identical with ω_{T} (n; z_{1}, …, z_{b}) for T = (1, 1, …, 1). He proved the following result which is a consequence of Theorem 11 above.

Corollary 13. Let n ≥ 1 and b ≥ 2 be integers, and let T = (1, …, 1) ∈ ℤ^{b}. If we write

ω_{T} (n + 1; z_{1}, …, z_{b}) = ∑_{α∈ℕ^{b}} c_{α}(n)z_{1}^{α_{1}} ⋯ z_{b}^{α_{b}}, α = (α_{1}, …, α_{b}),

then c_{α}(n) is the number of hyper b-ary representations of n for which α_{j} powers of b are used exactly j times, j = 1, 2, …, b.

Corollary 13 therefore generalizes the main results (for b = 2) in [1] and [11].

In closing, we remark that the polynomials ω_{T} (n; z_{1}, …, z_{b}) are objects worth studying in their own right, with numerous interesting properties; see, e.g., [2]. Some of these properties extend known results from base b = 2 to arbitrary bases, while others become nontrivial only for b ≥ 3. This will be the subject of a forthcoming paper.

References

[1] B. Bates and T. Mansour, The q-Calkin-Wilf tree, J. Combin. Theory Ser. A 118 (2011), 1143–1151.

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

[3] C. Defant, Upper bounds for Stern’s diatomic sequence and related sequences, Electron. J. Combin. 23 (2016), Paper 4.8.

[4] K. Dilcher and L. Ericksen, Generalized Stern polynomials and hyperbinary representations, Bull. Pol. Acad. Sci. Math. 65 (2017), 11–28.

[5] K. Dilcher and L. Ericksen, Continued fractions and polynomials related to hyperbinary representations, Bull. Pol. Acad. Sci. Math. 66 (2018). DOI: 10.4064/ba8126-12-2017. Published online: 22 January 2018.

[6] K. Dilcher and K. B. Stolarsky, A polynomial analogue to the Stern sequence, Int. J. Number Theory 3 (2007), 85–103.

[7] S. Klavžar, U. Milutinović, and C. Petr, Stern polynomials, Adv. in Appl. Math. 39 (2007), 86–95.

[8] T. Mansour, q-Stern polynomials as numerators of continued fractions, Bull. Pol. Acad. Sci. Math. 63 (2015), 11–18.

[9] OEIS Foundation Inc. (2011), The On-Line Encyclopedia of Integer Sequences,

http://oeis.org.

[10] B. Reznick, Some binary partition functions, in B. C. Berndt et al., eds., Analytic Number Theory: Proceedings of a Conference in Honor of Paul T. Bateman, Birkhäuser, 1990, pp. 451–477.

[11] R. P. Stanley and H. S. Wilf, Refining the Stern diatomic sequence, preprint, 2010,

http://www-math.mit.edu/~rstan/papers/stern.pdf.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 11B83. Keywords: Stern sequence, Stern polynomial, hyperbinary expansion, generating function.

(Concerned with sequences \underline{A002487} and \underline{A054390}.)

Received March 23 2018; revised versions received May 3 2018; May 7 2018. Published in Journal of Integer Sequences, May 7 2018.

Return to Journal of Integer Sequences home page.