\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}