% generalized1.tex: Begun July 11, 2014
% generalized2.tex: New Sections 2 and 3; new title. Begun Sept. 13, 2014.
% generalized3.tex: Sections 7, 8 removed (for a new paper). Sept. 16, 2014.
% generalized4.tex: Sect. 4 moved to the end; Sect. 6 mainly combined with
%                   Sect. 5, and partly with the former Sect. 4.
% generalized5.tex: Rewrote beginnings of Sect. 1-3. Oct. 23, 2014.
% generalized6.tex: Further revisions. Shortened title.
% This version as submitted to E-JC, Nov. 9, 2014.
% generalized7.tex: Reformatted according to E-JC style; referee comments
%                   implemented, April 1, 2015.
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P2.24}{22(2)}{2015}

\usepackage{amsthm,amsmath,amssymb}

\newtheorem{corollary}{Corollary}[section]
\newtheorem{definition}{Definition}[section]
\newtheorem*{notation}{Notation}                                                \newtheorem{proposition}{Proposition}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}{Lemma}[section]
\numberwithin{equation}{section}

 \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}


\title{\bf Hyperbinary expansions and Stern polynomials}

\author{Karl Dilcher\thanks{Supported in part by the Natural Sciences and 
Engineering Research Council of Canada, Grant \#145628481.}\\
\small Department of Mathematics and Statistics\\ [-0.8ex]
\small Dalhousie University\\ [-0.8ex]
\small Halifax, Nova Scotia, B3H 4R2, Canada \\
\small\tt dilcher@mathstat.dal.ca \\
\and
Larry Ericksen \\
\small P.O. Box 172\\ [-0.8ex]
\small  Millville, NJ 08332-0172, U.S.A.\\
\small\tt LE22@cornell.edu
}

\date{\dateline{Nov 10, 2014}{May 2, 2015}{May 14, 2015}\\
\small Mathematics Subject Classifications: 05A15, 11B83}

%\setcounter{equation}{0}
\begin{document}

\maketitle

\begin{abstract}
We introduce an infinite class of polynomial sequences $a_t(n;z)$ with integer
parameter $t\geq 1$, which reduce to the well-known Stern (diatomic) sequence 
when $z=1$ and are $(0,1)$-polynomials when $t\geq 2$.
Using these polynomial sequences, we derive two different characterizations
of all hyperbinary expansions of an integer $n\geq 1$. Furthermore,
we study the polynomials $a_t(n;z)$ as objects in their own right,
obtaining a generating function and some consequences. We also prove results  
on the structure of these sequences, and determine
expressions for the degrees of the polynomials.

%\bigskip\noindent \textbf{Keywords:} Stern sequence, Stern polynomials, 
%hyperbinary expansion, generating function
\end{abstract}

\section{Introduction and Motivation}

A {\rm hyperbinary expansion} 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, the hyperbinary expansions of $n=12$ are $8+4$, $8+2+2$,
$8+2+1+1$, $4+4+2+2$, $4+4+2+1+1$.

Within the framework of a more general study of binary partition functions,
Reznick \cite[Theorem~5.2]{Re} proved the following fundamental result.

\begin{theorem}[\cite{Re}]
The number of hyperbinary expansions of an integer $n\geq 1$ is given by
$a(n+1)$, where $\{a(n)\}$ is the Stern diatomic sequence.
\end{theorem}

Stern's (diatomic) sequence is one of the most remarkable integer sequences 
in number theory and combinatorics. Using the notation $\{a(n)\}_{n\geq 0}$, 
it can be defined by $a(0)=0$, $a(1)=1$, and for $n\geq 1$ by
\begin{equation}\label{1.1}
a(2n) = a(n),\qquad a(2n+1) = a(n) + a(n+1).
\end{equation}
Numerous properties and references can be found, e.g., in \cite[A002487]{OEIS},
\cite{CW}, or \cite{Re}. 

While Theorem~1.1 has been refined by results that count hyperbinary expansions
with certain properties (see \cite{BM}, \cite{KMP}, \cite{SW}),
one purpose of this paper is to prove results that give the actual
set of all hyperbinary expansions of $n$.
We begin by defining a {\it proper hyperbinary expansion\/} as one that has 
at least one repeated power of $2$. Our first main result, which characterizes 
the hyperbinary expansions, can then be stated as follows.

\begin{theorem}
Let $n\geq 2$ be an integer and denote by $k_1,\ldots,k_\nu$ those integers
$1\leq k\leq\lfloor\frac{n}{2}\rfloor$ for which $\binom{n-k}{k}$ is odd. Then
each hyperbinary expansion of $n$ corresponds to exactly one $k_j$, 
$j=1,\ldots,\nu$, as follows: The powers of $2$ in the binary expansion of 
$k_j$ are exactly the repeated powers of $2$ in a hyperbinary expansion of~$n$.
\end{theorem}

We illustrate this result with an example.

\medskip
\noindent
{\bf Example~1.} Considering again $n=12$, we find that $\binom{12-k}{k}$ is odd
for $k=1, 2, 5$, and 6. Accordingly, the four proper hyperbinary expansions of
$n=12$ are characterized as follows:
%\begin{enumerate}

$k_1=1$, so $12={\bf 1}+{\bf 1}+2+8$;

$k_2=2$, so $12={\bf 2}+{\bf 2}+8$;

$k_3=1+4$, so $12={\bf 1}+{\bf 1}+2+{\bf 4}+{\bf 4}$;

$k_4=2+4$, so $12={\bf 2}+{\bf 2}+{\bf 4}+{\bf 4}$.
%\end{enumerate}

\medskip
The proof of Theorem~1.2 involves properties of a class of polynomial analogues
of the Stern sequence, the introduction and study of which is the second main
purpose of this paper. We define these polynomials as follows: 

Given an integer $t\geq 1$, we set $a_t(0;z)=0$, $a_t(1;z)=1$, and for 
$n\geq 1$ we let
\begin{align}
a_t(2n;z) &= a_t(n;z^t), \label{1.4} \\
a_t(2n+1;z) &= z\,a_t(n;z^t) + a_t(n+1;z^t).\label{1.5}
\end{align}
For $t=2$ this definition reduces to that of the Stern polynomials defined in
\cite{DS1}, and polynomials closely related to $a_1(n;z)$ were studied in
\cite{BM} and \cite{SW}. 

Comparing \eqref{1.4} and \eqref{1.5} with \eqref{1.1}, we immediately see 
that for all integers $t\geq 1$ and $n\geq 1$ we have
\begin{equation}\label{1.6}
a_t(n;0) = 1,\qquad a_t(n;1) = a(n),
\end{equation}
and by iterating \eqref{1.4} and considering \eqref{1.5} we see that
\begin{equation}\label{1.9}
a_t(n;z) = 1\quad\Leftrightarrow\quad n=2^m,\quad m\geq 0.
\end{equation}
The polynomials $a_t(n;z)$ for $n\leq 20$ are listed in Table~1.

In Section~2 we derive further properties of the polynomials $a_t(n;z)$,
mainly concerning their structure, and in Section~3 we use these results to
establish a correspondence between these polynomials and hyperbinary
expansions. In Section~4 we obtain an explicit formula for $a_t(n;z)$ and use
it to prove Theorem~1.2 and a few additional results related to Theorems~1.1
and~1.2. In Section~5 we obtain a generating function and
prove some related identities, and in Section~6 we prove some further results
on the structure of the polynomials $a_t(n;z)$. Finally, in Section~7
we obtain identities for the degrees of these polynomials, and we conclude this
paper with some further remarks about Stern polynomials in Section~8.

\bigskip
\begin{center}
\begin{tabular}{|r|l||r|l|}
\hline
$n$ & $a_t(n;z)$ & $n$ & $a_t(n;z)$ \\
\hline
1 & 1 & 11 & $1+z+z^{t+1}+z^{t^2}+z^{t^2+1}$ \\
2 & 1 & 12 & $1+z^{t^2}$ \\
3 & $1+z$ & 13 & $1+z+z^t+z^{t^2+1}+z^{t^2+t}$ \\
4 & 1 &  14 & $1+z^t+z^{t^2+t}$ \\
5 & $1+z+z^t$ & 15 & $1+z+z^{t+1}+z^{t^2+t+1}$ \\
6 & $1+z^t$ & 16 & 1 \\
7 & $1+z+z^{t+1}$ & 17 & $1+z+z^t+z^{t^2}+z^{t^3}$ \\
8 & 1 & 18 & $1+z^t+z^{t^2}+z^{t^3}$ \\
9 & $1+z+z^t+z^{t^2}$ & 19 & $1+z+z^{t+1}+z^{t^2}+z^{t^2+1}+z^{t^3}+z^{t^3+1}$ \\
10 & $1+z^t+z^{t^2}$ & 20 & $1+z^{t^2}+z^{t^3}$ \\
\hline
\end{tabular}

\medskip
{\bf Table~1}: $a_t(n;z)$, $1\leq n\leq 20$.
\end{center}
\bigskip

\section{The structure of the polynomials $a_t(n;z)$}

Before we can state and prove results connecting hyperbinary expansions with
the polynomials $a_t(n;z)$, we need to derive some properties of these 
polynomials. 

\begin{proposition}
For integers $t\geq 2$ and $n\geq 0$, the coefficients of $a_t(n;z)$ are 
only $0$ or~$1$.
\end{proposition}

\begin{proof}
This is easily obtained by induction on $n$. We note that $a_t(1;z)=1$, and
suppose that the statement of the result is true up to index $n-1$. If $n$ is
even, the induction step is given by \eqref{1.4}. If $n$ is odd, we use 
\eqref{1.5} and note that for $t\geq 2$ the powers of $z$ in the two terms
on the right of \eqref{1.5} lie in two different residue classes modulo $t$;
hence there is no overlap, and the coefficients remain 0 or 1.
\end{proof}

When $t=1$, this proof fails. In fact, the smallest counterexample is
$a_1(5;z)=2z+1$; see Table~1. The case $t=1$ is of independent interest,
as we will see in Section~3.

The next result complements Proposition~2.1 and further explains the 
structure of the entries in Table~1.

\begin{proposition}
For any integer $n\geq 1$ we have
\begin{equation}\label{2a.1}
a_t(n;z) = 1 + \sum_{p\in\mathcal{P}_n} z^{p(t)},
\end{equation}
where $\mathcal{P}_n$ is a (possibly empty) set of $a(n)-1$ distinct 
polynomials in $t$ with coefficients $0$ or $1$.
\end{proposition}

\begin{proof}
We prove this by induction on $n$, using \eqref{1.4} and \eqref{1.5}. For $n=1$
we have $a_t(1;z)=1$, and so $\mathcal{P}_1=\emptyset$. Now suppose that the
statement holds up to a certain $n\geq 1$.

(i) By \eqref{1.4} and the induction hypothesis we have
\[
a_t(2n;z)=a_t(n;z^t) = 1 + \sum_{p\in\mathcal{P}_n} z^{tp(t)}.
\]
Hence 
\begin{equation}\label{2a.2}
\mathcal{P}_{2n}=\{tp(t)\mid p\in\mathcal{P}_n\}, 
\end{equation}
and therefore $\mathcal{P}_{2n}$ also has the desired properties. 

(ii) By \eqref{1.5} and the induction hypothesis we have
%\begin{align*}
\[
a_t(2n-1;z) = za_t(n-1;z^t) + a_t(n;z^t) 
=z+\sum_{p\in\mathcal{P}_{n-1}}z^{1+tp(t)}+1+\sum_{p\in\mathcal{P}_n}z^{tp(t)},
\]
%\end{align*}
and therefore
\begin{equation}\label{2a.3}
\mathcal{P}_{2n-1}=\{1\}\cup\{1+tp(t)\mid p\in\mathcal{P}_{n-1}\}
\cup\{tp(t)\mid p\in\mathcal{P}_n\}.
\end{equation}
Since the elements in $\mathcal{P}_{n-1}$ and in $\mathcal{P}_n$ are distinct,
and those in the second and third sets above have constant coeffcicients 1,
respectively 0, we see that all the elements in $\mathcal{P}_{2n-1}$ are
distinct. It is also clear that they have only coefficients 0 or 1.
This completes the proof by induction.
\end{proof}

We remark that this proof, along with \eqref{1.9}, shows that 
$\mathcal{P}_n$ is empty if and only if $n$ is a power of 2.

\section{Hyperbinary expansions}

The case $t=1$ of the polynomials $a_t(n;z)$ has recently been studied 
in connection with hyperbinary expansions. Indeed, Theorem~1.1 was refined 
by Bates and Mansour \cite{BM} and by Stanley and Wilf \cite{SW} who proved 
results that are equivalent to the following.

\begin{theorem}[\cite{BM}, \cite{SW}]
Given an integer $n\geq 1$, write
\begin{equation}\label{3a.1}
a_1(n+1;z) = \sum_{j\geq 0}c_{n,j}z^j.
\end{equation}
Then for each $j\geq 0$, $c_{n,j}$ is the number of hyperbinary expansions
of $n$ that have exactly $j$ repeated powers of $2$.
\end{theorem}

\noindent
{\bf Example~2.} Consider again $n=12$, with its hyperbinary expansions
\[
8+4,\quad 8+2+2,\quad 8+2+1+1,\quad 4+4+2+2,\quad 4+4+2+1+1.
\]
Since binary expansions are unique, we always have $c_{n,0}=1$, which is 
consistent with what we have seen in Section~1. Further, we see that $8+2+2$ 
and $8+2+1+1$ have exactly one repeated power of 2, so $c_{12,1}=2$. Finally, 
$4+4+2+2$ and $4+4+2+1+1$ 
have exactly two repeated power of 2, and thus $c_{12,2}=2$. So altogether,
the right-hand side of \eqref{3a.1} is $1+2z+2z^2$, which indeed equals
$a_1(13;z)$; see Table~1.

\medskip
The following result is similar to Theorem~1.2 in that it provides a complete
characterization of all hyperbinary expansions of a positive integer $n$,
thus vastly extends Theorem~3.1.
%Here the Stern polynomials $a_t(n+1;z)$ enter explicitly by way of the set 
%$\mathcal{P}_n$ of polynomials which was introduced in Proposition~2.2.

\begin{theorem}
Given an integer $n\geq 1$, let $\mathcal{P}_{n+1}$ be the set of exponents of
$z$ in $a_t(n+1;z)$, i.e.,
\[
a_t(n+1;z) = 1 + \sum_{p\in\mathcal{P}_{n+1}} z^{p(t)}.
\]
%!!
Then each proper hyperbinary expansion of $n$
corresponds to exactly one polynomial in $\mathcal{P}_{n+1}$, as follows: If
\begin{equation}\label{3a.2}
p(t) = t^{\alpha_1}+\dots+t^{\alpha_r}\in\mathcal{P}_{n+1},\quad
0\leq\alpha_1<\dots<\alpha_r,\quad r\geq 1,
\end{equation}
then exactly the powers $2^{\alpha_1},\ldots,2^{\alpha_r}$ are repeated in
the expansion.
\end{theorem}

In the following section we will see that Theorem~1.2 follows from Theorem~3.2.

\medskip
\noindent
{\bf Example~3.} We continue with the case $n=12$. Table~1 gives us
\[
\mathcal{P}_{13} = \{1, t, 1+t^2, t+t^2\}.
\]
Accordingly, the four proper hyperbinary expansions are characterized by the
following repeated powers of 2:
%\begin{enumerate}

$\bullet$ $2^0$, so $12={\bf 1}+{\bf 1}+2+8$;

$\bullet$ $2^1$, so $12={\bf 2}+{\bf 2}+8$;

$\bullet$ $2^0$ and $2^2$, so $12={\bf 1}+{\bf 1}+2+{\bf 4}+{\bf 4}$;

$\bullet$ $2^1$ and $2^2$, so $12={\bf 2}+{\bf 2}+{\bf 4}+{\bf 4}$.
%\end{enumerate}

\begin{proof}[Proof of Theorem~3.2]
We first deal with the case $n=2^m-1, m\geq 0$. Then by Theorem~1.1 and 
\eqref{1.9} there is only one hyperbinary expansion (HBE) of $n$, namely the
binary expansion (this can also be seen directly). On the other hand, again
by \eqref{1.9}, $\mathcal{P}_{n+1}$ is empty and therefore Theorem~3.2
holds trivially in this case. For all other $n$, \eqref{1.9} implies that
$\mathcal{P}_{n+1}$ is nonempty. (See also the remark a the end of Section~2).

We now proceed by induction on $n$, beginning with $n=2$. In this case
$\mathcal{P}_{n+1}=\{1\}=\{t^0\}$, which corresponds to the one proper HBE
$1+1$ of $n=2$, and the induction beginning is established. 

Suppose now that the result is true up to some integer $k\geq 1$. We 
distinguish between two cases.

(a) Let $n=2k+1$ be odd. By the first paragraph of the proof we may assume 
that $n+1$ is not a power of 2, and thus $k+1$ is also not a power of 2.
Clearly each HBE of $n$ contains exactly one summand $2^0$. By subtracting
this part and dividing the remainder by 2, we establish a bijection between
the HBEs of $k$ and those of $2k+1$.

On the other hand, by induction hypothesis all the proper HBEs of $k$ 
correspond to the elements
\[
t^{\alpha_1}+\dots+t^{\alpha_r}\in\mathcal{P}_{k+1},\quad
0\leq\alpha_1<\dots<\alpha_r,\quad r\geq 1.
\]
Now by \eqref{2a.2}, each element $p(t)\in\mathcal{P}_{k+1}$ corresponds to
the element $tp(t)=t^{\alpha_1+1}+\dots+t^{\alpha_r+1}\in\mathcal{P}_{2k+2}$.
But this was to be shown, since $2k+2=n+1$. Also note that the binary
expansion of $k$ corresponds to that of $2k+1$.

(b) Let $n=2k$ be even. Then the HBEs of $n$ fall into the following two
classes:

(i) Those HBEs which contain no summand $2^0$; this class contains the binary
expansion of $n$. Then by dividing by 2 we establish a bijection between these
and the HBEs of $k$. By induction hypothesis they are given by the binary 
expansion of $k$, along with the elements of $\mathcal{P}_{k+1}$.

(ii) Those HBEs which contain $2^0$ with multiplicity 2. Then by subtracting
these two parts and dividing by 2, noting that $(2k-2)/2=k-1$, we establish a
bijection between these and the HBEs of $k-1$. But by the induction 
hypothesis these latter HBEs are given by the binary expansion of $k-1$, along
with the elements of $\mathcal{P}_k$.

Now we use \eqref{2a.3} with $k+1$ in place of $n$, obtaining
\[
\mathcal{P}_{2k+1}=\{1\}\cup\{1+tp(t)\mid p\in\mathcal{P}_k\}
\cup\{tp(t)\mid p\in\mathcal{P}_{k+1}\}.
\]
We now see that the bijections in (i) and (ii) above are captured in this 
relation, with the exception of the binary expansion of $n$. But this is the
statement of Theorem~3.2 for $n=2k$. The proof by induction is now complete.
\end{proof}

\section{An explicit expansion, and a proof of Theorem~1.2}

In connection with a wider study of certain polynomial sequences, Carlitz
\cite[p.~17]{Ca1} proved, in different notation, the following result.

\begin{proposition}[\cite{Ca1}]
For a fixed $n\geq 0$, the number of odd binomial coefficients $\binom{n-k}{k}$
is given by the Stern number $a(n+1)$.
\end{proposition}

This indicates that it will be of interest to consider binomial coefficients
(mod~ 2). For the remainder of this section we use the notation
\begin{equation}\label{4a.1}
\binom{n}{k}^*\equiv \binom{n}{k}\pmod{2},\qquad \binom{n}{k}^*\in\{0,1\}.
\end{equation}
With this notation we can rewrite Proposition~4.1 as 
\begin{equation}\label{4a.2}
a(n+1)=\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-k}{k}^*,
\end{equation}
which was earlier obtained in \cite[p.~319]{GG}.
A polynomial analogue of this identity was given in Proposition~6.1 of
\cite{DS1} in terms of Chebyshev polynomials of the second kind, $U_n(x)$.
A well-known explicit expansion of $U_n(x)$ (see, e.g., \cite[Eqn.~(2.16)]{Ca1}) 
then gives, in the notation of \eqref{1.4} and \eqref{1.5},
\begin{equation}\label{4a.3}
a_2(n+1;z)=\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-k}{k}^*z^k.
\end{equation}
The main result of this section is an analogue of \eqref{4a.3} for $a_t(n+1;z)$
with arbitrary integer parameters $t\geq 1$. In order to state and prove this
result, we require the following function.

