\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 Largest Values for the Stern Sequence
}
\vskip 1cm
\large
Jennifer Lansing\\
Department of Mathematics\\
University of Illinois at Urbana Champaign\\
1409 W. Green St\\
Urbana, IL 61801\\
USA\\
\href{mailto:jlweber@illinois.edu}{\tt jlweber@illinois.edu}
\end{center}

\vskip .2 in

\begin{abstract}
In 1858, Stern introduced an array, later called the diatomic array.
The array is formed by taking two values $a$ and $b$ for the first row,
and each succeeding row is formed from the previous by inserting $c+d$
between two consecutive terms with values $c$, $d$.  This array has
many interesting properties, such as the largest value in a row of the
diatomic array is the $(r+2)$-th Fibonacci number, occurring roughly
one-third and two-thirds of the way through the row.  In this paper, we
show each of the second and third largest values in a row of the
diatomic array satisfy a Fibonacci recurrence and can be written as a
linear combination of Fibonacci numbers.  The array can be written in
terms of a recursive sequence, denoted $s(n)$ and called the Stern
sequence.  The diatomic array also has the property that every third
term is even.  In function notation, we have $s(3n)$ is always even.
We introduce and give some properties of the related sequence defined
by $w(n)=s(3n)/2$.
\end{abstract}

\section{Historical background}

The Stern sequence, denoted by $s(n)$, satisfies the recurrences
\[ 
s(2n)=s(n) \quad \text{and} \quad s(2n+1)=s(n+1)+s(n)
\]
for $n\ge 1$, with $s(0)=0$ and $s(1)=1$.   The first few values of this sequence are
\[
0, \; 1, \; 1,\; 2,\; 1,\; 3,\; 2,\; 3,\; 1,\; 4,\; 3,\; 5, \ldots
\]
This sequence has many properties, including $s(n)$ is even if and only if $3$ divides $n$, and
\[
\sum_{n=2^r}^{2^{r+1}-1} s(n)=3^r.
\]

In 1858, Stern \cite{mS1} constructed an array by taking two values $a$ and $b$, which give the first row, and then he formed the next row by rewriting the previous row and inserting the sum $a+b$ between its summands.  Stern studied the properties of this general array, but he also examined the case where $a=b=1$.  The numerous properties of this $(1,1)$ array, later called the diatomic array by Lehmer, are summarized by Lehmer \cite{dL1}.  The diatomic array is given in Table \ref{diatomicarray}.    
\begin{table}[h!]
\begin{center}
\scalebox{0.75}{
\begin{tabular}{ccccccccccccccccccccccccccccccccc}
& & & & & & & & & & & & & & & 1 &   & 1& & & & & & & & & \\ 
& & & & & & & & & & & & & & & 1 & 2 & 1& & & & & & & & & \\ 
& & & & & & & & & & & & & & 1 & 3 & 2 & 3 & 1& & & & & & & & \\ 
& & & & & & & & & & & & 1 & 4 & 3 & 5 & 2 & 5 & 3 & 4 & 1 & & & & & & \\
& & & & & & & & 1 & 5 & 4 & 7 & 3 & 8 & 5 & 7 & 2 & 7 & 5 & 8 & 3 & 7 & 4 & 5 & 1 & & & & & & & & \\
1 & 6 & 5 & 9 & 4 & 11 & 7 & 10 & 3 & 11 & 8 & 13 &5 & 12 & 7 & 9 & 2 & 9 & 7 & 12 & 5 & 13 & 8 & 11 & 3 & 10 & 7 & 11 & 4 & 9 & 5 & 6 & 1
\end{tabular}
}
\medskip

\caption{Diatomic Array for $s(n)$}
\end{center}\label{diatomicarray}
\end{table}

One of the most obvious properties of the diatomic array is the symmetry.  In terms of the sequence notation, the symmetry is noted as
\begin{equation}\label{symmetry}
s(n)=s(n^*) \text{ where }n^*:=3\cdot 2^r-n \text{ for }2^r \le n \le 2^{r+1}.
\end{equation}
Stern also considered the array starting with $(0,1)$, given in Table \ref{DA2}, and this array looks more like the sequence $s(n)$.  In fact, the $r$-th row of the $(0,1)$ array is given by $s(n)$ for $0 \le n \le 2^r$, and the $r$-th row of the diatomic array is given by $s(n)$ for $2^r\le n \le 2^{r+1}$.  
\begin{table}[h!]
\begin{center}
\scalebox{0.8}{
\begin{tabular}{ccccccccccccccccccccccccccccccccc}
 & & & & & & & & & & & & & & & 0 &   & 1& & & & & & & & & \\ 
 & & & & & & & & & & & & & & & 0 & 1 & 1& & & & & & & & & \\ 
 & & & & & & & & & & & & & & 0 & 1 & 1 & 2 & 1& & & & & & & & \\ 
 & & & & & & & & & & & & 0 & 1 & 1 & 2 & 1 & 3 & 2 & 3 & 1 & & & & & & \\
 & &  & & & & & & 0 & 1 & 1 & 2 & 1 & 3 & 2 & 3 & 1 & 4 & 3 & 5 & 2 & 5 & 3 & 4 & 1 & & & & & & & & \\
0 & 1 & 1 & 2 & 1 & 3 & 2 & 3 & 1 & 4 & 3 & 5 & 2 & 5 & 3 & 4 & 1 & 5 & 4 & 7 & 3 & 8 & 5 & 7 & 2 & 7 & 5 & 3 & 3 & 7 & 4 & 5 & 1
\end{tabular}
}
\end{center} 

\medskip

\caption{$(0,1)$  Array} \label{DA2}
\end{table}
For more information, Reznick \cite{bR1} gives many recurrence and regularity properties of the Stern sequence, and Northshield \cite{sN1} also gives a nice history of the sequence.  See also sequence \seqnum{A002487} in Sloane's Online Encyclopedia of Integer Sequences \cite{oeis}.  

\section{Largest values} 
In 1878, Lucas \cite{eL1} studied Stern's diatomic array, and noted that the largest value in the $r$-th row is a Fibonacci number, occurring roughly at 
one-third and two-thirds of the way in the row.  We now ask, what are the second and third largest values in a row of the diatomic array?

\begin{definition}
Let $L_m(r)$ denote \textit{the $m$-th largest distinct value in the $r$-th row of the Stern sequence}.  The maximum of the $r$-th row is denoted by $L_1(r)$, the second largest value is denoted by $L_2(r)$, and so forth.
\end{definition}

We restate Lucas's theorem, which was also later proved by Lehmer \cite{dL1}. 

\begin{theorem}\label{L1}
For all $r \ge 0$, we have $L_1(r)=F_{r+2}$.  Moreover, this maximum occurs for the values $n_r=(4\cdot 2^{r}-(-1)^r)/3$, as well as $n_r^*=(5 \cdot 2^r+(-1)^r)/3$ by symmetry.
\end{theorem}

