\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*{\Mod}{Mod}
\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]{\lfloor{#1}\rfloor}
\newcommand{\minus}{\setminus}
\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|$.
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 bit 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*{Properties of 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 + i) & = S_b(n) \text{ for } 0 < i < 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$ is
\[
\pvp(n, b, c) = \set{s}{n = \pve(s, b), s \in c^{\omega}, s(|s|) \neq 0}.
\]
Further define the number of place value partitions of
$n$ base $b$ carrying at $c$ as
\[
\pvr(n, b, c) = |\pvp(n, b, c)|
\]
and 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{lem*}
The usual $b$-ary partition of $n$ is lexicographically greatest
among $pvp(n, b, c)$ when $c \geq b$.
\end{lem*}

\begin{lem*}
If $r, s, t \in b^{<\omega}, rt = st$ and 
$t(i) \neq 0$ for all $i \in |t|$
then $S_b(\pve(rt, b)) = S_b(\pve(st, b))$.
\end{lem*}

\begin{cor*}
If the $b$-ary expansion of $n$ contains no zeroes
then $S_b(n) = 1$.
\end{cor*}

\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{lem*}
\[
\pvrf\left(1, \frac{b^n-1}{b-1} + 1, \frac{b^{n+1}-b}{b-1}, b, b+1\right) = (b-1)^n
\]
\end{lem*}

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

\section*{The case of $S_3(n)$}

Let $a_n = \frac{3^n}{2} + 1$ and $b_n = \frac{3^n}{2}$.

\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{lem*}
Let $m, n > 1$.
If there exists $i, j$ such that
$m = c_i + j$ and $n = b_i - j$
then $S_3(m) = S_3(n)$.
\end{lem*}

\end{document}

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

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

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

\begin{proof}
\end{proof}