\begin{definition}
Let $n\geq 0$ be an integer, and let $n=\sum_{j\geq 0}c_j2^j$, $c_j\in\{0,1\}$,
be the binary expansion of $n$. Then for integers $t\geq 1$ we define
\begin{equation}\label{4a.4}
d_t(n):=\sum_{j\geq 0}c_jt^j.
\end{equation}
\end{definition}

See Table~2 for various small values of $d_t(n)$. The sequences
$d_t(n)$, $n\geq 1$, are in fact known for the first few $t\geq 1$; see the
last column in Table~2, where the reference numbers to the On-Line Encyclopedia
of Integer Sequences \cite{OEIS} are given. In particular, $d_1(n)$ gives the
binary weight or Hamming weight of $n$, and $d_4(n)$, $n\geq 1$, is known
as the Moser-deBrujn sequence.

\bigskip
\begin{center}
\begin{tabular}{|c||r|r|r|r|r|r|r|r|r|r||c|}
\hline
$t\;\backslash\; n$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & OEIS \\
\hline
$d_1(n)$ & 1 & 1 & 2 & 1 & 2 & 2 & 3 & 1 & 2 & 2 & A000120 \\
$d_2(n)$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & $\mathbb N$\\
$d_3(n)$ & 1 & 3 & 4 & 9 & 10 & 12 & 13 & 27 & 28 & 30 & A005836 \\
$d_4(n)$ & 1 & 4 & 5 & 16 & 17 & 20 & 21 & 64 & 65 & 68 & A000695 \\
$d_5(n)$ & 1 & 5 & 6 & 25 & 26 & 30 & 31 & 125 & 126 & 130 & A033042 \\
\hline
\end{tabular}

