\documentclass[12pt]{amsart}
\usepackage{amsmath, amsthm, amssymb, amsfonts}
\usepackage{enumerate}
\usepackage{hyperref}
\usepackage{verbatim}
%\numberwithin{equation}{section}

%%%Document Configuration
\pagestyle{headings}
%\addtolength{\topmargin}{-.5in}
\textwidth = 6in 
\oddsidemargin = .25in
\evensidemargin = .25in
\voffset = -1in
\textheight = 9.5 in
%\textwidth = 6in
%\parindent = 0in
%\headsep = 0in
\relpenalty = 9999
\binoppenalty = 9999
%linespacing
\renewcommand{\baselinestretch}{1.25}
\reversemarginpar     
%%%

%%%Theorem Configuration
\theoremstyle{plain}
\newtheorem*{main}{Main~Theorem}
\newtheorem{thm}{Theorem}[section]
\newtheorem*{thm*}{Theorem}
\newtheorem*{claim*}{Claim}
\newtheorem{cor}[thm]{Corollary}
\newtheorem*{cor*}{Corollary}
\newtheorem*{conj*}{Conjecture}
\newtheorem{exer}[thm]{Exercise}
\newtheorem{fact}[thm]{Fact}
\newtheorem{lem}[thm]{Lemma}
\newtheorem*{lem*}{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{remark}[thm]{Remark}
\newtheorem*{remark*}{Remark}
\newtheorem{hw}[section]{}
%\newtheorem{hw}[section]{HW}
\newtheorem{dfn}{Definition}[section]
\newtheorem*{dfn*}{Definition}
\newtheorem*{eg*}{Example}
%%%

%%%Bibliography Configuration
\bibliographystyle{plain}
%%%

%%%semantic definitions
\DeclareMathOperator*{\Aut}{Aut}
\DeclareMathOperator*{\Dom}{Dom}
%\DeclareMathOperator*{\Layer}{Layer}
\DeclareMathOperator*{\Mod}{Mod}
\DeclareMathOperator*{\str}{str}
\DeclareMathOperator*{\Th}{Th}
\DeclareMathOperator*{\tp}{tp}
\DeclareMathOperator{\im}{Im}
\renewcommand{\div}{\mid}
\renewcommand{\emptyset}{\varnothing}
\renewcommand{\implies}{\Rightarrow}
\renewcommand{\natural}{\mathbb{N}}
\newcommand{\Acl}[1]{\obar{#1}}
\newcommand{\assign}{\leftarrow}
\newcommand{\Exists}{\Huge \exists}
\newcommand{\caseif}{\Rightarrow}
\newcommand{\caseonlyif}{\Leftarrow}
\newcommand{\cantprove}{\nvdash}
\newcommand{\complex}{\mathbb{C}}
\newcommand{\field}{\mathbb{F}}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\minus}{\setminus}
\newcommand{\Layer}{\text{Layer}}
\newcommand{\power}[1]{{\mathcal{P}}({#1})}
\newcommand{\nonnegative}{\mathbb{N}}
%\newcommand{\index}[3]{_{#1 = #2}^{#3}} %old style, general
%\newcommand{\index}[3]{_{#1}^{#3}} %ordinal style from 0
%\newcommand{\indexz}[2]{_{#1 = 0}^{#2 - 1}} %old style, 0 to #2-1
%\newcommand{\indexz}[2]{For #1 from 0 to #2-1}} %pseudocode, 0 to #2-1
\newcommand{\indexz}[2]{_{#1 \in #2}} %ordinal style, 0 to #2-1
\newcommand{\integer}{\mathbb{Z}}
\newcommand{\intersect}{\cap}
\newcommand{\isomorphic}{\simeq}
\newcommand{\obar}[1]{\overline{#1}}
\newcommand{\proves}{\vdash}
\newcommand{\rational}{\mathbb{Q}}
\newcommand{\real}{\mathbb{R}}
\newcommand{\sst}{{\big|}} %not semantic, but used for \set, \setBig
\newcommand{\sstBig}{{\Big|}}
\newcommand{\set}[2]{\left\{#1 \sst #2 \right\}}
\newcommand{\setl}[2]{\left.\left\{#1 \right| #2 \right\}}
\newcommand{\setr}[2]{\left\{#1 \left| #2 \right\}\right.}
\newcommand{\setBig}[2]{\left\{#1 \sstBig #2 \right\}}
\newcommand{\union}{\cup}
\newcommand{\Union}{\bigcup}
\newcommand{\units}[1]{{\left(#1\right)}^{\times}}
%%%

%%%local definitions
\newcommand{\degin}{d^-}
\newcommand{\degout}{d^+}
\newcommand{\eleq}{\equiv}
\newcommand{\elleq}{\preccurlyeq}
\newcommand{\eqand}{\hspace{1pc}\text{and}\hspace{1pc}}
\newcommand{\gtlex}{\displaystyle \mathop{>}_{lex}}
\newcommand{\ltlex}{\displaystyle \mathop{<}_{lex}}
\newcommand{\Hy}{\eta}
\newcommand{\lang}[1]{{\mathcal{#1}}}
\newcommand{\Los}{{\L o\'s}}
\newcommand{\LS}{{L\"{o}wenheim-Skolem }}
\newcommand{\lsh}{\texttt{<<}}
\newcommand{\rsh}{\texttt{>>}}
\newcommand{\mathscr}[1]{{\mathcal{#1}}}
\newcommand{\monster}{{\mathbb{M}}}
\newcommand{\ndiv}{\nmid}
\newcommand{\pve}{pve}
\newcommand{\pvp}{pvp}
\newcommand{\pvr}{pvr}
\newcommand{\pvrf}{pvrf}
\newcommand{\st}[1]{{\mathcal{#1}}}
\newcommand{\structure}[1]{{\mathcal{#1}}}
\newcommand{\struct}[1]{\left\langle#1\right\rangle}
\newcommand{\subst}{\prec}
\newcommand{\symAnd}{\mathop{\bigwedge}}
\newcommand{\symand}{\wedge}
\newcommand{\symimply}{\rightarrow}
\newcommand{\symiff}{\leftrightarrow}
\newcommand{\symnot}{\neg}
\newcommand{\symor}{\vee}
\newcommand{\tuple}[1]{\obar{#1}}
\newcommand{\Tfcp}{T_E^{\text{fcp}}}
\newcommand{\WFF}{well-formed formula}
\newcommand{\zonein}[1]{Z^-_{#1}}
\newcommand{\zoneout}[1]{Z^+_{#1}}
\newcommand{\0}{\textbf{0}}
\newcommand{\suc}{\textbf{S}}
\newcommand{\A}{\mathfrak{A}}
\newcommand{\B}{\mathfrak{B}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\NNN}{\mathfrak{N}}
\newcommand{\E}{\textbf{E}}
\newcommand{\Cn}{\textrm{Cn}}
\newcommand{\res}{\upharpoonright}
\renewcommand{\P}{{Pl\"{u}nnecke }}
%%%

%%%marginpars
\setlength{\marginparwidth}{1 in}
\let\oldmarginpar\marginpar
\renewcommand\marginpar[1]{\-\oldmarginpar[\raggedleft\footnotesize #1]%
{\raggedright\footnotesize #1}}

\begin{document}

\title{Properties of Stern-like Sequences}
\author{Dakota Blair}
\maketitle

\section*{Notation}
Let $c$ be an ordinal.
If $c$ is finite, associate it to the corresponding integer $c = |c|$.
This is an overloaded notation, but context will determine what type
of object $c$ is being considered at the time.
For example in the two cases $0 \in c$ and $0 < c$ the symbol
$c$ is a set and an integer respectively.
Let $s$ be a sequence, that is $s = (s_i)_{i \in I}$.
Denote the length of $s$ as $|s| = |I|$.
A sequence is considered a $1 \times |s|$ matrix
with transposition of $s$ denoted by $s^T$.
Further if $s = (s_i)_{i \in I}$ and $i' \in I$ then $s(i') = s_{i'}$.
Denote by $c^{<\omega}$ the set of all finite sequences $s = (s(i))_{i \in |s|}$
where $s(i) \in c$, that is,
$c^{<\omega}
= \set{s}{|s| < \omega, s = (s(i))_{i \in |s|} \text{ where } s(i) \in c}$.
Let $s, s' \in c^{<\omega}$.
Denote concatenation by juxtaposition, that is
$s'' = ss' = \{s''(i)\}_{i \in |s|+|s'|}$
where $s''(i) = s'(i)$ if $i < |s'|$ and $s''(i) = s(i - |s'|)$ otherwise.
If $s \in c^{<\omega}$ is written adjacent to $i < c$
then $i$ is considered to be a sequence of length $1$ and concatenation
as defined above applies.
Sequences are ordered lexicographically greatest index first,
denoted $\ltlex$ with the added definition that
if $|s| < |s'|$ then $s \ltlex s'$.
In particular $22 \ltlex 122 \ltlex 200$.
The shift right operator,
$\rsh$ acts by removing the initial element from a sequence.
That is, given $s = (s_i)_{i \in |s|}$
let $\rsh s = (s(i+1))_{i \in |s|-1}$.

\section*{Stern-like sequences}
\begin{dfn*}[Stern-like sequences]
Let $b \geq 2$ be an integer. Define $S_b(n)$ recursively with
\begin{align*}
S_b(0) & = S_b(1) = \cdots = S_b(b-1) = 1 \\
S_b(bn + r) & = S_b(n) \text{ for } 0 < r < b\\
S_b(bn) & = S_b(n) + S_b(n-1).
\end{align*}
\end{dfn*}

\begin{dfn*}[Place Value Partition]
Let $c$ be a positive integer and $s \in c^{<\omega}$.
Then $s$ is a place value partition base $b$ of $n$ where
\[
n = \pve(s, b) = \sum_{i \in |s|} s(i) b^i.
\]
The set of place value partitions of
$n$ base $b$ carrying at $c$ of length at most $d$ is
\[
\pvp(n, b, c, d) = \set{s}{n = \pve(s, b), s \in c^{\leq d} , s(|s|) \neq 0}.
\]
The set of such partitions of any length is
\[
\pvp(n, b, c) = \Union_{d<\omega} \pvp(n, b, c, d).
\]
Further define
\[
\pvr(n, b, c, d) = |\pvp(n, b, c, d)|
\eqand
\pvr(n, b, c) = |\pvp(n, b, c)|.
\]
Denote the frequency of occurences of $m$ from $n'$ to $n''$ as
\[
\pvrf(m, n', n'', b, c) =
\left|\set{n}{\pvr(n,b,c) = m, n' \leq n \leq n''}\right|.
\]
\end{dfn*}

\begin{thm*}
For all integers $b$ and $n$ such that $b > 1$ and $n$ nonnegative
\[
\pvr(n, b, b+1) = S_b(n).
\]
\end{thm*}

\begin{proof}
For brevity let $A_b(n) = \pvr(n, b, b+1)$.
Note that the claim is true for $n < b$ by definition.
Assume the induction hypothesis,
that is $A_b(m) = S_b(m)$, holds for all $m < n$.
Let $r \in b$ such that $r \equiv n \pmod b$.
There are two cases, one where $r = 0$ and the other where $r > 0$.
Let $n'$ be such that $n = n'b + r$,
$a = A_b(n)$ and $a' = A_b(n')$.
Enumerate the place value representations of $n$ and $n'$ as
$\{s_i\}_{i \in a}$ and $\{s'_i\}_{i \in a'}$ respectively.
Given $i$, let $s''_i = \rsh s_i$ 
that is, $s''_i$ is the sequence resulting from
dropping the $0$th index from $s_i$.

Assume first that $r > 0$.
Thus $\pve(s'_i r, b) = n$ for all $i \in a$ hence
$A_b(n') \leq A_b(n)$.
Note also that $s''_i \in \pvp(n', b, b+1)$
since $\pve(s''_i, b) = n'$.
Further these are distinct because $s_i(0) = r$ for all $i \in a$.
Therefore $A_b(n) \leq A_b(n')$, so
\[
\pvr(n, b, b+1) = A_b(n) = A_b(n') = S_b(n') = S_b(n'b + r) = S_b(n)
\]
when $r > 0$.

If $r = 0$ then for each $i$ either
$s_i(0) = 0$ or $s_i(0) = b$.
Partition $\pvp(n, b, b+1)$ into
\begin{align*}
C_0 & = \set{s \in \pvp(n, b, b+1)}{s(0)=0}
\eqand \\
C_b & = \set{s \in \pvp(n, b, b+1)}{s(0)=b}.
\end{align*}
If $s_i(0) = 0$ then $\pve(s''_i, b) = n'$.
Since each $i$ is associated to a distinct $s''_i$
this shows $C_0 \subset \pvp(n', b, b+1)$
and $|C_0| \leq A_b(n')$.
Further for $s' \in C_b(n')$ it is the case that
$\pve(s'0, b) = bn' = n$
therefore $s' \in C_0$ hence $A_b(n') \leq |C_0|$,
thus $|C_0| = A_b(n')$.
If $s_i(0) = b$ then $\pve(s''_i, b) = n'-1$,
so $s''_i \in \pvp(n' - 1, b, b+1)$.
Then, similarly as above,
$|C_b| = A_b(n'-1)$.
Therefore $A_b(n) = |C_0| + |C_b| = A_b(n') + A_b(n'-1)$.
Consequently 
\[
\pvr(n, b, b+1) = S_b(n)
\]
for all $b$ and $n$ such that $b > 1$ and $n \geq 0$.
\end{proof}

\begin{comment}
\begin{dfn*}[Multilinear recurrence (MLR)]
A multilinear recurrence $S_X(n)$ is a map
such that for all integers $n = qm + r$
where $m \geq 0$ and $r \in q$
\[
S_X(qm+r) = (S_X(m-i))_{i \in I} X_j^T
\]
where $X_j$ is a tuple of reals.
The matrix $X = ((X_j)_{j \in J})^T$
is the matrix corresponding to the MLR $S_X(n)$.
\end{dfn*}

X_{b,c}
 & = (\pvr(ib^d+j, b, c, d))_{i \in f+1, j \in b^d} \text{ and}\\
S_{X_{b,c}}(n)
 & = \pvr(n, b, c) \text{ for } n \leq (f+1)b^d
\[
\pvr(n, b, c) = S_{X_{b,c}}(n) \text{ for all } n.
\]
That is
\end{comment}

\begin{thm*}
Let
\begin{align*}
d & = \floor{\log_b(c-1)} + 1,\\
w & = \frac{(c-1)(b^d - 1)}{b-1},\\
f & = \floor{\frac{w}{b^d}},\\
n & = m b^d + j \text{ and } n > (f+1)b^d.
\end{align*}
Then
\[
\pvr(n, b, c) = \sum_{i \in f+1} \pvr(ib^d + j, b, c, d)\pvr(m-i, b, c)
\tag{$\ast$}
\label{recurrence-ih}
\]
where $j \in b^d$ is an integer.
\end{thm*}

\begin{proof}
This result may be seen by induction.
%By definition the two sequences are equal up to $(f+1) b^d$.
Assume (\ref{recurrence-ih}) for all $n \leq m$.
%that $\pvr(n, b, c) = S_{X_{b,c}}(n)$ for all $n \leq m$.
Note that $n' \neq n''$ implies that
$\pvp(n', b, c)$ and $\pvp(n'', b, c)$ are disjoint.
If $s \in \pvp(m-i, b,c)$ and $t \in \pvp(ib^d+j, b, c, d)$
then $st \in \pvp(n, b, c)$.
This defines a concatenation map, say $g$, from the set
\[
A = \Union_{i \in f+1}
  \pvp(i b^d + j, b, c, d)\times\pvp(m-i, b,c)
\]
to $\pvp(n, b, c)$ which is injective, therefore
\[
\sum_{i \in f+1}|\pvp(i b^d + j, b, c, d)||\pvp(m-i, b,c)| \leq |\pvp(mb^d + j, b, c)|.
\]
and in other terms,
\[
\sum_{i \in f+1}\pvr(i b^d + j, b, c, d)\pvr(m-i, b,c) \leq \pvr(n, b, c).
\]
%For each $v$ there are $|\pvp(i b^d+j, b, c, d)|$ choices of $z$
%such that $vz \in \pvp(n, b, c)$.
%\left|\set{t \in \pvp(n, b, c)}{t = vt' \text{ and } \pve(t', b) = ib^d+j}\right|
If $u \in \pvp(n, b, c)$
%for $j \in b^d$
then one may factor $u$ as
$u = st$ with $|t| = d$.
In this case, there exists an $i$ such that $s \in \pvp(m-i, b, c)$,
further $i < f+1$ because $w < (f+1)b^d$.
Then $mb^d +j - (m-i)b^d = ib^d + j$
implies that $t \in \pvp(ib^d + j, b, c, d)$.
Thus every element of $\pvp(n, b, c)$ has an inverse in $A$,
hence $g$ is bijective.
%$\pve(t, b) = ib^d+j$,
%that is $t' \in \pvp(i b^d + j, b, c, d)$ and $v \in \pvp(m-i, b, c)$.
%consider the factorizations $t = st' = s'ut'$
%where $|t'| = d, \pve(s, b) = m$ and $u \in c$.
%It may be assumed that $(f+1)b^d \leq \pve(s'u, b)$
%as otherwise the base case applies.
Therefore
\[
|\pvp(n, b, c)|
\leq \sum_{i \in f+1}|\pvp(i b^d + j, b, c, d)||\pvp(m-i, b, c)|.
\]
Consequently $\pvr(n, b, c) = \sum_{i \in f+1} \pvr(ib^d + j, b, c, d)\pvr(m-i, b, c).$
\end{proof}

\begin{eg*}
Let $b = 2$ and $c = 5$,
then $\pvr(n, 2, 5)$ is the $5$th hyperbinary sequence.
Further $d = 3, w = \pve(444, 2) = 28, f = 3$ and
\[
X_{2,5} = \left(\begin{array}{cccc}
1 & 7 & 8 & 4\\
1 & 5 & 5 & 2\\
2 & 7 & 7 & 2\\
2 & 5 & 5 & 1\\
4 & 8 & 7 & 1\\
3 & 5 & 4 & 0\\
5 & 7 & 5 & 0\\
4 & 5 & 3 & 0
\end{array}
\right).
\]
Note that $(\pvr(15-i, 2, 5))_{i \in 4} = (9, 12, 8, 12)$
and
\[
(\pvr(120+j, 2, 5))_{j \in 8}
 = (205, 133, 182, 130, 200, 119, 169, 120)
 = X_{2,5} \cdot (9, 12, 8, 12)
\]
See Table 1 for a list of values of $\pvr(n, 2, 5)$ for $1 \leq n \leq 128$.
\end{eg*}
\section*{Properties of Stern-like sequences}

\begin{lem*}
The usual $b$-nary partition of $n$ is lexicographically greatest
among $pvp(n, b, c)$ when $b \leq c$.
\end{lem*}

\begin{proof}
Let $s$ be the usual $b$-nary partition of $n$.
If $|s| = 1$ then $pvp(n, b, c) = \{s\}$ and the claim is true.
Assume that the claim is true for all $|s'| < m$ and that $|s| = m$.
Let $s'$ be such that $s \neq s'$ and $n = pve(s', b, c)$.
If $|s'| < |s|$ then $s \ltlex s'$ and there is nothing to show.
If $|s'| = |s|$ then either $s'(|s|) = s(|s|)$ or not.
If $|s'| = |s|$ then $s$ and $s'$ share a common prefix, namely $y$, that is,
\[
s = yw_s \eqand s' = yw_{s'}.
\]
But then $w_s$ is a $b$-nary partition such that $|w_s| < |s|$,
and therefore the induction hypothesis applies.
Otherwise $|s| = |s'|$ and $s(|s|) \neq s'(|s|)$.
If $s'(|s|) < s(|s|)$ then $s' \ltlex s$ and there is nothing to show.
Finally if $s(|s|) < s'(|s|)$ then
$pve(s', b) > n$ since $s$ is the $b$-nary representation of $n$.
That is, $n \leq s'(|s|)b^{|s|}$.
This contradicts our choice of $s'$ hence
the usual $b$-nary partition of $n$ is the lexicographically greatest
element of $\pvp(n, b, c)$ when $c \geq b$.
\end{proof}

\begin{lem*}[Common suffix property]
\label{suffix}
If $r, s, t \in b^{<\omega}, |r| = |s|,
 r(i) \neq 0$ and $s(i) \neq 0$ for all $i \in |r|$
then $S_b(\pve(tr, b)) = S_b(\pve(ts, b))$.
\end{lem*}

\begin{proof}
This can be seen by induction on $|r|$.
If $|r| = 0$ then $t = t$ and the claim is true.
If $|r| > 0$ then $r(0) \neq 0$ and $s(0) \neq 0$ therefore
$S_b(tr) = S_b(\rsh tr)$ and
$S_b(ts) = S_b(\rsh ts)$.
Thus $\rsh tr = t(\rsh r), \rsh ts = t(\rsh s)$ and
$|\rsh s| = |\rsh r| = |r| - 1 < |r|$
therefore the induction hypothesis applies and
$S_b(st) = S_b(\rsh st) = S_b(\rsh rt) = S_b(rt)$.
\end{proof}

\begin{cor*}
Given $n > 0$, if the $b$-nary expansion of $n$ contains no zeroes
then $S_b(n) = 1$.
\end{cor*}

\begin{proof}
For $n = 1$ the assertion holds by definition.
If $n > 1$ and its $b$-nary expansion, say $s$, contains no zeros
then $\rsh s$ is a $b$-nary expansion which contains no zeroes
and is shorter.
Therefore by the induction hypothesis
$S_b(n) = S_b(\pve(s,b)) = 1$.
\end{proof}

\begin{cor*}
\[
\pvrf\left(1, \frac{b^n-1}{b-1}+1, \frac{b^{n+1}-1}{b-1}-1, b, b+1\right)
 = (b-1)^n
\]
\end{cor*}

\begin{proof}
This can be seen by induction on $n$.
Define $u_n = \frac{b^n - 1}{b-1}$.
Define $F(i,n) = \pvrf(i, u_n, u_{n+1}-1, b, b+1)$.
Note that $F(1, 0) = 1$.
Therefore the induction hypothesis is then that
$F(1, n) = (b-1)^n$.
Assume that this holds for all $m \leq n$.
Then for all $i$ such that
$u_n + 1 \leq i \leq u_{n+1}$
and $\pvr(i, b, b+1) = S_b(i) = 1$
it is the case that $b \ndiv i$.
Otherwise $S_b(i)$ would be the sum of two positive values
and hence greater than $1$.
Further, for each such $i$ and $1 \leq j < b$,
\[
u_{n+1} + 1 \leq bi + j \leq u_{n+2}
\]
and by the recurrence,
$\pvr(bi + j, b, b+1) = S_b(bi + j) = S_b(i) = 1$.
Therefore
\[
F(1, n+1) = (b-1)F(1, n) = (b-1)^{n+1}
\]
and the induction hypothesis holds for $n+1$.
Thus
\[
\pvrf\left(1, \frac{b^n-1}{b-1}+1, \frac{b^{n+1}-1}{b-1}-1, b, b+1\right) = (b-1)^n
\]
for all $n$.
\end{proof}

\begin{dfn*}(Layer and related values)
Let $a_{b,n} = \frac{b^n - 1}{b - 1} + 1,
b_{b,n} = \frac{b^{n+1}-1}{b-1}$ and
$c_{b,n} = b^n - 1$.
Note that $b a_{b, n} = a_{b,n+1} + b - 2$.
\begin{align*}
b a_{b, n}
& = b \left(\frac{b^n - 1}{b-1} + 1\right)
  = b \left(1 + \sum_{i \in n} b^i\right)\\
& = b + \sum_{i = 1}^{n} b^i
  = b - 2 + \left(1 + \sum_{i \in n+1} b^i\right)\\
& = b - 2 + \left(\frac{b^{n+1}-1}{b-1} + 1 \right)\\
b a_{b, n}
& = b - 2 + a_{b,n+1}
\end{align*}
Finally define the $n$th layer of the base $b$ Stern-like sequence as
\[
\Layer_b(n) = \prod_{a_{b,n}}^{b_{b,n}}\str(S_b(i)).
\]
\end{dfn*}
\begin{lem*}
\[
\Layer_b(n) = \Layer_b(n-1) X_n
\]
\end{lem*}
\begin{proof}
The equivalent result
\[
\tag{$\ast\ast$}
\label{layer-init}
i \leq c_n \implies S_b(i + a_{b, n+1}) = S_b(i + a_{b,n})
\]
may be seen by induction.
In the base case $S_b(1) = S_b(2) = 1$ is true by definiton.
Assume that (\ref{layer-init}) is true for $n = m-1$
and $i = bm + b - 2 \leq c_n$.
Note that $m < c_{n-1}$.
\begin{align*}
i = bm + b - 2 & \leq c_m\\
bm + b - 1 & \leq c_m + 1\\
m + \frac{b - 1}{b} & \leq b^{m-1}\\
m - \frac{1}{b} & \leq c_{m-1}
\end{align*}
Then since $m \in \integer \implies m \leq c_{n-1}$.

\begin{align*}
S_b(i + a_{b, m+1})
 &= S_b(bm + b - 2 + a_{b,m+1})\\
 &= S_b(b(m + a_{b,m}))\\
 &= S_b(m + a_{b,m}) + S_b(m - 1 + a_{b,m})\\
 &= S_b(m + a_{b,m-1}) + S_b(m - 1 + a_{b,m-1}) \text{ by IH }\\
 &= S_b(b(m + a_{b, m-1}))\\
 &= S_b(bm + ba_{b,m-1})\\
 &= S_b(bm + b - 2 + a_{b,m})\\
S_b(i + a_{b, m+1})
 &= S_b(i + a_{b,m}).
\end{align*}
\end{proof}

\begin{claim*}
\[
F_b(x)
= \sum_{i<\omega} S_b(i)x^i
= \prod_{j<\omega} \sum_{i\in b+1} x^{ib^j}
\]
\end{claim*}

\begin{claim*}
\[
F_b(x) = F_b(x^b)\sum_{i \in b+1} x^i
\]
\end{claim*}

\begin{proof}
\begin{align*}
F_b(x)
& = \prod_{j<\omega} \sum_{i\in b+1} x^{ib^j}\\
& = 
    \left(\prod_{0<j<\omega} \sum_{i\in b+1} x^{ib^j}\right)
    \left(\sum_{i \in b+1} x^i\right)\\
& = 
    \left(\prod_{j'<\omega} \sum_{i\in b+1} (x^b)^{ib^{j'}}\right)
    \left(\sum_{i \in b+1} x^i\right)\\
F_b(x)
& = F_b(x^b)\sum_{i \in b+1} x^i\\
\end{align*}
\end{proof}

\section*{The case of $S_3(n)$}
\begin{comment}
Let $T_3$ be a ternary tree with root labeled $1$
such that each child node is labeled with the label of the previous node
with added to an element of ${1, 2, 3}$.
Consider $S_3(n)$ applied to the labels on $T_3$, call this tree $S_3$.
Let the $l$th layer of a rooted tree be the set of nodes which are
a distance $l$ from the root.
Therefore the root is the $0$th layer, and the first layer
consists of $2, 3, 4$.
Each layer of $S_3$ is a concatenation of two palindromes,
the first being a concatenation of previous layers
and the other is made of new values.
\end{comment}
\noindent
Let
$a_n = \frac{3^n-1}{2} + 1,
 b_n = \frac{3^{n+1} - 1}{2}$ and
$c_n = 3^n-1$.

%An initial segment of each layer is a palindrome.
\begin{lem*}
For all $n \geq 0$
let $0 \leq j \leq a_n$, then
$S_3(c_n + j) = S_3(b_n - j)$.
\end{lem*}

\begin{proof}
Proceed by induction on $n$.
For $n = 0$ it is the case that $a_1 = 0, b_1 = 2, c_n = 1$
and $S_3(2) = S_3(1)$ which establishes the base case.
Now consider the case when $n > 0$.
Let $m$ and $m'$ be such that $c_n \leq m \leq m' \leq b_n$,
and $m + m' = b_n + c_n$.
This condition is equivalent to the premise of the assertion.

Assume $m$ is not a multiple of $3$
and define $k, k', r$ and $r'$ by
$m = 3k + r$, $m' = 3k' + r'$ where $\{r, r'\} \subset 3$.
Therefore $r + r' = 3$ since $m + m'$ is a multiple of $3$.
Note that this implies $k + k' = b_{n-1} + c_{n-1}$,
\begin{comment}
\begin{align*}
3k + r + 3k' + r' & = b_n + c_n
3k + r + 3k' + r' & = 3 b_{n-1} + 1 + 3 c_{n-1} + 2
3k + 3k' + 3  & = 3 b_{n-1} + 3 c_{n-1} + 3
k + k' & = b_{n-1} + c_{n-1}
\end{align*}
\end{comment}
hence by the induction hypothesis $S_3(k) = S_3(k')$.
By the recurrence, $S_3(m) = S_3(k)$ and $S_3(m') = S_3(k')$,
so $S_3(m) = S_3(m')$.

On the other hand if $m$ and $m'$ are multiples of $3$
then there is an integer $q$ such that
$m = c_n + 3q + 1$ and $m' = b_n - 3q - 1$.
Thus
\begin{align*}
S_3(m)  & = S_3(c_{n-1} + q + 1) + S_3(c_{n-1} + q)\\
S_3(m') & = S_3(b_{n-1} - q) + S_3(b_{n-1} - q - 1)
\end{align*}
and by the induction hypothesis
\begin{align*}
S_3(b_{n-1} - q) & = S_3(c_{n-1} + q)\\
S_3(b_{n-1} - q - 1) & = S_3(c_{n-1} + q + 1)
\end{align*}
hence $S_3(m) = S_3(m')$.
Consequently,
for all $n \geq 0$ if $0 \leq j \leq a_n$ then
$S_3(c_n + j) = S_3(b_n - j)$.
\begin{comment}
Note $k = \pve(\rsh s, b) = \floor{\frac{m}{3}}$
and let $k' = \pve(\rsh s', b) = \floor{\frac{m'}{3}}$
and $r'$ be such that $m' = 3k' + r'$.
Then $c_{n-1} \leq k, k' \leq b_{n-1}$ and
$k - c_{n-1} = b_{n-1} - k'$.
Therefore by the induction hypothesis $S_3(k) = S_3(k')$.
then $m = 3k + r$ for integers $k$ and $r$ with $r > 0$.
Let the ternary expansion of $m$ and $m'$ be $s$ and $s'$ respectively.
Further, $s(0)$ and $s'(0)$ are both not zero thus \ref{suffix} applies
and $S_3(m) = S_3(k) = S_3(k') = S_3(m')$.
\end{comment}
\end{proof}

\begin{lem*}
Let $n = 3k+2$.
Then $S_3(n) + S_3(n+2) = S_3(n+1)$.
\end{lem*}

\begin{proof}
This is strictly a derivation based on the recurrence for $S_3(n)$.
\begin{align*}
S_3(n+1)
 & = S_3(3k + 3) = S_3(3(k+1))\\
 & = S_3(k) + S_3(k+1)\\
 & = S_3(3k+2) + S_3(3(k+1)+1)\\
S_3(n+1)
 & = S_3(n) + S_3(n+2).
\end{align*}
\end{proof}

\begin{claim*}
\[
(3+1)^n = \sum_{i = a_n}^{b_n} S_3(i)
\]
\end{claim*}

Table 1
\[
\begin{tabular}{cccc}
$\begin{array}{c|c}
n & \pvr(n, 2, 5)\\ \hline
1 & 1\\
2 & 2\\
3 & 2\\
4 & 4\\
5 & 3\\
6 & 5\\
7 & 4\\
8 & 8\\
9 & 6\\
10 & 9\\
11 & 7\\
12 & 12\\
13 & 8\\
14 & 12\\
15 & 9\\
16 & 17\\
17 & 12\\
18 & 18\\
19 & 14\\
20 & 23\\
21 & 15\\
22 & 22\\
23 & 16\\
24 & 28\\
25 & 19\\
26 & 27\\
27 & 20\\
28 & 32\\
29 & 20\\
30 & 29\\
31 & 21\\
32 & 38\\
33 & 26\\
34 & 38\\
35 & 29\\
36 & 47\\
37 & 30\\
38 & 44\\
39 & 32\\
40 & 55\\
\end{array}$ &
$\begin{array}{c|c}
n & \pvr(n, 2, 5)\\ \hline
41 & 37\\
42 & 52\\
43 & 38\\
44 & 60\\
45 & 37\\
46 & 53\\
47 & 38\\
48 & 66\\
49 & 44\\
50 & 63\\
51 & 47\\
52 & 74\\
53 & 46\\
54 & 66\\
55 & 47\\
56 & 79\\
57 & 52\\
58 & 72\\
59 & 52\\
60 & 81\\
61 & 49\\
62 & 70\\
63 & 50\\
64 & 88\\
65 & 59\\
66 & 85\\
67 & 64\\
68 & 102\\
69 & 64\\
70 & 93\\
71 & 67\\
72 & 114\\
73 & 76\\
74 & 106\\
75 & 77\\
76 & 121\\
77 & 74\\
78 & 106\\
79 & 76\\
80 & 131\\
\end{array}$ &
$\begin{array}{c|c}
n & \pvr(n, 2, 5)\\ \hline
81 & 87\\
82 & 124\\
83 & 92\\
84 & 144\\
85 & 89\\
86 & 127\\
87 & 90\\
88 & 150\\
89 & 98\\
90 & 135\\
91 & 97\\
92 & 150\\
93 & 90\\
94 & 128\\
95 & 91\\
96 & 157\\
97 & 104\\
98 & 148\\
99 & 110\\
100 & 173\\
101 & 107\\
102 & 154\\
103 & 110\\
104 & 184\\
105 & 121\\
106 & 167\\
107 & 120\\
108 & 186\\
109 & 112\\
110 & 159\\
111 & 113\\
112 & 192\\
113 & 126\\
114 & 178\\
115 & 131\\
116 & 203\\
117 & 124\\
118 & 176\\
119 & 124\\
~\\
\end{array}$ &
$\begin{array}{c|c}
n & \pvr(n, 2, 5)\\ \hline
120 & 205\\
121 & 133\\
122 & 182\\
123 & 130\\
124 & 200\\
125 & 119\\
126 & 169\\
127 & 120\\
128 & 208\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
~\\
\end{array}$
\end{tabular}
\]
\end{document}

\begin{dfn*}[]
\end{dfn*}

\begin{eg*}
\end{eg*}

\begin{thm*}
\end{thm*}

\begin{proof}
\end{proof}