This theorem is proved by an easy induction, which we omit.  The relationship between the position of the maximum of the $r$-th row and that of the $(r-1)$-th row is quite important.  We have 
\begin{equation}\label{n-r}
n_r=2n_{r-1}-(-1)^r,
\end{equation}
which means the maximum for the $r$-th row will alternate between appearing on the left or right side of the previous maximum in the diatomic array.  Similarly, $n_r^*=2n_{r-1}^*+(-1)^r$, by the mirror symmetry of the second half of the row.

\section{Second Largest Value for $s(n)$}

Using Mathematica, we can easily compute the second largest value in a particular row of the diatomic array.  The second largest values are given in Table \ref{Tab:SecLargest}, and they follow a Fibonacci recurrence relation, $L_2(r)=L_2(r-1)+L_2(r-2)$, for $r\ge 6$.
\begin{table}[htb!]
 \begin{center}
 \caption{Second Largest Values of $s(n)$ in rows}
\medskip
  \begin{tabular}{ccc}
row $r$ & $n$ & $L_2(r)$ \\ \hline
1 &  2, 4 & 1  \\
2 & 6 & 2  \\
3 & 9, 15 & 4 \\
4 & 19, 23, 25, 29 & 7 \\
5 & 45, 51 & 12  \\
6 & 83, 91, 101, 109 & 19 \\
7 & 173, 181, 203, 211 & 31 \\
8 & 339, 363, 405, 429 & 50 \\
9 & 685, 725, 811, 851 & 81 \\
10 & 1363, 1451, 1621, 1709 & 131 \\
11 & 2733, 2901, 3243, 3411 & 212 \\
12 & 5459, 5803, 6485, 6829 & 343 \\
  \end{tabular}
  \label{Tab:SecLargest}
 \end{center} 
\end{table} 
However, starting in the 4th row, there are 4 occurrences of the second largest value.  Two of them come from adding the second largest values from the two preceding rows, $L_2(r-1)+L_2(r-2)$, while the other two come from a linear combination of previous maximum values, $2L_1(r-2)+L_1(r-4)$.  The second way of obtaining the second largest value, from $2L_1(r-2)+L_1(r-4)$, will occur either 2 to the left or right of where $L_1(r)$ occurs in the row.  The Stern sequence achieves these second largest values for explicitly describable $n$.  

\begin{definition}
For $r \ge 4$, let 
\[
n_{2,1}(r):=\frac{17\cdot 2^{r-2}-(-1)^{r-1}}{3} \quad  \text{and} \quad n_{2,2}(r):=\frac{16 \cdot 2^{r-2}-7(-1)^{r}}{3}.
\]
\end{definition}
By the symmetry defined earlier in \eqref{symmetry}, we have
\[
n_{2,1}^*(r)=\frac{19\cdot 2^{r-2}+(-1)^{r-1}}{3} \quad \text{and} \quad n_{2,2}^*(r)=\frac{20\cdot 2^{r-2}+7(-1)^{r}}{3}.
\]
Note that $n_{2,1}(r)$ and $n_{2,2}(r)$ coalesce at $r=5$ so that there are only two occurrences of $L_2(5)$.

We observe $s(n_{2,1}(r))$ and $s(n_{2,1}^*(r))$ give the second largest value in the $r$-th row as a sum of preceding second largest values, 
and $s(n_{2,2}(r))$ and $s(n_{2,2}^*(r))$ give the second largest value of the $r$-th row as a linear combination of previous maximum values.  Also note $n_{2,1}(r)$ has a similar recurrence relation as $n_r$ in \eqref{n-r}: 
\begin{equation}\label{n-r-1}
n_{2,1}(r)=\frac{17\cdot 2^{r-2}+2(-1)^{r-1}-3(-1)^{r-1}}{3} =2n_{2,1}(r-1)+(-1)^r.
\end{equation}
We will also need 
\begin{equation}\label{n-r-2}
n_{2,2}(r)=4n_{r-2}-(-1)^r=n_r -2(-1)^r,
\end{equation}
and the last equality makes it explicit that the second way of obtaining the second largest value, from \\
$2L_1(r-2)+L_1(r-4)$, will occur either two to the left or right of where $L_1(r)$ occurs in the row.  

\begin{theorem} \label{Stern-SecondLarge}
\begin{enumerate}
\item[\textup{(i)}] $L_2(r)=F_{r+2}-F_{r-3}=L_1(r)-F_{r-3}$, for $r \ge 4$.
\item[\textup{(ii)}] $s(n_{2,1}(r))=s(n_{2,1}^*(r))=s(n_{2,2}(r))=s(n_{2,2}^*(r))=L_2(r)$, for $r \ge 4$.  
\item[\textup{(iii)}] For $n_{2,1}(r)$ and $n_{2,1}^*(r)$, $L_2(r)$ arises from the sum $L_2(r-1)+L_2(r-2)$, for $r \ge 6$.  
\item[\textup{(iv)}] For $n_{2,2}(r)$ and $n_{2,2}^*(r)$, $L_2(r)$ arises from the sum $2L_1(r-2)+L_1(r-4)$, for $r\ge 8$.
\end{enumerate}
\end{theorem}

\begin{proof}
The induction base is clear and easily verified.  Assume (i)-(iv) hold for all rows before and including the $r$-th row, with $r\ge 8$.  