\medskip
{\bf Table~2}: $d_t(n)$ for $1\leq t\leq 5$ and $1\leq n\leq 10$.
\end{center}
\bigskip

The following identities are immediate consequences of the definition
\eqref{4a.4}: For all $n\geq 1$ we have
\begin{equation}\label{4a.5}
d_t(2n) = t\,d_t(n),\qquad d_t(2n+1) = t\,d_t(n)+1.
\end{equation}
We are now ready to prove the following result.

\begin{theorem}
For integers $t\geq 1$ and $n\geq 0$ we have
\begin{equation}\label{4a.6}
a_t(n+1;z)=\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-k}{k}^*z^{d_t(k)}.
\end{equation}
\end{theorem}

Before proving this result, we derive some basic properties of the 
coefficients in the polynomials in \eqref{4a.6}. By a special case of a 
well-known congruence of Lucas (see, e.g., \cite{Gr}) we have for nonnegative 
integers $m, n$ and $a, b\in \{0, 1\}$,
\[
\binom{2m+a}{2n+b}\equiv\binom{m}{n}\binom{a}{b}\pmod{2}.
\]
Hence we obtain (as also used by Carlitz \cite[p.~18f.]{Ca1}),
\begin{equation}\label{4a.7}
\binom{2m+a}{2n+b}^*=\begin{cases}
0 & \hbox{when $a=0$ and $b=1$},\\
\binom{m}{n}^* & \hbox{otherwise}.
\end{cases}
\end{equation}

