\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Polynomials Characterizing Hyper $b$-ary \\ \vskip .1in Representations} \vskip 1cm \large Karl Dilcher\footnote{Research supported in part by the Natural Sciences and Engineering Research Council of Canada, Grant \# 145628481.}\\ Department of Mathematics and Statistics\\ Dalhousie University\\ Halifax, NS B3H 4R2\\ Canada\\ \href{mailto:dilcher@mathstat.dal.ca}{\tt dilcher@mathstat.dal.ca}\\ \ \\ Larry Ericksen\\ P. O. Box 172\\ Millville, NJ 08332-0172\\ USA\\ \href{mailto:LE22@cornell.edu}{\tt LE22@cornell.edu}\\ \end{center} \vskip .2in \begin{abstract} Given an integer base $b\geq 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. \end{abstract} \section{Introduction} A {\it hyperbinary representation} of an integer $n\geq 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 \begin{equation}\label{1.1} s(2n)=s(n),\qquad s(2n+1)=s(n)+s(n+1)\qquad (n\geq 1). \end{equation} This sequence, which appears in different notations in the literature, is sequence A002487 in \cite{OEIS}, where numerous properties and references can be found. The first few nonzero terms of the sequence \eqref{1.1} are easily seen to be {\bf 1}, {\bf 1}, 2, {\bf 1}, 3, 2, 3, {\bf 1}, 4, 3, 5, 2, 5, 3, 4, {\bf 1}, 5,$ \ldots,$ 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 \cite[Theorem~5.2]{Re} who proved that the number of hyperbinary representations of an integer $n\geq 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. \medskip In analogy to hyperbinary representations, a {\it hyperternary representation} of an integer $n\geq 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\geq 2$ is one of the fundamental concepts of this paper. \begin{definition}\label{def:1st} For a fixed integer $b\geq 2$, a hyper $b$-ary representation of an integer $n\geq 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 \begin{equation}\label{1.2} n = \sum_{j=0}^\nu d_jb^j,\quad 0\leq d_j\leq b\;\;\hbox{for}\;\; 0\leq j\leq\nu,\;\hbox{and}\;\; d_{\nu}\neq 0. \end{equation} \end{definition} Sometimes such a representation is called a base $b$ over-expansion of the integer $n$; see, e.g., Defant \cite{De}. \begin{example}\label{ex:1st} Let $b=3$ and $n=36$. Then the hyperternary representations of $n$ are $3^3+3^2,\quad 3^3+3+3+3,\quad 3^3+3+3+1+1+1,\quad 3^2+3^2+3^2+3+3+3,$ $3^2+3^2+3^2+3+3+1+1+1.$ \noindent Thus we have a total of five such representations, the first one being the unique representation of $n$ in base $b=3$. \end{example} Perhaps not surprisingly, there is a generalized concept of the Stern sequence \eqref{1.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 \cite{De}. \begin{definition}\label{def:2nd} For a fixed integer $b\geq 2$ we define the generalized Stern sequence $s_b(n)$ by $s_b(0)=0$, $s_b(1)=1$, and for $n\geq 1$ by \begin{align} s_b(bn-j) &= s_b(n)\qquad (j=0,1,\ldots,b-2),\label{1.3} \\ s_b(bn+1) &= s_b(n) + s_b(n+1).\label{1.4} \end{align} \end{definition} It is clear that the case $b=2$ is the original Stern sequence \eqref{1.1}. The sequence for $b=3$ is listed as A054390 in \cite{OEIS}, 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~\ref{def:2nd} with $b=3$, we compute $s_3(37)=5$, which is consistent with Example~\ref{ex:1st}. Generalizing this connection between hyperternary representations and a generalized Stern sequence, Defant \cite{De} stated the following result, along with the sketch of a proof. \begin{theorem}[Defant]\label{thm:defant} Given a base $b\geq 2$, the number of hyper $b$-ary representations of an integer $n\geq 1$ is equal to $s_b(n+1)$. \end{theorem} It is the main purpose of this paper to introduce a refinement of Theorem~\ref{thm:defant}, where we actually obtain the individual hyper $b$-ary representations of the integers $n\geq 1$. This is achieved by way of a polynomial analogue of the numerical sequence $s_b(n)$ of Definition~\ref{def:2nd}. 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 \cite{DE7} to characterize all hyperbinary representations of an integer $n\geq 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. \section{Bivariate Stern polynomials} We begin by recalling the definition of a bivariate polynomial analogue of the Stern sequence \eqref{1.1}. It was first introduced in the recent paper \cite{DE7}, and was further studied in \cite{DE8}. \begin{definition}\label{def:3rd} Let $s$ and $t$ be fixed positive integer parameters. We define the two-parameter generalized Stern polynomials in the variables $y$ and $z$ by $\omega_{s,t}(0;y,z)=0$, $\omega_{s,t}(1;y,z)=1$, and for $n\geq 1$ by \begin{align} \omega_{s,t}(2n;y,z) &= y\,\omega_{s,t}(n;y^s,z^t),\label{2.1} \\ \omega_{s,t}(2n+1;y,z) &= z\,\omega_{s,t}(n;y^s,z^t)+\omega_{s,t}(n+1;y^s,z^t). \label{2.2} \end{align} \end{definition} Various properties, including an explicit formula, a generating function, and some special cases, can be found in \cite[Section~4]{DE7}. For the sake of completeness and easy comparison with the ternary case, we copied Table~1 from \cite{DE7}; it contains the first 16 nonzero polynomials $\omega_{s,t}(n;y,z)$. \begin{table}[h]\label{table1} \begin{center} \begin{tabular}{|r|l||r|l|}\hline $n$ & $\omega_{s,t}(n;y,z)$ & $n$ & $\omega_{s,t}(n;y,z)$ \\ \hline 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^sz^{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^sz+z^t$ & 13 & $y^{s^2+s^3}+y^{s+s^3}z+y^{s^3}z^{t}+y^sz^{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}$ \\ \hline \end{tabular} \end{center} \caption{$\omega_{s,t}(n;y,z)$ for $1\leq n\leq 16$} \end{table} By comparing Definition~\ref{def:3rd} with \eqref{1.1}, we immediately see that for all $n\geq 0$ we have \begin{equation}\label{2.3} \omega_{s,t}(n;1,1) = s(n), \end{equation} where $s$ and $t$ are arbitrary. We also have \begin{equation}\label{2.4} \omega_{1,t}(n;y,1) = B_n(y),\quad \omega_{1,1}(n;y,q) = B_n(q,y),\quad \omega_{s,2}(n;1,z) = a(n;z), \end{equation} where $s$ and $t$ are arbitrary, $B_n(y)$ is the $n$th Stern polynomial introduced by Klav{\v z}ar et al.\ \cite{KMP}, $B_n(q,y)$ is a $q$-analogue defined by Mansour \cite{Ma}, and $a(n;z)$ is a different type of Stern polynomial introduced in \cite{DS1}. Finally, the case $\omega_{s,1}(n;1,z)$, with $s$ again arbitrary, is equivalent to sequences of polynomials that were independently introduced in \cite{BM} and \cite{SW}, where they were applied to obtain a refinement of Reznick's result on hyperbinary representations. A similar refinement was earlier obtained in \cite{KMP}; see Section~2 of \cite{DE7} for a summary of these results. The relevance of the polynomials $\omega_{s,t}(n;y,z)$ lies in the following result; see \cite[Theorem~4.2]{DE7}. \begin{theorem}\label{thm:bivariate} For an integer $n\geq 1$ let ${\mathbb H}_n$ be the set of all hyperbinary representations of $n$. Then we have \begin{equation}\label{2.5} \omega_{s,t}(n+1;y,z)=\sum_{h\in{\mathbb H}_n}y^{p_h(s)}z^{q_h(t)}, \end{equation} where for each $h$ in ${\mathbb H}_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 \begin{align} p_h(s) &= s^{\sigma_1}+\dots+s^{\sigma_\mu},\quad 0\leq\sigma_1<\dots<\sigma_\mu,\quad \mu\geq 0, \label{2.6} \\ q_h(t) &= t^{\tau_1}+\dots+t^{\tau_\nu},\quad 0\leq\tau_1<\dots<\tau_\nu,\quad \nu\geq 0, \label{2.7} \end{align} then the hyperbinary representation $h\in{\mathbb H}_n$ is given by \begin{equation}\label{2.8} n = 2^{\sigma_1}+\dots+2^{\sigma_\mu}+(2^{\tau_1}+2^{\tau_1})+\dots +(2^{\tau_\nu}+2^{\tau_\nu}). \end{equation} \end{theorem} By convention we assume that $\mu=0$ in \eqref{2.6} indicates that $p_h(s)$ is the zero polynomial, which in turn means that there is no non-repeated power of 2 in \eqref{2.8}. We make a similar assumption for $\nu=0$ in \eqref{2.7}. This theorem also implies that for a given $h\in{\mathbb H}_n$ the exponents $\sigma_j$ and $\tau_k$ in \eqref{2.6} and \eqref{2.7} are all distinct. \begin{example}\label{ex:2nd} From Table~1 we have \[ \omega_{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.$ \end{example} \section{{\it b}-ary Stern-type polynomial sequences} Just as we defined the sequence of bivariate polynomials $\omega_{s,t}(n;y,z)$ in \eqref{2.1}, \eqref{2.2} as a wide-ranging 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~\ref{def:3rd} we then define the following polynomial sequence. \begin{definition}\label{def:4th} Let $r,s,t$ be fixed positive integer parameters. We define the polynomial sequence $\omega_T(n;x,y,z)$ by $\omega_T(0;x,y,z)=0$, $\omega_T(1;x,y,z)=1$, and for $n\geq 1$ by \begin{align} \omega_T(3n-1;x,y,z) &= x\,\omega_T(n;x^r,y^s,z^t),\label{3.1} \\ \omega_T(3n;x,y,z) &= y\,\omega_T(n;x^r,y^s,z^t),\label{3.2} \\ \omega_T(3n+1;x,y,z) &= z\,\omega_T(n;x^r,y^s,z^t)+\omega_T(n+1;x^r,y^s,z^t). \label{3.3} \end{align} \end{definition} The first 27 of the polynomials $\omega_T(n;x,y,z)$ are listed in Table~2. \begin{table}[h]\label{table2} \begin{center} \begin{tabular}{|c | l || l | l || l | l |} \hline $n$ & $\omega_{r,s,t}(n;x,y,z)$ & $n$ & $\omega_{r,s,t}(n;x,y,z)$ & $n$ & $\omega_{r,s,t}(n;x,y,z)$ \\ \hline $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}+x z^t$ & $20$ & $x^{1+r^2} z^t +x y^{s^2}$ \\ $3$ & $y$ & $12$ & $x^{r^2} y+y z^t$ & $21$ & $x^{r^2} y z^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$ & $x y^s$ & $17$ & $x^{1+r^2} y^s$ & $26$ & $x y^{s+s^2}$ \\ $9$ & $y^{1+s}$ & $18$ & $x^{r^2} y^{1+s}$ & $27$ & $y^{1+s+s^2}$ \\ \hline \end{tabular} \end{center} \caption{$\omega_T(n;x,y,z)$ for $1\leq n\leq 27$} \end{table} Definition~\ref{def:4th} suggests that these polynomials can be further extended. We fix a base $b\geq 2$ and a $b$-tuple of positive integer parameters $T=(t_1,t_2,\ldots,t_b)$. Then in analogy to Definitions~\ref{def:3rd} and \ref{def:4th} we define the following sequence of polynomials in $b$ variables. \begin{definition}\label{def:5th} Let $t_1,\ldots,t_b$ be fixed positive integer parameters. We define the polynomial sequence $\omega_T(n;z_1,\ldots,z_b)$ in the $b$ variables $z_1,\ldots,z_b$ by the initial conditions $\omega_T(0;z_1,\ldots,z_b)$ $=0$, $\omega_T(1;z_1,\ldots,z_b)=1$, and for $n\geq 1$ by \begin{align} &\omega_T(b(n-1)+j+1;z_1,\ldots,z_b) = z_j\,\omega_T(n;z_1^{t_1},\ldots,z_b^{t_b})\quad (1\leq j\leq b-1), \label{3.4} \\ &\omega_T(bn+1;z_1,\ldots,z_b) = z_b\,\omega_T(n;z_1^{t_1},\ldots,z_b^{t_b}) +\omega_T(n+1;z_1^{t_1},\ldots,z_b^{t_b}). \label{3.5} \end{align} \end{definition} We immediately see that for $b=2$ and $b=3$ we get Definitions~\ref{def:3rd} and \ref{def:4th}, respectively. From Definition~\ref{def:5th} we obtain the following easy properties, instances of which can be observed in Tables~1 and~2. \begin{lemma}\label{lem} With $b$ and $T$ as in Definition~\ref{def:5th}, we have \begin{align} \omega_T(j;z_1,\ldots,z_b) &= z_{j-1}\qquad (2\leq j\leq b),\label{3.6}\\ \omega_T(b+1;z_1,\ldots,z_b) &= z_b+z_1^{t_1},\label{3.7}\\ \omega_T(b^\ell;z_1,\ldots,z_b) &= z_{b-1}^{1+t_{b-1}+\dots+t_{b-1}^{\ell-1}} \qquad (\ell\geq 1).\label{3.8} \end{align} \end{lemma} \begin{proof} The identity \eqref{3.6} follows immediately from \eqref{3.4} with $n=1$. We obtain \eqref{3.7} from \eqref{3.5} with $n=1$, followed by \eqref{3.6} with $j=2$. Finally, \eqref{3.8} is obtained by an easy induction, where \eqref{3.6} with $j=b$ is the induction beginning, and \eqref{3.4} with $j=b-1$ provides the induction step. \end{proof} To conclude this section, we note that by comparing Definition~\ref{def:5th} with Definition~\ref{def:2nd} we see that for any $b\geq 2$ and $n\geq 0$ we have \begin{equation}\label{3.9} \omega_T(n;1,\ldots,1) = s_b(n), \end{equation} where the $b$-tuple $T$ is arbitrary. This extends the identity \eqref{2.3}. \section{The main result} To state a general $b$-ary analogue of Theorem~\ref{thm:bivariate}, we let ${\mathbb H}_{b,n}$ denote the set of all hyper $b$-ary representations of the integer $n\geq 1$, and as in Definition~\ref{def:5th} we let $T=(t_1,\ldots,t_b)$ be a $b$-tuple of positive integer parameters. \begin{theorem}\label{thm:main} For any integer $n\geq 1$ we have \begin{equation}\label{4.1} \omega_T(n+1;z_1,\ldots, z_b)=\sum_{h\in{\mathbb H}_{b,n}} z_1^{p_{h,1}(t_1)}\cdots z_b^{p_{h,b}(t_b)}, \end{equation} where for each $h$ in ${\mathbb H}_{b,n}$, the exponents $p_{h,1}(t_1),\ldots,p_{h,b}(t_b)$ are polynomials in $t_1,\ldots,t_b$, respectively, with only $0$ and $1$ as coefficients. Furthermore, if for $1\leq j\leq b$ we write \begin{equation}\label{4.2} p_{h,j}(t_j) =t_j^{\tau_j(1)}+t_j^{\tau_j(2)}+\dots+t_j^{\tau_j(\nu_j)},\quad 0\leq\tau_j(1)<\dots<\tau_j(\nu_j),\quad \nu_j\geq 0, \end{equation} then the powers that are used exactly $j$ times in the hyper $b$-ary representation of $n$ are \begin{equation}\label{4.3} b^{\tau_j(1)}, b^{\tau_j(2)},\ldots, b^{\tau_j(\nu_j)}. \end{equation} If $\nu_j=0$ in \eqref{4.2}, we set $p_{h,j}(t_j)=0$ by convention, and accordingly \eqref{4.3} is the empty set. \end{theorem} By setting $z_1=\dots=z_b=1$ and using \eqref{3.9}, we immediately obtain Defant's Theorem~\ref{thm:defant}, and we see that Theorem~\ref{thm:bivariate} is the special case $b=2$ with $z_1=y$, $z_2=z$, $t_1=s$, and $t_2=t$. Before proving Theorem~\ref{thm:main}, we consider the following example. \begin{example}\label{ex:3rd} We choose $b=3$ and $n=36$. As in Definition~\ref{def:4th} we use $x,y,z$ for $z_1,z_2,z_3$ and $r,s,t$ for $t_1,t_2,t_3$. Using \eqref{3.3} and the relevant entries in Table~2, we find \begin{align*} \omega_T(37;x,y,z) &= z\,\omega_T(12;x^r,y^s,z^t)+\omega_T(13;x^r,y^s,z^t) \\ &= x^{r^2+r^3} + x^{r^3}y^sz^1 + x^{r^3}z^t + y^sz^{1+t^2} + z^{t+t^2}. \end{align*} The five terms in this polynomial correspond to the five hyperternary representations of $n=36$ (see Example~\ref{ex:1st}) that are listed in Table~3. \end{example} \begin{table}[h]\label{table3} \begin{center} \begin{tabular}{|l|c|c|c|}\hline $h$ & $p_{h,1}(r)$ & $p_{h,2}(s)$ & $p_{h,3}(t)$ \\ \hline $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$ \\ \hline \end{tabular} \end{center} \caption{$h\in{\mathbb H}_{3,36}$ and $\omega_T(37;x,y,z)$} \end{table} \begin{proof}[Proof of Theorem~\ref{thm:main}] 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\leq n\leq b-1$. In this case the only HBR $h$ of $n$ is $b^0+\dots+b^0$ ($n$ summands). On the other hand, by \eqref{3.6} we have \[ \omega_T(n+1;z_1,\ldots,z_b) = z_n. \] By \eqref{4.1} and \eqref{4.2} this means that \[ p_{h,n}(t_n)=1=t_n^0,\qquad p_{h,j}(t_j)=0\quad (1\leq j\leq b, j\neq n). \] But this, by \eqref{4.3}, is consistent with the expansion $n=b^0+\dots+b^0$. Second, let $n=b$. In this case two HBRs are given by $h_1: n=b^0+\dots+b^0$ (with $b$ summands) and $h_2: n=b^1$. On the other hand, by \eqref{3.7} we have $\omega_T(b+1;z_1,\ldots,z_b)=z_b+z_1^{t_1}$, and this time \eqref{4.1} and \eqref{4.2} imply that \begin{align*} p_{h_1,b}(t_b)=1=t_b^0,\qquad &p_{h_1,j}(t_j)=0\quad (1\leq j\leq b-1),\\ p_{h_2,1}(t_1)=t_1=t_1^1,\qquad &p_{h_2,j}(t_j)=0\quad (2\leq j\leq b). \end{align*} This is consistent with the two HBRs, which completes the induction beginning, namely that Theorem~\ref{thm:main} holds for $1\leq n\leq b$. \medskip (b) We now assume that the theorem is true for all $n$ up to and including $bk$, for some $k\geq 1$. We wish to show that it holds also for $n=bk+r$, $r=1,2,\ldots, b$. We need to distinguish between the two cases (i) $r=1,2,\ldots,b-1$, and (ii) $r=b$. \medskip (i) Let $r$ be such that $1\leq r\leq 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 \eqref{4.1}, we have \begin{equation}\label{4.4} \omega_T(k+1;z_1,\ldots, z_b)=\sum_{h\in{\mathbb H}_{b,k}} z_1^{p_{h,1}(t_1)}\cdots z_b^{p_{h,b}(t_b)}, \end{equation} with exponents $p_{h,1}(t_1),\ldots,p_{h,b}(t_b)$ as in \eqref{4.2}. Now, in order to lift the HBRs of $k$ to those of $bk+r$, all powers of $t_j$, $1\leq j\leq b$, in \eqref{4.2} 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 \begin{equation}\label{4.5} P:=\sum_{h'\in{\mathbb H}_{b,n}} z_1^{p_{h',1}(t_1)}\cdots z_b^{p_{h',b}(t_b)}, \end{equation} where \begin{equation}\label{4.6} p_{h',r}(t_r) = 1+t_rp_{h,r}(t_r),\qquad p_{h',j}(t_j) = t_jp_{h,j}(t_j)\quad (1\leq j\leq b, j\neq r). \end{equation} Now with \eqref{4.4} and \eqref{4.6}, the sum in \eqref{4.5} becomes \begin{align*} P &= z_r\sum_{h\in{\mathbb H}_{b,k}}\left(z_1^{t_1}\right)^{p_{h,1}(t_1)}\cdots \left(z_b^{t_b}\right)^{p_{h,b}(t_b)} \\ &= z_r\omega_T(k+1;z_1^{t_1},\ldots, z_b^{t_b}) = \omega_T(bk+r+1;z_1,\ldots, z_b), \end{align*} where in the last equation we have used \eqref{3.4}. This concludes the induction step in the case $1\leq r\leq b-1$. \medskip (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$. \noindent 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 \begin{equation}\label{4.7} P_1 := z_b\omega_T(k+1;z_1^{t_1},\ldots, z_b^{t_b}). \end{equation} 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 \begin{equation}\label{4.8} P_2 := \omega_T((k+1)+1;z_1^{t_1},\ldots, z_b^{t_b}). \end{equation} Finally, with \eqref{4.7} and \eqref{4.8}, the polynomial corresponding to all HBRs of $bk+b$ is \begin{align*} P_1+P_2 &= z_b\omega_T(k+1;z_1^{t_1},\ldots, z_b^{t_b}) + \omega_T((k+1)+1;z_1^{t_1},\ldots, z_b^{t_b}) \\ &= \omega_T(bk+b+1;z_1,\ldots, z_b), \end{align*} where in the last equation we have used \eqref{3.5}. This concludes the induction step in the case $r=b$, and the proof is complete. \end{proof} 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 $\omega_T(n;z_1,\ldots,z_b)$ for $T=(1,1,\ldots,1)$. He proved the following result which is a consequence of Theorem~\ref{thm:main} above. \begin{corollary}\label{cor} Let $n\geq 1$ and $b\geq 2$ be integers, and let $T=(1,\ldots,1)\in{\mathbb Z}^b$. If we write \[ \omega_T(n+1;z_1,\ldots, z_b)=\sum_{\alpha\in{\mathbb N}^b}c_\alpha(n) z_1^{\alpha_1}\cdots z_b^{\alpha_b},\qquad \alpha=(\alpha_1,\ldots,\alpha_b), \] then $c_\alpha(n)$ is the number of hyper $b$-ary representations of $n$ for which $\alpha_j$ powers of $b$ are used exactly $j$ times, $j=1,2,\ldots,b$. \end{corollary} Corollary~\ref{cor} therefore generalizes the main results (for $b=2$) in \cite{BM} and \cite{SW}. \medskip In closing, we remark that the polynomials $\omega_T(n;z_1,\ldots,z_b)$ are objects worth studying in their own right, with numerous interesting properties; see, e.g., \cite{CS}. Some of these properties extend known results from base $b=2$ to arbitrary bases, while others become nontrivial only for $b\ge 3$. This will be the subject of a forthcoming paper. \begin{thebibliography}{25} \bibitem{BM} B.~Bates and T.~Mansour, The $q$-Calkin-Wilf tree, {\it J. Combin. Theory Ser. A} {\bf 118} (2011), 1143--1151. \bibitem{CS} M.~Coons and L.~Spiegelhofer, The maximal order of hyper-($b$-ary)-expansions. {\it Electron. J. Combin.} {\bf 24} (2017), Paper 1.15. \bibitem{De} C.~Defant, Upper bounds for Stern's diatomic sequence and related sequences, {\it Electron. J. Combin.} {\bf 23} (2016), Paper 4.8. \bibitem{DE7} K.~Dilcher and L.~Ericksen, Generalized Stern polynomials and hyperbinary representations, {\it Bull. Pol. Acad. Sci. Math.} {\bf 65} (2017), 11--28. \bibitem{DE8} K.~Dilcher and L.~Ericksen, Continued fractions and polynomials related to hyperbinary representations, {\it Bull. Pol. Acad. Sci. Math.} {\bf 66} (2018). DOI: 10.4064/ba8126-12-2017. Published online: 22 January 2018. \bibitem{DS1} K.~Dilcher and K.~B.~Stolarsky, A polynomial analogue to the Stern sequence, {\it Int. J. Number Theory} {\bf 3} (2007), 85--103. \bibitem{KMP} S.~Klav\v{z}ar, U.~Milutinovi\'c, and C.~Petr, Stern polynomials, {\it Adv. in Appl. Math.} {\bf 39} (2007), 86--95. \bibitem{Ma} T.~Mansour, $q$-Stern polynomials as numerators of continued fractions, {\it Bull. Pol. Acad. Sci. Math.} {\bf 63} (2015), 11--18. \bibitem{OEIS} OEIS Foundation Inc. (2011), {\it The On-Line Encyclopedia of Integer Sequences}, \url{http://oeis.org}. \bibitem{Re} B.~Reznick, Some binary partition functions, in B.~C.~Berndt et al., eds., {\it Analytic Number Theory: Proceedings of a Conference in Honor of Paul T.~Bateman}, Birkh\"auser, 1990, pp. 451--477. \bibitem{SW} R.~P.~Stanley and H.~S.~Wilf, Refining the Stern diatomic sequence, preprint, 2010, \url{http://www-math.mit.edu/\~rstan/papers/stern.pdf}. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 05A15; Secondary 11B83. \noindent \emph{Keywords: } Stern sequence, Stern polynomial, hyperbinary expansion, generating function. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A002487} and \seqnum{A054390}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received March 23 2018; revised versions received May 3 2018; May 7 2018. Published in {\it Journal of Integer Sequences}, May 7 2018. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}