We first show that besides the maximum value, there is no element larger than $L_2(r)+L_2(r-1)$ in the $(r+1)$-th row. If $2k \in [2^{r+1}, 2^{r+2}]$, then using the induction hypothesis from part (i), we find that for all the even values in the $(r+1)$-th row 
\[
s(2k)=s(k) \le L_1(r)=F_{r+2}<F_{r+2}+2F_{r-1}=F_{r+3}-F_{r-2}=L_2(r)+L_2(r-1).
\]
We now want to obtain a bound on the odd values in the $(r+1)$-th row, and more specifically $s(4k \pm1)$.  Now let $k \in [2^{r-1}, 2^{r}]$ such that $4k\pm 1 \in (2^{r+1},2^{r+2})$.  We examine some special cases first.  If $k= n_{r-1}$,  or $k=n_{r-1}^*$, we have 
\[
 s(2n_{r-1}-(-1)^r)=s(n_r)=L_1(r)=s(n_r^*)=s(2n_{r-1}^*+(-1)^r),
\]
which implies $s(2n_{r-1}+(-1)^r)<L_1(r)$ and $s(2n_{r-1}^*-(-1)^r)<L_1(r)$.  Similarly, if  $k=2n_{r-2}$ or $k=2n_{r-2}^*$, we have
\[
s(2\cdot 2n_{r-2}+(-1)^r)=s(n_r)=L_1(r)=s(n_r^*)=s(2\cdot 2n_{r-2}^*-(-1)^r),
\]
which means $s(2\cdot 2n_{r-2}-(-1)^r)<L_1(r)$ and $s(2\cdot 2n_{r-2}^*+(-1)^r)<L_1(r)$.  Except for these special cases where $k=n_{r-1}$, $n_{r-1}^*$, $2n_{r-2}$, or $2n_{r-2}^*$, we have $s(2k \pm 1)<L_1(r)$, and therefore $s(2k \pm 1) \le L_2(r)$.  Then we have 
\[
s(4k \pm 1)=s(2k)+s(2k \pm 1)=s(2k \pm 1)+s(k) \le L_2(r)+L_2(r-1). 
\]
We now examine the special cases more closely.  If $k=n_{r-1}$, we have
\[
s(4n_{r-1}-(-1)^r)=s(2n_{r-1})+s(2n_{r-1}-(-1)^r)=s(n_{r-1})+s(n_r)=L_1(r+1),
\]
but we can disregard this (largest) value, since we are looking for the second largest value.  Now, we also have
\begin{align}
s(4n_{r-1}+(-1)^r)&=s(2n_{r-1})+s(2n_{r-1}+(-1)^r) \nonumber \\
&=s(n_{r-1})+s(n_{r-1})+s(n_{r-1}+(-1)^r) \nonumber \\
&=2s(n_{r-1})+s(2n_{r-2}+2(-1)^r) \nonumber \\
&=2s(n_{r-1})+s(n_{r-2}+(-1)^r) \nonumber \\
&=2s(n_{r-1})+s(2n_{r-3}-(-1)^r+(-1)^r) \nonumber \\
&=2s(n_{r-1})+s(n_{r-3}) \nonumber \\
&=2L_1(r-1)+L_1(r-3). \label{s-n2-r}
\end{align}
Note that by symmetry we have $s(4n_{r-1}^*-(-1)^r)=2L_1(r-1)+L_1(r-3)$ and $s(4n_{r-1}^*+(-1)^r)=L_1(r)$.  Lastly, if $k=2n_{r-2}$ we have  
\begin{align*}
s(4 \cdot 2n_{r-2} \pm 1)&=2s(n_{r-2})+s(2n_{r-2} \pm 1)\\
&=\begin{cases}
2s(n_{r-2})+s(2n_{r-2} +(-1)^r)\\
2s(n_{r-2})+s(2n_{r-2} -(-1)^r)\\
\end{cases}\\
&=\begin{cases}
2s(n_{r-2}+s(n_{r-1})=2L_1(r-2)+L_1(r-1)  \\
3s(n_{r-2})+s(n_{r-4})=3L_1(r-2)+L_1(r-4) \\
\end{cases}\\
&<2L_1(r-1)+L_1(r-3).  
\end{align*}
So now we only need compare $2L_1(r-1)+L_1(r-3)$ to $L_2(r)+L_2(r-1)$.  However, using part (i) from the induction hypothesis, we have
\begin{align*}
L_2(r)+L_2(r-1)&=F_{r+2}-F_{r-3}+F_{r+1}-F_{r-4}\\
&=F_{r+3}-F_{r-2}=L_1(r+1)-L_1(r-4)\\
&=2L_1(r-1)+L_1(r-3).
\end{align*}
Thus, all elements in the $(r+1)$-th row, besides the maximum, are less than or equal to $L_2(r)+L_2(r-1)$, and so we have 
\begin{equation*}
L_2(r+1)=F_{r+3}-F_{r-2}=L_2(r)+L_2(r-1)=2L_1(r-1)+L_1(r-3). 
\end{equation*}
All that is left is to verify the second largest values occur for the $n$ given earlier.  Evaluating $s(n_{2,1}(r+1))$ and using \eqref{n-r-1}, we have 
\begin{align*}
s(n_{2,1}(r+1))&=s(2n_{2,1}(r)+(-1)^{r+1})=s(n_{2,1}(r))+s(n_{2,1}(r)-(-1)^r)\\
&=s(n_{2,1}(r))+s(2n_{2,1}(r-1))\\
&=s(n_{2,1}(r))+s(n_{2,1}(r-1))\\
&=L_2(r)+L_2(r-1).
\end{align*}
We also note that by \eqref{n-r-2} we have $n_{2,2}(r+1)=4n_{r-1}+(-1)^r$, and in \eqref{s-n2-r} we see that $s(4n_{r-1}+(-1)^r)$ also gives $L_2(r)$.  Therefore, the second largest values occur where we expect.  Finally, by the symmetry of the Stern sequence in rows, we have 
\[
s(n_{2,1}^*(r+1))=s(n_{2,1}(r+1))=L_2(r+1)=s(n_{2,2}(r+1))=s(n_{2,2}^*(r+1)). \qedhere
\]
\end{proof}

\section{Third Largest Value for $s(n)$}

The third largest values in a row for $s(n)$, given in Table \ref{Tab:ThirdLargest}, also eventually satisfy a Fibonacci recurrence. This recurrence starts in the 10th row, and rows 8 and 9 give the two initial values.    
\begin{table}[htb!]
 \begin{center}
 \caption{Third Largest Values of $s(n)$ in rows}
\medskip
  \begin{tabular}{ccc}
row $r$ & $n$ & $L_3(r)$ \\ \hline
1 & N/A & N/A  \\
2 & 4 & 1  \\
3 & 10, 14 & 3 \\
4 & 17, 22, 26, 31 & 5 \\
5 & 37, 41, 55, 59 & 11  \\
6 & 75, 87, 105, 117 & 18 \\
7 & 165, 219 & 30 \\
8 & 331, 347, 421, 437 & 49 \\
9 & 693, 843 & 80 \\
10 & 1355, 1387, 1685, 1717 & 129 \\
11 & 2741, 2773, 3371, 3403 & 209 \\
12 & 5451, 5547, 6741, 6837 & 338 \\
  \end{tabular}
  \label{Tab:ThirdLargest}
 \end{center} 
\end{table}
Similar to the second largest value in a row, there are 4 occurrences of the third largest value.  By symmetry, two of them come from $L_3(r-1)+L_3(r-2)$, and the other two come from the sum of $(2L_1(r-4)+L_1(r-6))+(3L_1(r-4)+2L_1(r-6))$, which adds to $5L_1(r-4)+3L_1(r-6)$.  

The values of $n$ where the third largest values occur also follow a pattern, starting in the eighth row.  For the outside left and right values, it appears that the next value is two times the previous value plus or minus 31.  The inside right and left values follow the pattern, two times the previous value plus or minus one.  Taking this recurrences and iterating them, we obtain the following apparent closed form for these values.

\begin{definition}
For $r \ge 8$, let 
\[
n_{3,1}(r):=\frac{64\cdot 2^{r-4}-31(-1)^r}{3}  \quad \text{and} \quad n_{3,2}(r):=\frac{65\cdot 2^{r-4}+(-1)^r}{3}.
\]
\end{definition}
By symmetry, we have
\[
n_{3,1}^*(r)=\frac{80\cdot 2^{r-4}+31(-1)^r}{3}  \quad \text{and} \quad n_{3,2}^*(r)=\frac{79\cdot 2^{r-4}-(-1)^r}{3} .
\]
We will show that $n_{3,1}(r)$, $n_{3,1}^*(r)$, $n_{3,2}(r)$, and $n_{3,2}^*(r)$ give the third largest values for $s(n)$ in the $r$-th row.  It is useful to note 
\begin{equation}\label{n31rel}
n_{3,1}(r)=\frac{4\cdot 2^r-(-1)^r-30(-1)^r}{3}=n_r-10(-1)^r.
\end{equation}
This tells us that the first (and by symmetry, the last) occurrence of the third largest value in the row will be either 10 to the left or 10 to the right of the largest values, depending on the parity of the row. We also remark that $n_{3,2}(r)$ satisfies the recurrence relations
\begin{equation}\label{n32rel}
n_{3,2}(r)=2n_{3,2}(r-1)+(-1)^r \quad \text{and} \quad n_{3,2}(r)-(-1)^r=2n_{3,2}(r-1).
\end{equation}

\begin{theorem}\label{Stern-ThirdLarge}
\begin{enumerate}
\item[\textup{(i)}] $L_3(r)=L_{2}(r)-F_{r-7}=F_{r+1}+5F_{r-4}=L_1(r)-3F_{r-5}$, for $r \ge 8$.
\item[\textup{(ii)}] $s(n_{3,1}(r))=s({n_{3,1}^*(r)})=s(n_{3,2}(r))=s(n_{3,2}^*(r))=L_3(r)$, for $r \ge 8$.  
\item[\textup{(iii)}] For $n_{3,1}(r)$ and $n_{3,1}^*(r)$, $L_3(r)$ arises from the sum $5L_1(r-4)+3L_1(r-6)$, for $r\ge 8$.
\item[\textup{(iv)}] For $n_{3,2}(r)$ and $n_{3,2}^*(r)$, $L_3(r)$ arises from the sum $L_3(r-1)+L_3(r-2)$, for $r \ge 10$.  
\end{enumerate}
\end{theorem}

\begin{proof}
We proceed by induction.  Again, the base case is easily verified.  Assume the induction hypotheses hold for all values below $r>10$.  We will first verify that $L_3(r)+L_3(r-1)$ and $5L_1(r-3)+3L_1(r-5)$ are achieved at the expected values.  We will then show that all values in the $(r+1)$-th row, except for $L_1(r+1)$ and $L_2(r+1)$, are less than or equal to $L_3(r)+L_3(r-1)=F_{r+2}+5F_{r-3}$. 

We first verify that $s(n_{3,2}(r+1))=L_3(r)+L_3(r-1)$.  Using \eqref{n32rel}, we have  
\begin{align*}
s(n_{3,2}(r+1))&=s(2n_{3,2}(r)-(-1)^r)=s(n_{3,2}(r))+s(n_{3,2}(r)-(-1)^r)\\
&=L_3(r)+s(2n_{3,2}(r-1))\\
&=L_3(r)+L_3(r-1).
\end{align*}
Now considering $s(n_{3,1}(r+1))$, and using \eqref{n31rel} and \eqref{n-r} we have
\begin{align*}
s(n_{3,1}(r+1))&=s(n_{r+1}+10(-1)^r)=s(2n_r+(-1)^r+10(-1)^r)\\
&=s(n_r +5(-1)^r)+s(n_r +5(-1)^r+(-1)^r)\\
&=s(2n_{r-1}-(-1)^r+5(-1)^r)+s(2n_{r-1}+6(-1)^r-(-1)^r)\\
&=s(n_{r-1}+2(-1)^r)+s(n_{r-1}+3(-1)^r)+s(n_{r-1}+3(-1)^r-(-1)^r)\\
&=2s(n_{r-1}+2(-1)^r)+s(n_{r-1}+3(-1)^r)\\
&=2s(2n_{r-2}+(-1)^r+2(-1)^r)+s(2n_{r-2}+(-1)^r+3(-1)^r)\\
&=2s(n_{r-2}+(-1)^r)+2s(n_{r-2}+2(-1)^r)+s(n_{r-2}+2(-1)^r) \\
&=2s(n_{r-3})+3s(2n_{r-3}+(-1)^r)\\
&=2s(n_{r-3})+3s(n_{r-3})+3s(n_{r-3}+(-1)^r)\\
&=5s(n_{r-3})+3s(2n_{r-4}+2(-1)^r)\\
&=5s(n_{r-3})+3s(n_{r-4}+(-1)^r)\\
&=5s(n_{r-3})+3s(2n_{r-5})\\
&=5L_1(r-3)+3L_1(r-5).
\end{align*}
We also note by hypothesis (i), we have 
\begin{equation}\label{L3-Fib-L1rel}
L_3(r)+L_3(r-1)=F_{r+3}-3F_{r-4}=5F_{r-1}+3F_{r-3}=5L_1(r-3)+3L_1(r-5).
\end{equation}
We now show that all values in the $(r+1)$-th row, except for $L_1(r+1)$ and $L_2(r+1)$, are less than or equal to $L_3(r)+L_3(r-1)=F_{r+2}+5F_{r-3}$. First note that for $2k \in [2^{r+1},2^{r+2}]$, we have 
\[
s(2k)=s(k) \le L_1(r)=F_{r+2}<F_{r+2}+5F_{r-3}=L_3(r)+L_3(r-1).
\]
For the odd values in the $(r+1)$-th row, we eliminate the cases that anything larger than $L_3(r)+L_3(r-1)$ can come from the first, second or third largest values and a neighbor.  Now consider $s(2k+1)=s(k)+s(k+1)$, and let $b$ represent the larger of $s(k)$ and $s(k+1)$, which comes from the $r$-th row, and $c$ denote the smaller value coming from the $(r-1)$-th row.   

If $b$ is $L_1(r)$, then $c$ is either $L_1(r-1)$ or $L_1(r-2)$.  However, $L_1(r)+L_1(r-1)$ gives the largest value in the $(r+1)$-th row, so we can ignore this value.  Observe that  
\begin{equation*}
L_1(r)+L_1(r-2)=F_{r+2}+F_{r}<F_{r+2}+5F_{r-3}
\end{equation*}
is too small. So then it must be the case that $b\le L_2(r)$.  Now, there are 2 distinct ways of obtaining $L_2(r)$.  If $b=L_2(r)$, then $c$ could be $L_2(r-1)$ or $L_2(r-2)$.  But $L_2(r)+L_2(r-1)$ gives $L_2(r+1)$ and we can ignore this value.  We also have 
\begin{align*}
L_2(r)+L_2(r-2)&=F_{r+2}-F_{r-3}+F_r-F_{r-4}=F_{r+2}+F_{r-2}+2F_{r-4}\\
&<F_{r+2}+5F_{r-3}=L_3(r)+L_3(r-1),
\end{align*}
so this value is too small.  But if $b=2L_1(r-2)+L_1(r-4)$, then $c$ is $L_1(r-2)$ or $L_1(r-2)+L_1(r-4)$, and we only need to consider the latter.  We have
\begin{align*}
2L_1(r-2)+L_1(r-4)+L_1(r-2)+L_1(r-4&)=3F_r+2F_{r-2}\\
&<F_{r+2}+5F_{r-3}=L_3(r)+L_3(r-1),
\end{align*}
which implies $b\le L_3(r)$.  If $b=L_3(r)$, there are 2 distinct ways of obtaining $L_3(r)$.  If $b=L_3(r)$, then $c$ could be $L_3(r-1)$ or $L_3(r-2)$, but we can disregard these because we want to find something larger.  If $b=5L_1(r-4)+3L_1(r-6)$, then $c$ could be $2L_1(r-4)+L_1(r-6)$ or $3L_1(r-4)+2L_1(r-6)$.  We need only consider the latter, and we have 
\begin{align*}
5L_1(r-4)+3L_1(r-6)+3L_1(r-4)+2L_1(r-6)&=8F_{r-2}+5F_{r-4}\\
&<F_{r+2}+5F_{r-3}=L_3(r)+L_3(r-1),
\end{align*}
which implies $b<L_3(r)$.  However $c$ might be a large value in the $(r-1)$-the row to make up for $b$ being so small.  Now, we know $c<b<L_3(r)$, that $c$ comes from the $(r-1)$-th row, and that $c>L_3(r-1)$. If $c=L_1(r-1)$, then $b$ could only be $L_1(r-2)+L_1(r-3)$ (since we already eliminated $b=L_1(r)$).  But then $b+c=2L_1(r-1)+L_1(r-3)=L_2(r+1)$, and we can also ignore this value.  Then $c$ must be $L_2(r-1)$, and the only possibility for $b$ is $L_2(r-1)+L_2(r-3)$ (as we already eliminated $b=L_2(r)$).  By Theorem \ref{Stern-SecondLarge} (i) and the induction hypothesis (i), we have  
\begin{align}\label{L2-L3rel}
L_2(r+1)-F_{r-6}&=L_2(r)+L_2(r-1)-F_{r-6} \notag\\
&=L_3(r)+F_{r-7}+L_3(r-1)+F_{r-8}-F_{r-6} \notag \\
&=L_3(r)+L_3(r-1).
\end{align}
Using \eqref{L2-L3rel}, we have
\begin{align*}
b+c&=2L_2(r-1)+L_2(r-3)\\
&=2L_1(r-1)-2F_{r-4}+L_1(r-3)-F_{r-6}\\
&=L_2(r+1)-2F_{r-4}-F_{r-6}\\
& <L_2(r+2)-F_{r-6}=L_3(r)+L_3(r-1).
\end{align*}
Finally, we have that $c$ could be $L_2(r-1)=2L_1(r-3)+L_1(r-5)$ and $b$ could be $3L_1(r-3)+2L_1(r-5)$ or $3L_1(r-3)+L_1(r-5)$.  Then by \eqref{L3-Fib-L1rel} we see 
\[
L_3(r)+L_3(r-1)=5L_1(r-3)+3L_1(r-5)>5L_1(r-3)+2L_1(r-5),
\]
so that $5L_1(r-3)+2L_1(r-5)$ is too small, while $5L_1(r-3)+3L_1(r-5)$ gives $L_3(r)+L_3(r-1)$.  
This eliminates all possibilities and shows nothing can be between $L_3(r)+L_3(r-1)$ and $L_2(r+1)$, so that $s(2k+1)\le L_3(r)+L_3(r-1)$.  Thus, we have $L_3(r+1)=L_3(r)+L_3(r-1)$.
\end{proof} 

Since the next row in the diatomic array is formed by inserting the sum of two consecutive terms in between them, it makes sense that the $k$-th largest value in the $r$-th row will satisfy a Fibonacci recurrence.  This appears to hold true for the 4th, 5th, and 6th (distinct) largest value in a row, for a sufficiently large row value.  
\begin{table}[htb!]
 \begin{center}
 \caption{$L_m$ of $s(n)$ in rows}
\medskip
  \begin{tabular}{crrrrrr}
row $r$ & $L_1(r)$ & $L_2(r)$ & $L_3(r)$ & $L_4(r)$ & $L_5(r)$ & $L_6(r)$ \\ \hline
3 & 5 & 4 & 3 & 2 & 1  & N/A \\
4 & 8 & 7 & 5 & 4 & 3 & 2 \\
5 & 13 & 12 & 11 & 10 & 9 & 8 \\
6 & 21 & 19 & 18 & 17 & 16 & 15 \\
7 & 34 & 31 & 30 & 29 & 27 &  26 \\
8 & 55 & 50 & 49 & 47 & 46 & 45 \\
9 & 89 & 81 & 80 & 79 & 76 & 75 \\
10 & 144 & 131 & 129 & 128 & 123 & 121 \\
11 & 233 & 212 & 209 & 208 & 207 & 199 \\
12 & 377 & 343 & 338 & 337 & 335 & 322 \\
13 & 610 & 555 & 547 & 546 & 545 & 542 \\
14 & 987 & 898 & 885 & 883 & 882 & 877 \\
15 & 1597 & 1453 & 1432 & 1429 & 1428 & 1427 \\
16 & 2584 & 2351 & 2317 & 2312 & 2311 & 2309 \\
17 & 4181 & 3804 & 3749 & 3741 & 3740 & 3739\\
18 & 6765 & 6155 & 6066 & 6053 & 6051 & 6050\\
19 & 10946 & 9959 & 9815 & 9794 & 9791 & 9790\\
20 & 17711 & 16114 & 15881 & 15847 & 15842 & 15841\\
21 & 28657 & 26073 & 25696 & 25641 & 25633 & 25632 \\
22 & 46368 & 42187 & 41577 & 41488 & 41475 & 41473\\
23 & 75025 & 68260 & 67273 & 67129 & 67108 & 67105 \\
  \end{tabular}
  \label{Tab:456Largest}
 \end{center} 
\end{table}
We see in Table \ref{Tab:456Largest} a Fibonacci recurrence starts at the 14th row for $L_4$, the 18th for $L_5$, and the 22nd row for $L_6$.  This leads us to the following conjecture.

\begin{conjecture}
For all $r \ge 4m-2$, the $m$-th largest distinct value satisfies the recurrence $L_m(r)=L_m(r-1)+L_m(r-2)$.
\end{conjecture}

\begin{remark}
By Theorems \ref{Stern-SecondLarge} (i) and \ref{Stern-ThirdLarge} (i), we have $L_2(r)=F_{r+2}-F_{r-3}$ and $L_3(r)=L_2(r)-F_{r-7}$.  Note that $L_3(r)=F_{r+2}-F_{r-3}-F_{r-7}$.  Inspecting Table \ref{Tab:456Largest}, we notice the following: 
\begin{align*}
L_4(r)=&L_3(r)-F_{r-11}=F_{r+2}-F_{r-3}-F_{r-7}-F_{r-11} \quad \text{for $r \ge 12$},\\
L_5(r)=&L_4(r)-F_{r-15}=F_{r+2}-F_{r-3}-F_{r-7}-F_{r-11}-F_{r-15} \quad \text{for $r \ge 16$, and}\\
L_6(r)=&L_5(r)-F_{r-19}=F_{r+2}-F_{r-3}-F_{r-7}-F_{r-11}-F_{r-15}-F_{r-19} \quad \text{for $r \ge 20$.}
\end{align*}
This leads us to another conjecture.
\end{remark}
\begin{conjecture}\label{Largest-val-rel}
For $r \ge 4(m-1)$, we have 
\[
L_m(r)=L_{m-1}(r)-F_{r-(4m-5)}=F_{r+2}-\sum_{j=2}^{m}F_{r-(4j-5)}.
\]
\end{conjecture}

\section{The Distribution of Gaps}

In a previous paper, the author \cite{jL1} considered the classical question of the distribution of values for the Stern sequence.  A more modern question to consider is, what is the distribution of gaps?  There are numerous ways we could consider the gaps of the Stern sequence.  First, we can simply compute $s(n+1)-s(n)$.  Figure \ref{fig:Stern-gaps-1} plots the normalized difference for the 14th row.
\begin{figure}[htb]
\begin{center}
	\begin{minipage}[h]{3in}
		\includegraphics[width=3 in]{stern-distr-14.eps}
	\caption{Values of $s(n)$ in the 14th row}
	\label{fig:stern-distr-14}
	\end{minipage}
	\hfill
	\begin{minipage}[h]{3in}
		\includegraphics[width=3 in]{Stern-gaps-1.eps}
	\caption{$s(n+1)-s(n)$ for the 14th row}
	\label{fig:Stern-gaps-1}
	\end{minipage}
	\end{center}
\end{figure}
Figure \ref{fig:Stern-gaps-1} looks like the plot of $s(n)$, given in Figure \ref{fig:stern-distr-14}, with also a reflection over the $x$-axis.  If $n=2\ell$, we have 
\[
s(n+1)-s(n)=s(2\ell+1)-s(2\ell)=s(\ell+1).
\]
If $n=2\ell+1$, then we have
\[
s(n+1)-s(n)=s(2\ell+2)-s(2\ell+1)=-s(\ell).
\] 
From this perspective, the distribution of gaps is the same problem as the distribution of values. 

Another way to approach this problem is to order a row from largest to smallest and then take the difference of consecutive terms.  Since values occur at least twice in a row, we would have a lot of zeros.  If we eliminate repeated values when taking the difference, then we have a type of step function.  
\begin{figure}[ht]
	\begin{center}
	\begin{minipage}[h]{3in}
		\includegraphics[width=3in]{Stern-gaps-2.eps}
	\caption{Length of gaps for the 10th row}
	\label{fig:Stern-gaps-2}
	\end{minipage}
	\hfill
	\begin{minipage}[h]{3in}
		\includegraphics[width=3in]{Stern-gaps-3.eps}
	\caption{Length of gaps for the 14th row}
	\label{fig:Stern-gaps-3}
	\end{minipage}
	\end{center}
\end{figure}
Figures \ref{fig:Stern-gaps-2} and \ref{fig:Stern-gaps-3} give the differences of terms for the 10th row and the 14th row, after they have been sorted and repeated elements deleted.  

In the previous three sections, we discussed the largest three values in a row of the diatomic array, and we can use this information here.  First, we normalize the data by dividing by the largest possible value $F_{r+2}$.  By Theorems \ref{Stern-SecondLarge} and \ref{Stern-ThirdLarge}, we have the biggest gap is $F_{r-3}/F_{r+2}$, and the next gap is $F_{r-7}/F_{r+2}$.  If the conjecture $L_k(r)-L_{k-1}(r)=F_{r-(4k-5)}$ is true, then the distribution of gaps is $F_{r-(4k-5)}/F_{r+2}$ for $2\le k \le (r+5)/4$, with the smallest value being $1/F_{r+2}$.  The largest gaps are fixed, regardless of the row.  The smallest gaps then approach 0, for the later rows.  

This would mean the distribution of the gaps is not uniformly distributed.  If Conjecture \ref{Largest-val-rel} is true, then we have the following conjecture.
\begin{conjecture}
The normalized distribution of gaps for the Stern sequence is 
\[
\phi^{-(4k-3)} \text{ for } 2\le k \le (r+5)/4.
\]
\end{conjecture}

\section{A related sequence}

We introduce a new and related sequence.  As noted earlier, $s(3n)$ is always even, so we study the related sequence defined by
\[
w(n):=\frac{1}{2} s(3n).
\]
How does this sequence behave?  It has some similarities to the Stern sequence, such as symmetry of terms in a row in the diatomic array, the same average order of magnitude, and that the sum over powers of 2 is a power of 3.  However, $w(n)$ has a much more complicated structure; it has no simple generating function and the recursive definition is not as short.  

Table \ref{Tab:Values} gives a comparison of the first $64$ values of $s(n)$ and $w(n)$.  
\begin{table}[htb!] 
 \caption{Values for $s(n)$ and $w(n)$}
 \medskip
 \begin{center} 
 \begin{tabular}{|ccc|ccc|ccc|ccc|} \hline
$n$ & $s(n)$ & $w(n)$ & $n$ & $s(n)$ & $w(n)$ & $n$ & $s(n)$ & $w(n)$ & $n$ & $s(n)$ & $w(n)$\\ \hline
1 & 1 & 1 & 17 & 5 & 6 & 33 & 6 & 8 & 49 & 9 & 13 \\
2 & 1 & 1 & 18 & 4 & 4 & 34 & 5 & 6 & 50 & 7 & 9 \\
3 & 2 & 2 & 19 & 7 & 5 & 35 & 9 & 9 & 51 & 12 & 12\\
4 & 1 & 1 & 20 & 3 & 2 & 36 & 4 & 4 & 52 & 5 & 5 \\
5 & 3 & 2 & 21 & 8 & 3 & 37 & 11 & 7 & 53 & 13 & 8 \\
6 & 2 & 2 & 22 & 5 & 3 & 38 & 7 & 5 & 54 & 8 & 7\\
7 & 3 & 4 & 23 & 7 & 7 & 39 & 10 & 9 & 55 & 11 & 15 \\
8 & 1 & 1 & 24 & 2 & 2 & 40 & 3 & 2 & 56 & 3 & 4\\
9 & 4 & 4 & 25 & 7 & 9 & 41 & 11 & 7 & 57 & 10 & 17\\
10 & 3 & 2 & 26 & 5 & 5 & 42 & 8 & 3 & 58 & 7 & 9 \\
11 & 5 & 3 & 27 & 8 & 7 & 43 & 13 & 4 & 59 & 11 & 11\\
12 & 2 & 2 & 28 & 3 & 4 & 44 & 5 & 3 & 60 & 4 & 6 \\
13 & 5 & 5 & 29 & 7 & 9 & 45 & 12 & 8 & 61 & 9 & 13 \\
14 & 3 & 4 & 30 & 4 & 6 & 46 & 7 & 7 & 62 & 5 & 8 \\
15 & 4 & 6 & 31 & 5 & 8 & 47 & 9 & 11 & 63 & 6 & 10 \\
16 & 1 & 1 & 32 & 1 & 1 & 48 & 2 & 2 & 64 & 1 & 1  \\ \hline
 \end{tabular} \label{Tab:Values}
 \end{center}
\end{table}
Analogous to the Stern sequence, we can arrange $w(n)$ into a triangular array, where the $k$-th row is given by $w(n)$ with $2^{k}/3 < n < 2^{k+1}/3$, with the convention of when $k=0$, $n=0$.  The entries in this triangular array are one half the even elements from the diatomic array of the Stern sequence.
\begin{table}[htb!]
\begin{center}
\begin{tabular}{ccccccccccccccccccccc}
 & & & & & & & & & & 0 & & & & & & & & & & \\ 
 & & & & & & & & & & 1 & & & & & & & & & & \\ 
 & & & & & & & & & & 1 & & & & & & & & & & \\ 
 & & & & & & & & & 2 & 1 & 2 & & & & & & & & & \\
 & & & & & & & & 2 & 4 & 1 & 4 & 2 & & & & & & & & \\
 & & & & & 3 & 2 & 5 & 4 & 6 & 1 & 6 & 4 & 5 & 2 & 3 & & & & & \\
3 & 7 & 2 & 9 & 5 & 7 & 4 & 9 & 6 & 8 & 1 & 8 & 6 & 9 & 4 & 7 & 5 & 9 & 2 & 7 & 3 \\
\end{tabular}
\medskip
\caption{Triangular Array for $w(n)$}
\end{center}
\end{table}
What properties does this sequence have?  How often is $w(n)$ even?  What is the largest value in a row?  What type of recurrence relations does this sequence have?  Does it have a nice expression for its generating function?  

Looking at Table \ref{Tab:Values}, we see many similarities to the Stern sequence.  We notice the first five values are the same, and that at powers of 2, the sequence is 1.  The Stern sequence has lots of beautiful recurrence relations, and while $w(n)$ is a little more complicated, it has some similar structure.

We now show the sequence $w(n)$ can be defined independently of $s(n)$. 
\begin{theorem}\label{ind-rec}
Let $w(0)=0$, $w(1)=1$ and $w(3)=2$.  For $n \ge 1$, we have
\begin{align}
w(2n)&=w(n), \notag\\
w(8n \pm 1)&=w(4n \pm 1) +2w(n), \label{8npm1}  \\
w(8n \pm 3)&=w(4n \pm 1) + w(2n \pm 1) -w(n). \label{8npm3}
\end{align}
\end{theorem}

\begin{proof} Using the recurrence properties for $s(n)$ and the definition of $w(n)$, we immediately see
\[
w(2^k n)=\frac{1}{2}s(3\cdot 2^k n)=\frac{1}{2}s(3n)=w(n).
\]
Looking at $w(2n+1)$ we see
\[
w(2n+1)=\frac{1}{2}s(3n+1)+\frac{1}{2}s(3n+2),
\]
which is not very enlightening.  However, if we consider arithmetic progressions modulo 4, we see 
\begin{align}
w(4n+1)&=\frac{1}{2}s(3n)+s(3n+1)=w(n)+s(3n+1), \label{4n+1} \\ 
w(4n+3)&=\frac{1}{2}s(3n+3)+s(3n+2)=w(n+1)+s(3n+2) \label{4n+3},
\end{align}
which is better, but still not completely in terms of $w(n)$.  We can use a more compact notation and write \eqref{4n+1} and \eqref{4n+3} as 
\begin{equation*}
w(4n \pm1)= w(n)+s(3n\pm1).
\end{equation*}
Since we still do not have any recurrence formulas strictly in terms of $w(n)$, we consider arithmetic progressions modulo 8.  Replace $n$ with $2n$ and then $2n+1$ in \eqref{4n+1} and \eqref{4n+3}.  We then use the definition and recurrence relations for $s(n)$, and rearranging the relations in \eqref{4n+1} and \eqref{4n+3} to substitute in for $s(3n+1)$ and $s(3n+2)$, we obtain the recurrence relations in \eqref{8npm1} and \eqref{8npm3}, which completes the proof.
\end{proof}

\begin{remark}
We remark that the Stern sequence is a $2$-regular sequence.  The referee observes that, from the point of view of $2$-regular sequences, the existence of recurrence formulas such as in Theorem \ref{ind-rec} are not surprising.  For more on $2$-regular sequences, see Allouche and Shallit \cite[Ch. 16]{AS1}.
\end{remark}

A natural question to ask is, what is the largest value for $w(n)$ in a row of its triangular array?  Not surprisingly, the largest value of $w(n)$ depends on the three largest values for $s(n)$.  Since $L_1(r)$, $L_2(r)$, and $L_3(r)$ each satisfy a Fibonacci recurrence which is not all even, every third term in the sequence is even.  This simply comes from the fact $odd + even=odd$, $even+odd=odd$, and $odd+odd=even$.  So the maximum of $w(n)$ in a row occurs precisely when one of $L_1(r)$, $L_2(r)$,or $L_3(r)$ is even and then it is divided by two.  Please note Table \ref{Tab:ThreeLargest} gives a comparison of the three largest values for $s(n)$ for easy reference.  The boxed even values in Table \ref{Tab:ThreeLargest} are divided by 2 to yield the $M_k$'s in Table \ref{Tab:Maxvalues}.
\begin{table}[htb!]
 \begin{center}
 \renewcommand{\arraystretch}{1.5}
 \caption{Comparison of the Three Largest Values of $s(n)$ in rows}
\medskip
  \begin{tabular}{cccc}
row $r$ & $L_1(r)$ & $L_2(r)$ & $L_3(r)$ \\ \hline
1 & \fbox{2} & 1 & N/A \\
2 & 3 & \fbox{2} & 1  \\
3 & 5 & \fbox{4} & 3 \\
4 & \fbox{8} & 7 & 5 \\
5 & 13 & \fbox{12} & 11  \\
6 & 21 & 19 & \fbox{18} \\
7 & \fbox{34} & 31 & 30 \\
8 & 55 & \fbox{50} & 49 \\
9 & 89 & 81 & \fbox{80} \\
10 & \fbox{144} & 131 & 129 \\
11 & 233 & \fbox{212} & 209 \\
12 & 377 & 343 & \fbox{338} 
  \end{tabular}
  \label{Tab:ThreeLargest}
 \end{center} 
\end{table} 

Let $M_k$ be the maximum of $w(n)$ in the $k$-th row.  The maximum values for $w(n)$ and where they occur are given in Table \ref{Tab:Maxvalues}.  
\begin{table}[htb!]
 \begin{center}
 \caption{Maxima of $w(n)$ in rows}
\medskip
  \begin{tabular}{ccc|ccc}
row & $n$ & $M_k$ & row & $n$ & $M_k$\\ \hline
2 & 1 & 1 & 13 & 1817, 1849, 2247, 2279 & 169 \\
3 & 2 & 1 & 14 & 3641, 4551 & 305\\
4 & 3, 5 & 2 & 15 & 7281, 7737, 8647, 9103 & 449 \\
5 & 7,9 & 4 & 16 & 14567, 14791, 17977, 18201 & 716 \\
6 & 15, 17 & 6 & 17 & 29127, 36409 & 1292 \\
7 & 25, 29, 35, 39 & 9 & 18 & 58255, 61895, 69177, 72817 & 1902 \\
8 & 57, 71 & 17 & 19 & 116505, 118329, 143815, 145639 & 3033\\
9 & 113, 121, 135, 143 & 25 & 20 & 233017, 291271 & 5473 \\
10 & 231, 281 & 40 & 21 & 466033, 495161, 533415, 582543 & 8057 \\
11 & 455, 569 & 72 & 22 & 932071, 946631, 1150521, 1165081 & 12848 \\
12 & 911, 967, 1081, 1137 & 106 & 23 & 1864135, 2330169 & 23184 
  \end{tabular}
  \label{Tab:Maxvalues}
 \end{center} 
\end{table}
There is a pattern for $M_k$ and where they occur, based on every third row.  

The Fibonacci numbers $F_{r}$ are even when $r$ is a multiple of 3, which implies $L_1(r)=F_{r+2}$ will be even when $r \equiv 1 \pmod 3$. Now, $L_2(r)=F_{r+2}-F_{r-3}$, and this will be even only when $r\equiv 2 \pmod 3$.  If $r \equiv 1 \pmod 3$, then $F_{r+2}$ is even and $F_{r-3}$ is odd, so that their sum is odd.  If $r \equiv 0 \pmod 3$, then $F_{r+2}$ is odd, and $F_{r-3}$ would be even.  If $r\equiv 2 \pmod 3$, then both are odd, so that $F_{r+2}-F_{r-3}$ is even.  We have $L_3(r)=F_{r+2}-3F_{r-5}$ is even when $r \equiv 0 \pmod 3$.  

However, it is important to note the row numbers for $w(n)$ are shifted up one relative to the row numbers for $s(n)$.  To avoid confusion, we denote the row numbers for $s(n)$ with $r$ and the row numbers for $w(n)$ with $k$ (with $k=r+1$).  We then have the following theorem.

\begin{theorem}\label{Max:w}
For $k\ge 5$, the maximum value of $w(n)$ in the $k$-th row is
\begin{align*}
\frac{1}{2}F_{k+1}-\frac{1}{2}F_{k-4}& \quad \text{when $k \equiv 0 \pmod 3$,}\\
\frac{1}{2}F_{k+1}-\frac{3}{2}F_{k-6}& \quad \text{when $k \equiv 1 \pmod 3$,}\\
\frac{1}{2}F_{k+1}& \quad \text{when $k \equiv 2 \pmod 3$.}
\end{align*}
\end{theorem}

\begin{proof}
This is a consequence of Theorems \ref{L1}, \ref{Stern-SecondLarge}, and \ref{Stern-ThirdLarge}.  Note when the three largest values for $s(n)$ begin their Fibonacci recurrence (starting at their initial values):  $L_1(r)$ for all $r$, $L_2(r)$ for $r\ge4$ ($k \ge 5)$, and $L_3(r)$ for $r \ge8$ ($k\ge 9$).  However, in the $r=6$-th row ($k=7$-th), $L_3$ is 18 and the largest even value among $L_1$, $L_2$, and $L_3$.  We also see that $\frac{1}{2}(F_{8}-3F_{1})=\frac{1}{2}(21-3)=\frac{1}{2}\cdot 18=9$, so the last condition is also true for $k=7$.  This completes the proof.
\end{proof}

Using Theorem \ref{Max:w}, the generating function for $M_k$ is
\begin{equation*}
\sum_{n=0}^{\infty} M_k x^k=\frac{x^2+x^3+2x^4+2x^6+x^7+2x^{10}}{1-4x^3-x^6}.
\end{equation*}

The results in this paper are contained in the author's University of Illinois Ph.D. dissertation \cite{jL2}, which has much more information on $w(n)$.  

\begin{thebibliography}{99}

\bibitem{AS1} J.-P. Allouche and J. Shallit, \emph{Automatic Sequences}, Cambridge University Press, 2003.

\bibitem{jL1} J. Lansing, 
Distribution of values of the binomial coefficients and the Stern sequence,
\emph{J. Integer Seq.} \textbf{16} (2013), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL16/Lansing/lansing3.html}{Article 13.3.7}.