\begin{proof}[Proof of Theorem~4.1]
We denote the right-hand side of \eqref{4a.6} by $\overline{a}_t(n+1;z)$ and
show that these sums satisfy the same recursions as $a_t(n+1;z)$, namely
\eqref{1.4} and \eqref{1.5}. The initial conditions 
$\overline{a}_t(1;z)=\overline{a}_t(2;z)=1$ are trivially true. We now 
distinguish between two cases: 

(i) Let $n$ be odd, say $n=2m-1$, $m\geq 2$. Then, using \eqref{4a.7},
\begin{align*}
\overline{a}_t(n+1;z) &= \overline{a}_t(2m;z)
=\sum_{k\geq 0}\binom{2m-1-k}{k}^*z^{d_t(k)} \\
&=\sum_{j\geq 0}\binom{2m-1-2j}{2j}^*z^{d_t(2j)} \\
&=\sum_{j\geq 0}\binom{m-1-j}{j}^*z^{td_t(j)} = \overline{a}_t(m;z^t), 
\end{align*}
where we have used \eqref{4a.7} again, as well as \eqref{4a.5}.

(ii) Let $n$ be even, say $n=2m$, $m\geq 1$. We split the summation
index into odd and even $k$ and then use \eqref{4a.7} and \eqref{4a.5}:
\begin{align*}
\overline{a}_t(n+1;z) &= \overline{a}_t(2m+1;z)
=\sum_{k\geq 0}\binom{2m-k}{k}^*z^{d_t(k)} \\
&=\sum_{j\geq 0}\binom{2m-2j-1}{2j+1}^*z^{d_t(2j+1)} 
+\sum_{j\geq 0}\binom{2m-2j}{2j}^*z^{d_t(2j)} \\
&=\sum_{j\geq 0}\binom{m-1-j}{j}^*z^{1+td_t(j)} 
+\sum_{j\geq 0}\binom{m-j}{j}^*z^{td_t(j)} \\
&= z\overline{a}_t(m;z^t) + \overline{a}_t(m+1;z^t).
\end{align*}
The cases (i) and (ii), together with the initial conditions, complete the 
proof.
\end{proof}

\begin{proof}[Proof of Theorem~1.2] Note that by Proposition~2.2 and 
Theorem~4.1, the elements of $\mathcal{P}_{n+1}$ are exactly those $d_t(k)$ 
for which $1\leq k\leq\lfloor\frac{n}{2}\rfloor$ and $\binom{n-k}{k}^*=1$, i.e.,
$\binom{n-k}{k}$ is odd. Now, by the definition \eqref{4a.4} of $d_t(k)$, there
is a one-to-one correspondence between the powers of $t$ in $d_t(k)$ and the
powers of 2 in the binary expansion of $k$. The result now follows from 
Theorem~3.2.
\end{proof}

We now consider the question of how many different
integers $n$ have the same number of hyperbinary expansions. The answer is
easily obtained from the following fact about the Stern sequence $a(n)$, which
goes back to Stern's original paper \cite[p.~202]{St}; see also 
\cite[p.~60]{Le}.

\begin{proposition}[\cite{St}]
Given an integer $m\geq 2$, the number of integers $j$ in the interval
$2^{m-1}\leq j\leq 2^m$ for which $a(j)=m$ is $\varphi(m)$, where $\varphi$
denotes Euler's totient function. Furthermore, it is the same number in any
subsequent interval between two consecutive powers of~$2$.
\end{proposition}

These $\varphi(m)$ numbers may be odd (e.g., $a(2^{m-1}+1)=a(2^m-1)=m$, which
is easy to see by induction), or they may be even, in which case we divide by
the appropriate power of 2, keeping \eqref{1.1} in mind. With Theorem~1.1 we
now get the following result.

\begin{proposition}
Given an integer $m\geq 2$, there are $\varphi(m)$ even integers with exactly
$m$ hyperbinary expansions.
\end{proposition}

\noindent
{\bf Example~4.} We saw in Example~1 that $n=12$ has $a(13)=5$ hyperbinary
expan\-sions, including the binary expansion. In accordance with Stern's 
Proposition~4.2,
\[
a(17) = a(22) = a(26) = a(31) =5,
\]
and since by \eqref{1.1} we also have $a(11)=a(13)=5$, we see that
$2h_r+1=11$, 13, 17 and 31 are the only odd integers with $a(2h_r+1)=5$,
$r=1,\ldots, 4$. Hence $2h_r=10$, 12, 16 and 30 are the only {\it even\/}
integers with exactly 5 hyperbinary expansions. {\it All\/} integers with 
this property are then given by 
\[
n = 2^s(2h_r+1)-1,\quad r=1,\ldots, 4;\quad s=1,2,\ldots.
\]
This last identity holds also in general, with the range of $r$ appropriately
adjusted.

\medskip
We conclude this section with a few more observations related to Theorem~1.2.
First, let $m\geq 2$ be given,
and let $2h_r+1$, $r=1,\ldots,\varphi(m)$ be the odd integers for which
$a(2h_r+1)=m$.

\begin{proposition}
Let $m\geq 2$ and $h_r$, $1\leq r\leq\varphi(m)$, be as above. If $\mu_r$ is
the number of odd $k$, $1\leq k\leq h_r$, for which $\binom{2h_r-k}{k}$ is odd,
then $\{\mu_r\mid 1\leq r\leq\varphi(m)\}$ is a reduced residue system modulo
$m$.
\end{proposition}

\begin{proof}
We let $h$ stand for an arbitrary $h_r$, and we rewrite \eqref{4a.2} by
splitting the summation index into $k=2j+1$ and $k=2j$; this is followed by
applying \eqref{4a.7}:
\begin{align*}
a(2h+1)&=\sum_{j\geq 0}\binom{2h-2-2j+1}{2j+1}^*
+\sum_{j\geq 0}\binom{2h-2j}{2j}^*\\
&=\sum_{j\geq 0}\binom{h-1-j}{j}^*+\sum_{j\geq 0}\binom{h-j}{j}^*
= a(h)+a(h+1),
\end{align*}
where we have used \eqref{4a.2} again. From this it is also clear that the
number of odd $k$ (resp.\ even $k$) for which $\binom{2h-k}{k}$ is odd is
exactly $a(h)$ (resp.\ $a(h+1)$).

To complete the proof, we note that $a(h)$ and $a(h+1)$ must be relatively 
prime (as already shown by Stern \cite[p.~199]{St}; see also \cite[p.~60]{Le}),
their sum is $m$, and they lie between 1 and $m-1$. But this means that both
$a(h)$ and $a(h+1)$ traverse a reduced residue system modulo $m$ as $h$ takes 
on the values $h_r$, $1\leq r\leq\varphi(m)$.
\end{proof}

It is clear from the proof that Proposition~4.4 could also be stated in terms
of even $k$. 

To return to our running example $n=12$: In Example~1 we
saw that there are two odd $k$ for which $\binom{12-k}{k}$ is odd, and indeed,
$a(6)=2$. For $n=10$, 16 and 30 (see Example~4), the corresponding numbers of
odd $k$ are $a(5)=3$, $a(8)=1$ and $a(15)=4$, respectively.

Finally, since the odd integers $k\geq 1$ are exactly those which have the
power $2^0=1$ in their binary expansions, Theorem~1.2 and the proof of 
Proposition~4.4 immediately gives the following consequence.

\begin{proposition}
Among the hyperbinary expansions of the positive even integer $n=2h$, exactly
$a(h)$ have a repeated $1$.
\end{proposition}

\section{Generating function}

A well-known property of the Stern sequence, first obtained by Carlitz
\cite{Ca2}, is the generating function
\begin{equation}\label{3.1}
x\prod_{k=0}^{\infty} \left(1+x^{2^k}+x^{2^{k+1}}\right)
= \sum_{n=1}^{\infty} a(n)x^n.
\end{equation}
In this section we are going to prove the general case.

\begin{proposition}
For integers $t\geq 1$, the Stern polynomials $a_t(n;z)$ have the generating 
function
\begin{equation}\label{3.4}
x\prod_{k=0}^{\infty} \left(1+x^{2^k}+x^{2^{k+1}}z^{t^k}\right)
= \sum_{n=1}^{\infty} a_t(n;z)x^n.
\end{equation}
\end{proposition}

Special cases of \eqref{3.4} were given in \cite{BM} for $t=1$ and in 
\cite{DS1} for $t=2$.

\begin{proof}[Proof of Proposition~5.1]
For a fixed $t\geq 1$, we set
\begin{align*}
f(x,z) := \sum_{n=1}^{\infty} a_t(n;z)x^{n-1}
&=\sum_{n=1}^{\infty}a_t(2n;z)x^{2n-1} + \sum_{n=0}^{\infty}a_t(2n+1;z)x^{2n}\\
&=: f_e(x,z)+f_o(x,z).
\end{align*}
Now by \eqref{1.4} we have
\begin{equation}\label{3.5}
f_e(x,z) = x\sum_{n=1}^{\infty}a_t(n;z^t)(x^2)^{n-1} = xf(x^2,z^t).
\end{equation}
Similarly, by \eqref{1.5} we have
\begin{align}
f_o(x,z) 
&=\sum_{n=0}^{\infty}\left(za_t(n;z^t)+a_t(n+1;z^t)\right)x^{2n}\label{3.6} \\
&= zx^2\sum_{n=1}^{\infty}a_t(n;z^t)(x^2)^{n-1} 
+ \sum_{n=0}^{\infty}a_t(n+1;z)(x^2)^n \nonumber \\
&= (zx^2+1)f(x^2,z^t). \nonumber
\end{align}
Adding \eqref{3.5} and \eqref{3.6}, we obtain
\[
f(x,z) = (1+x+x^2z)f(x^2,z^t),
\]
and upon iterating this functional equation we get
\begin{align}
f(x,z) &= (1+x+x^2z)(1+x^2+x^4z^t)f(x^4,z^{t^2}) \label{3.7} \\
&= \ldots \nonumber \\
&= \prod_{k=0}^N\left(1+x^{2^k}+x^{2^{k+1}}z^{t^k}\right)
\cdot f(x^{2^{N+1}},z^{t^{N+1}}). \nonumber
\end{align}
We are done if we can show that for sufficiently small $x$ and $z$ we have
\begin{equation}\label{3.8}
f(x^{2^{N+1}},z^{t^{N+1}}) \rightarrow 1\quad\hbox{as}\quad N\rightarrow\infty;
\end{equation}
then \eqref{3.7} becomes the desired identity \eqref{3.4} as 
$N\rightarrow\infty$.

To prove \eqref{3.8}, we use the following estimate on the size of the 
polynomials $a_t(n;z)$: For $|z|\leq 1$ we have
\begin{equation}\label{3.9}
|a_t(n;z)| \leq a(n) \leq c\cdot n^\mu < n,
\end{equation}
where the first inequality in \eqref{3.9} follows from \eqref{1.6}, and the
second inequality can be found in \cite[p.~472]{Re}; see also \cite[Prop.~2.2]{DS1}.
Here $c<1$ and $\mu=\log_2\frac{1+\sqrt{2}}{2}\simeq 0.694242$. If we rewrite
the definition of $f(x,z)$ as
\begin{equation}\label{3.10}
f(x,z) =  1 + x\left(\sum_{n=2}^{\infty}a_t(n;z)x^{n-2}\right),
\end{equation}
then we see that for any $|z|\leq 1$ and $|x|\leq 1-\varepsilon$ for some
$\varepsilon > 0$, the sum in parentheses on the right of \eqref{3.10} remains
bounded due to \eqref{3.9}. But then, since $x^{2^{N+1}}\rightarrow 0$ as
$N\rightarrow\infty$, we immediately get \eqref{3.8}. This completes the proof.
\end{proof}

We finish this section with what can be considered a finite analogue of the
generating function. One of the properties of the Stern polynomials $a_2(n;z)$ 
derived in \cite{DS1} is the identity
\begin{equation}\label{4.1}
\prod_{k=0}^{N-1}\left(2+z^{2^k}\right) = \sum_{n=2^N+1}^{2^{N+1}}a_2(n;z),
\end{equation}
valid for all integers $N\geq 1$. Using a different method of proof, we can
obtain the following generalization.