\bibitem{jL2} J. Lansing, On the Stern sequence and a related sequence,
Ph.~D.\ Dissertation, University of Illinois, 2014.

\bibitem{dL1} D. H. Lehmer, On Stern's diatomic series, \emph{Amer. Math. Monthly} \textbf{36} (1929), 59--67.

\bibitem{eL1} E. Lucas, Sur les suites de Farey, \emph{Bull. Soc. Math. France} \textbf{6} (1878), 118--119.

\bibitem{sN1} S. Northshield, Stern's diatomic sequence 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, $\ldots$, \emph{Amer. Math. Monthly} \textbf{117} (2010), 581--590.

\bibitem{bR1} B. Reznick, Regularity properties of the Stern
enumeration of the rationals, \emph{J. Integer. Seq.} \textbf{11}
(2008), \href{https://cs.uwaterloo.ca/journals/JIS/VOL11/Reznick/reznick4.html}{Article 08.4.1}.

\bibitem{oeis} N. J. A. Sloane, The Online Encyclopedia of Integer Sequences.  Published electronically at \url{http://oeis.org}.

\bibitem{mS1} M. A. Stern, \"Uber eine zahlentheoretische Funktion,  \emph{J. Reine Angew. Math.} \textbf{55} (1858), 193--220. 


\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B65.  

\noindent \emph{Keywords: } 
Stern sequence, largest value.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A002487} and
\seqnum{A240388}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 11 2014;
revised version received  June 17 2014.
Published in {\it Journal of Integer Sequences},
July 1 2014.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}