\begin{proposition}
For all integers $t\geq 1$ and $N\geq 1$ we have
\begin{equation}\label{4.2}
\prod_{k=0}^{N-1}\left(2+z^{t^k}\right) = \sum_{n=2^N+1}^{2^{N+1}}a_t(n;z).
\end{equation}
\end{proposition}

Before proving this result, we note that in addition to obtaining \eqref{4.1}
for $t=2$, the case $t=1$ immediately gives 
\begin{equation}\label{4.3}
(2+z)^N = \sum_{n=2^N+1}^{2^{N+1}}a_1(n;z),
\end{equation}
which can be viewed as an apparently new property of the $q$-hyperbinary
sequence (with $q=z$) studied in \cite{BM} and \cite{SW}. Another immediate
consequence of \eqref{4.2}, obtained by setting $z=1$ and using \eqref{1.6},
is the well-known identity
\[
\sum_{n=2^N+1}^{2^{N+1}}a(n) = 3^N
\]
for the Stern sequence; see, e.g., \cite{Le}.

The proof of Proposition~5.2 relies on the following property of the 
Stern polynomials $a_t(n;z)$.

\begin{proposition}
For all integers $t\geq 1$, $N\geq 0$ and $0\leq j\leq 2^N$ we have
\begin{equation}\label{4.4}
a_t(2\cdot 2^N+j;z)+a_t(3\cdot 2^N+j;z) = a_t(2^N+j;z)\left(2+z^{t^N}\right).
\end{equation}
\end{proposition}

To prove Proposition~5.2, we first sum both sides of \eqref{4.4} over all $j$,
$1\leq j\leq 2^N$, obtaining
\begin{equation}\label{4.5}
\sum_{n=2^{N+1}+1}^{2^{N+2}}a_t(n;z) 
= \left(2+z^{t^N}\right)\sum_{n=2^N+1}^{2^{N+1}}a_t(n;z).
\end{equation}
The desired identity \eqref{4.2} now follows by induction: For the base case
$N=1$ we note that $a_t(3;z)+a_t(4;z)=2+z$; see Table~1. Assuming now that 
\eqref{4.2} holds for some $N\geq 1$, \eqref{4.5} shows that it also holds for
$N+1$, which concludes the proof.

\begin{proof}[Proof of Proposition~5.3]
We prove this by induction on $N$. When $N=0$, we have
\[
a_t(2+j;z)+a_t(3+j;z) = a_t(1+j;z)(2+z)
\]
for $j=0, 1$, which is easy to verify with Table~1. Now suppose that \eqref{4.4}
holds up to some $N-1$, and for all $j$ with $0\leq j\leq 2^{N-1}$. To prove
\eqref{4.4} for $N$, we first assume that $j$ is even, say $j=2\ell$. Then by
\eqref{1.4} we have
\[
a_t(2\cdot 2^{N-1}+\ell;z^t)+a_t(3\cdot 2^{N-1}+\ell;z^t) 
= a_t(2^{N-1}+\ell;z^t)\left(2+(z^t)^{t^{N-1}}\right),
\]
but this is true by the induction hypothesis. When $j$ is odd, we proceed
analogously, using \eqref{1.5} and the induction hypothesis. This completes
the proof.
\end{proof}

\section{Further results on the structure of $a_t(n;z)$}

While Section~2 is concerned with the ``large structure" of the polynomials
$a_t(n;z)$, in this section we prove some results on the finer structure
of the polynomials. We start with the
observation that, for $t\geq 2$, all $a_t(2n+1;z)$ begin with
$1+z$ and all $a_t(2n;z)$ contain no $z$ term; see Table~1. Similarly, we 
observe a periodicity with period 4 which can be stated as follows: For all 
integers $t\geq 2$ and $k\geq 1$ we have
\begin{align*}
a_t(4k;z) &\equiv 1\pmod{z^{t^2}},\\
a_t(4k+1;z) &\equiv 1+z+z^t\pmod{z^{t^2}},\\
a_t(4k+2;z) &\equiv 1+z^t\pmod{z^{t^2}},\\
a_t(4k+3;z) &\equiv 1+z+z^{1+t}\pmod{z^{t^2}}.
\end{align*}
In general, we have the following result.

\begin{proposition}
Let $t\geq 2$ and $N\geq 0$ be integers. Then for all $n\geq 2^N$ we have
\begin{equation}\label{2.1a}
a_t(n+2^N;z)\equiv a_t(n;z)\pmod{z^{t^N}}.
\end{equation}
\end{proposition}

\begin{proof}
We prove this by induction on $N$. The base case $N=0$ reduces to
\[
a_t(n+1;z)\equiv a_t(n;z)\pmod{z}\quad\hbox{for all $n\geq 1$}. 
\]
But this is obvious since all $a_t(n;z)$ have constant coefficient 1 for 
$n\geq 1$.  

Now suppose that \eqref{2.1a} holds up to some $N\geq 0$ and for all 
$n\geq 2^N$. We first replace $z$ by $z^t$ in \eqref{2.1a} and apply 
\eqref{1.4} to both sides, to obtain
\begin{equation}\label{2.1b}
a_t(2n+2^{N+1};z)\equiv a_t(2n;z)\pmod{z^{t^{N+1}}},\quad n\geq 2^N.
\end{equation}
Using this and \eqref{1.5} with \eqref{1.4}, we get
\begin{align*}
a_t(2n-1+2^{N+1};z)-a_t(2n-1;z) 
&= z\left(a_t(2n-2+2^{N+1};z)-a_t(2n-2;z)\right)\\
&\quad + a_t(2n+2^{N+1};z)-a_t(2n;z)\\
&= zf(z)z^{t^{N+1}} + g(z)z^{t^{N+1}},
\end{align*}
for some polynomials $f$ and $g$, and valid for $n-1\geq 2^N$. But this, 
together with \eqref{2.1b}, means that for all $n\geq 2^{N+1}$ we have
\[
a_t(n+2^{N+1};z)\equiv a_t(n;z)\pmod{z^{t^{N+1}}},
\]
which completes the proof by induction.
\end{proof}

The following result, which is similar in nature to Proposition~5.3, can be
seen as supplementing Proposition~6.1. Indeed, it exhibits the exact remainder
when $n$ is restricted to $2^N\leq n\leq 2^{N+1}$. Here we find it convenient
to shift the parameters by setting $j=n-2^N$.

\begin{proposition}
For all integers $t\geq 1$, $N\geq 0$ and $0\leq j\leq 2^N$ we have
\begin{equation}\label{2.1c}
a_t(2^{N+1}+j;z) = a_t(2^N+j;z) + z^{t^N}a_t(j;z).
\end{equation}
\end{proposition}

\begin{proof}
We prove this again by induction on $N$. The base case $N=0$ is
\[
a_t(2+j;z) = a_t(1+j;z) + za_t(j;z)
\]
for $j=0, 1$, which is obvious from Table~1. The induction step is now very 
similar to the proof of Proposition~5.3.
\end{proof}

Related to the previous results is a regularity in the growth in the terms
of certain subsequences of the polynomials $a_t(n;z)$, as seen in the
following 

\medskip
\noindent
{\bf Example~5.}
\begin{align*}
a_3( 7;z) &= 1+z+z^4,\\
a_3(11;z) &= 1+z+z^4+z^9+z^{10},\\
a_3(19;z) &= 1+z+z^4+z^9+z^{10}+z^{27}+z^{28},\\
a_3(35;z) &= 1+z+z^4+z^9+z^{10}+z^{27}+z^{28}+z^{81}+z^{82}.
\end{align*}

This progression is explained by the following easy extension of 
Proposition~6.2.
It can be obtained by replacing $N$ by $N+\nu$ in \eqref{2.1c} and summing 
over all $\nu$, $0\leq \nu\leq K-1$.

\begin{proposition}
For all integers $t\geq 1$, $N\geq 0$, $K\geq 1$, and $0\leq j\leq 2^N$ we have
\begin{equation}\label{2.1d}
a_t(2^{N+K}+j;z) = a_t(2^N+j;z) + a_t(j;z)\sum_{\nu=0}^{K-1}z^{t^{N+\nu}}.
\end{equation}
\end{proposition}

This shows that the polynomials $a_t(2^{N+K}+j;z)$ change in a very regular
way for fixed $N$ and $j$, as $K$ grows.

While Propositions~6.2 and~6.3 deal with indices $n$ in $a_t(n;z)$ that are
a fixed integer $j$ above a power of 2, the following result deals with 
those that lie $j$ units below a power of 2.

\begin{proposition}
Let the integers $t\geq 1$ and $j\geq 1$ be given, and let $N$ be the 
smallest exponent for which $2^N\geq j$. Then for all $K\geq 1$ we have
\begin{align}\label{2.1e}
a_t(2^{N+K+1}-j;z) &= a_t(2^{N+K}-j;z)\\
&\quad+ z^{t^N+\dots+t^{N+K-1}}\left(a_t(2^{N+1}-j;z) - a_t(2^N-j;z)\right).
\nonumber
\end{align}
\end{proposition}

\begin{proof}
In \eqref{4.4} and \eqref{2.1c} we replace $j$ by $2^N-j$, obtaining the term
$a_t(3\cdot 2^N-j;z)$ in both identities. If we eliminate this term, we get
\begin{equation}\label{2.1f}
a_t(2^{N+2}-j;z) - a_t(2^{N+1}-j;z)
= z^{t^N}\left(a_t(2^{N+1}-j;z) - a_t(2^N-j;z)\right).
\end{equation}
This identity remains valid if we replace $N$ by $N+1,\ldots,N+K-1$. Then,
iterating \eqref{2.1f}, we obtain \eqref{2.1e}.
\end{proof}

Proposition~6.4 explains the next example, again with $t=3$ and $j=3$:

\medskip
\noindent
{\bf Example~6.}
\begin{align*}
a_3(1;z) &= 1,\\
a_3(5;z) &= 1+z+z^3,\\
a_3(13;z) &= 1+z+z^3+z^{10}+z^{12},\\
a_3(29;z) &= 1+z+z^3+z^{10}+z^{12}+z^{37}+z^{39},\\
a_3(61;z) &= 1+z+z^3+z^{10}+z^{12}+z^{37}+z^{39}+z^{118}+z^{120}.\\
\end{align*}

In closing this section we note that the sequences of polynomials in 
Examples~5 and~6, as well as \eqref{2.1d} and \eqref{2.1e}, suggest the 
existence of analytic functions (for $|z|<1$) as limiting cases, as 
$K \rightarrow \infty$.  

\section{The degrees of $a_t(n;z)$}

The main goal of this section is to obtain explicit expressions for the 
degrees of the polynomials $a_t(n;z)$. To this end we need to derive certain 
supporting identities.
We begin with some preliminary results on the differences in the
degrees of successive polynomials.

\begin{proposition}
Let $t\geq 1$ be a fixed integer. Then for any integer $n\geq 1$ we have
\begin{equation}\label{2.1}
\deg a_t(2n-1;z) \geq \deg a_t(2n;z).
\end{equation}
Furthermore, for any integer $k\geq 1$ and any odd integer $n'\geq 1$ we 
have
\begin{equation}\label{2.2}
\deg a_t(2^kn'+1;z)-\deg a_t(2^kn';z) = t^{k-1}.
\end{equation}
\end{proposition}

\begin{proof}
Slightly rewriting \eqref{1.5}, we have
\begin{equation}\label{2.2a}
a_t(2n-1;z) = a_t(n;z^t) + za_t(n-1;z^t).
\end{equation}
Since the coefficients of all these polynomials are nonnegative, there is no
cancellation on the right-hand side of \eqref{2.2a}. Therefore,
comparing this with \eqref{1.4}, we immediately obtain \eqref{2.1}.

Now, given an odd $n'\geq 1$, we get with \eqref{1.4} and \eqref{1.5},
\begin{align}
a_t(2^{k+1}n'+1;z) &= za_t(2^kn';z^t) + a_t(2^kn'+1;z^t), \label{2.3}\\
a_t(2^{k+1}n';z) &= a_t(2^kn';z^t).\label{2.4}
\end{align}
We first let $k=0$. Since $n'$ is odd, by \eqref{2.1} the degree of
\eqref{2.3} in this case is the same as the degree of the first term on the
right-hand side of \eqref{2.3}. Thus, by \eqref{2.4}, we have shown that 
$\deg a_t(2n'+1;z)-\deg a_t(2n';z)=1$, which is \eqref{2.2} for $k=1$.

This now serves as the base case of the general proof by induction on $k$.
Thus, suppose that \eqref{2.2} holds up to a certain $k\geq 1$. Since by the
induction hypothesis we have
\[
\deg a_t(2^kn'+1;z^t) \geq \deg a_t(2^kn';z^t)+1,
\]
the identity \eqref{2.3} gives
\[
\deg a_t(2^{k+1}n'+1;z) = \deg a_t(2^kn'+1;z^t)
= t\deg a_t(2^kn'+1;z).
\]
Hence, with \eqref{2.4} and the induction hypothesis we get
\begin{align*}
\deg a_t(2^{k+1}n'+1;z) &- \deg a_t(2^{k+1}n';z) \\
&= t\left(\deg a_t(2^kn'+1;z) - \deg a_t(2^kn';z)\right) = t\cdot t^{k-1},
\end{align*}
which is \eqref{2.2} with $k+1$ in place of $k$. This completes the proof.
\end{proof}

To obtain an explicit expression for the degrees of the polynomials $a_t(n;z)$,
we require the function $d_t(n)$, which was defined in \eqref{4a.4}.

\begin{proposition}
Let $e(n)$ be the highest power of $2$ dividing $n$. Then for integers
$t\geq 1$ and $n\geq 1$ we have
\begin{equation}\label{2.7}
\deg a_t(n;z) = d_t\left(\frac{n-2^{e(n)}}{2}\right),
\end{equation}
and in particular,
\begin{equation}\label{2.8}
\deg a_t(2n+1;z) = d_t(n).
\end{equation}
\end{proposition}

\begin{proof}
We prove \eqref{2.7} by induction on $n$; \eqref{2.8} then follows immediately
since $e(2n+1)=0$. \eqref{2.7} clearly holds for $n=1, 2$. Now, using 
\eqref{1.4}, the induction hypothesis, and finally the first identity in 
\eqref{4a.5}, we get
\begin{align*}
\deg a_t(2n;z) &= \deg a_t(n;z^t) = t \deg a_t(n;z) \\
&= t d_t\left(\frac{n-2^{e(n)}}{2}\right)
= d_t\left(2\frac{n-2^{e(n)}}{2}\right) \\
&= d_t\left(\frac{2n-2^{e(2n)}}{2}\right),
\end{align*}
which proves the statement for even indices.

Next, by \eqref{1.5}, the induction hypothesis, and both parts of \eqref{4a.5}
we have
\begin{align}
\deg a_t(2n+1;z) 
&= \max\left\{\deg a_t(n;z^t)+1,\deg a_t(n+1;z^t)\right\}\label{2.9} \\ 
&= \max\left\{t \deg a_t(n;z)+1,t \deg a_t(n+1;z)\right\}.\nonumber
\end{align}
If $n$ is even, then by \eqref{2.2} the maximum is attained by the second term
on the right-hand side of \eqref{2.9}. Therefore, by \eqref{2.9}, the induction
hypothesis, and by the first part of \eqref{4a.5} we have 
\begin{align*}
\deg a_t(2n+1;z) &= t \deg a_t(n+1;z) 
= t d_t\left(\frac{n+1-2^{e(n+1)}}{2}\right) \\
&= d_t\left(\frac{2n+1-(2^{e(n+1)+1}-1)}{2}\right).
\end{align*}
Now $e(n+1)=0$ since $n$ is even, and so $2^{e(n+1)+1}-1=1=2^{e(2n+1)}$, 
which means
\begin{equation}\label{2.10}
\deg a_t(2n+1;z) = d_t\left(\frac{2n+1-2^{e(2n+1)}}{2}\right),
\end{equation}
as required. If $n$ is odd, then by \eqref{2.1} the maximum on the right-hand
side of \eqref{2.9} is attained by the first term, so by induction hypothesis
and the second part of \eqref{4a.5} we have
\begin{align*}
\deg a_t(2n+1;z) &= t \deg a_t(n;z)+1 
= t d_t\left(\frac{n-2^{e(n)}}{2}\right)+1 \\
&= d_t\left(\frac{2n+1-(2^{e(n)+1}-1)}{2}\right).
\end{align*}
Since $n$ is odd, we have $e(n)=0$, so that $2^{e(n)+1}-1=1=2^{e(2n+1)}$, 
and once again we obtain \eqref{2.10}, as required. The proof is now complete.
\end{proof}

We note that in the case $t=2$, Proposition~7.2 above reduces to Proposition~2.1
in \cite{DS1}. For fixed $t\neq 2$, Table~2 with \eqref{2.8} seems to indicate
that the sequence of the degrees are rather irregular. However, it is clear
from Definition~2 that all degree polynomials in $t$ actually occur, 
and moreover they do so in their lexicographic order for $a_t(2n+1;z)$, 
$n\geq 1$. For instance, up to $n=7$ the degrees are $1, t, t+1, t^2, t^2+1, 
t^2+t$, and $t^2+t+1$.

\section{Further Remarks}

Since this paper deals with Stern polynomials, it should be mentioned that
a polynomial extension of the Stern sequence, different from that in 
\cite{DS1}, was independently introduced by S.~Klav{\v z}ar et al.\ \cite{KMP}.
Interestingly, their sequence of polynomials, which are not $(0,1)$-polynomials,
is also related to hyperbinary expansions of $n$. In fact, the $k$th 
coefficient of the $(n+1)$th Stern polynomial in the sense of \cite{KMP} is the 
number of hyperbinary expansions of $n$ with exactly $k$ digits 1. 

The Stern polynomials introduced in \cite{DS1}, which are the special case 
$t=2$ of the polynomials $a_t(n;z)$, have been investigated in greater detail
in \cite{DE1} and \cite{DS2}. The result of Carlitz, quoted in the 
present paper as Proposition~4.1, was also stated in \cite{DS1} as
Corollary~6.2; however, it contains a misprint: $a(n)$ should be replaced 
by $a(n+1)$.

In closing we mention that in addition to Theorem~1.1, another remarkable 
property of the Stern (diatomic) sequence $\{a(n)\}$ is the
fact that the quotients $a(n)/a(n+1), n\geq 1$, give an enumeration without
repetitions of all the positive rationals; see, e.g., \cite{CW}.


\begin{thebibliography}{25}

\bibitem{BM} B.~Bates and T.~Mansour. \newblock The $q$-Calkin-Wilf tree.
\newblock {\em J. Combin. Theory Ser. A}, 118:1143--1151, 2011.

\bibitem{CW} N.~Calkin and H.~S.~Wilf. \newblock Recounting the rationals.
\newblock {\em Amer. Math. Monthly}, 107(4):360--363, 2000.

\bibitem{Ca1} L.~Carlitz. \newblock Single variable Bell polynomials.
\newblock {\em Collect. Math.}, 14:13--25, 1960.

\bibitem{Ca2} L.~Carlitz. \newblock A problem in partitions related to the 
Stirling numbers. \newblock {\em  Bull. Amer. Math. Soc.}, 70:275--278, 1964.

\bibitem{DE1} K.~Dilcher and L.~Ericksen. \newblock Reducibility and 
irreducibility of Stern $(0,1)$-polynomials. \newblock {\em  Commun. Math.},
22:77--102, 2014.

\bibitem{DS1} K.~Dilcher and K.~B.~Stolarsky. \newblock A polynomial analogue 
to the Stern sequence. \newblock {\em Int. J. Number Theory}, 3:85--103, 2007.

\bibitem{DS2} K.~Dilcher and K.~B.~Stolarsky. \newblock Stern polynomials and
double-limit continued fractions. \newblock {\em Acta Arith.}, 140:19--134, 
2009.

\bibitem{GG} C.~Giuli and R.~Giuli. \newblock A primer on Stern's diatomic
sequence, Part~III: Additional results. \newblock {\em  Fibonacci Quart.},
17:318--320, 1979. 

\bibitem{Gr} A.~Granville. \newblock Arithmetic properties of binomial 
coefficients. I. Binomial coefficients modulo prime powers. \newblock In
{\em Organic mathematics}, (Burnaby, BC, 1995), pages 253--276. CMS Conf. 
Proc., 20, Amer. Math. Soc., Providence, RI, 1997. 

\bibitem{KMP} S.~Klav\v{z}ar, U.~Milutinovi\'c, and C.~Petr. \newblock Stern
polynomials. \newblock {\em Adv. in Appl. Math.}, 39:86--95, 2007.

\bibitem{Le} D.~H.~Lehmer. \newblock On Stern's diatomic series. \newblock
{\em Amer. Math. Monthly}, 36:59--67, 1929.

\bibitem{OEIS}
OEIS Foundation Inc. (2011). \newblock {\em The On-Line Encyclopedia of Integer
Sequences}.\\ \url{http://oeis.org}

\bibitem{Re} B.~Reznick. \newblock Some binary partition functions. \newblock 
In {\em Analytic Number Theory. Proceedings of a conference in honor of Paul 
T.~Bateman}. B.~C.~Berndt et al., eds., pages 451--477. Birkh\"auser, Boston, 
1990.

\bibitem{SW} R.~P.~Stanley and H.~S.~Wilf. \newblock Refining the Stern 
diatomic sequence. Preprint, 2010. 
\url{http://www-math.mit.edu/~rstan/papers/stern.pdf}

\bibitem{St} M.~A.~Stern. \newblock Ueber eine zahlentheoretische Funktion.
\newblock {\em J. Reine Angew. Math.}, 55:193--220, 1858.

\end{thebibliography}

\end{document}