<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{verbatim}


\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}
\usepackage{3parttable}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]
{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}
{\underline{#1}}}

\long\def\symbolfootnote[#1]#2{\begingroup%
\def\thefootnote{\fnsymbol{footnote}}\footnote[#1]{#2}\endgroup}



\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{remark}{Remark}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\Large\bf
How the Shift Parameter Affects the Behavior of a\\
\vskip .1in
Family of Meta-Fibonacci Sequences}
\vskip 1cm \large
Mu Cai and Stephen M. Tanny\\
Department of Mathematics\\
University Of Toronto \\
Toronto, Ontario M5S 2E4\\
Canada\\
\href{mailto:tanny@math.toronto.edu}{\tt tanny@math.toronto.edu} \\
\end{center}

\vskip .2in

\begin{abstract}
We explore the effect of different values of the shift parameter $s$
on the behavior of the family of meta-Fibonacci sequences defined by
the $k$-term recursion
$$T_{s,k}(n) := \displaystyle\sum_{i=0}^{k-1} T_{s,k}(n - i - s - T_{s,k}(n - i - 1)), \quad n &gt; s + k, \quad k \geq 2$$
with the $s+k$ initial conditions $T_{s,k}(n) = 1$ for $1 \leq n
\leq s + k$. We show that for any odd $k \geq 3$ and non-negative
integer $s$ the values in the sequence $T_{s,k}(n)$ and $T_{0,k}(n)$
are essentially the same. The only differences in these sequences
are that each power of $k$ occurs precisely $k+s$ times in
$T_{s,k}(n)$ and $k$ times in $T_{0,k}(n)$. For even $k$ the
frequency of $k^r$ in $T_{0,k}(n)$ depends upon $r$. We conjecture
that for $k$ even the effect of the shift parameter $s$ is analogous
to that for $k$ odd, in the sense that the only differences in the
sequences $T_{s,k}(n)$ and $T_{0,k}(n)$ occur in the frequencies of
the powers of $k$; specifically, each power of $k$ appears to occur
precisely $s$ more times in $T_{s,k}(n)$ than it does in
$T_{0,k}(n)$.
\end{abstract}

\vskip .2in


\section{Introduction}\label{sec1}
In this paper, unless otherwise indicated all values are integers.
For $s \geq 0$ and $k \geq 2$ consider the generalized Conolly
meta-Fibonacci (self-referencing) recursion defined in \cite{cct}:
\begin{equation}\label{eq11}
T_{s,k}(n) := \displaystyle\sum_{i=0}^{k-1} T_{s,k}(n - i - s - T_{s,k}(n - i - 1)), \quad n &gt; s + k.
\tag{1.1}
\end{equation}
For given values of the parameters $s$ and $k$ the behavior of the
sequence defined by \eqref{eq11} is highly sensitive to the choice
of the initial conditions. Some initial conditions lead to sequences
with identifiable and regular (though potentially very complex)
patterns, while others generate highly chaotic sequences or even
cause the sequence $T_{s,k}(n)$ eventually to fail to be defined;
that is, for some value of $n$ the argument of one of the terms on
the right hand side of $T_{s,k}(n)$ becomes negative. See \cite{cct}
for additional details.

In the special case $s = 1$, and with the initial conditions
$T_{1,k}(1) := 1$ and $T_{1,k}(i) := i - 1$, $2 \leq i \leq k + 1$,
the resulting sequence behaves in a very simple manner \cite{hts1}.
In particular, it is monotone and its consecutive terms increase by
either 0 or 1, so it hits every positive integer. Following Ruskey
\cite{r} we term such a sequence ``slowly growing''.

In \cite{dr} and \cite{jr} Ruskey and his colleagues derive a
beautiful combinatorial interpretation in terms of k-ary trees for
each of the sequences generated by \eqref{eq11} with $k \geq 2$, $s
\geq 0$ and the initial conditions $T_{s,k}(i) := 1$ for $1 \leq i
\leq s + 1$ and $T_{s,k}(s + i) := i$, $2 \leq i \leq k$. Using
these initial conditions, which are a natural analogue for general
$s$ to the ones in \cite{hts1} for $s = 1$, they show that for every
$k \geq 2$ all these sequences are slowly growing. Even further,
from their combinatorial interpretation it is immediate that for
fixed $k$ the sequences $T_{s,k}(n)$ and $T_{s+1,k}(n)$ are
essentially the same: the only differences in these sequences occur
in the frequencies with which the powers of $k$ occur. In
particular, each power of $k$ occurs precisely one more time in the
sequence $T_{s+1,k}(n)$ than it does in $T_{s,k}(n)$. See Table
\ref{table01} for examples of this for $k = 3, 4, 5$ and $s = 0, 1,
2$.

The shift parameter is known to have this benign type of effect on
other families of slowing growing sequences that are generated by a
meta-Fibonacci recursion similar to the one for $T_{s,k}(n)$. See,
for example, \cite{blt}. The focus of this paper is to show that the
shift parameter $s$ can have such a modest effect even when the
behavior of the sequence is considerably more complicated.


We demonstrate this by showing it to be the case for the family of sequences
generated by \eqref{eq11} but this time with a very different set of initial
conditions, namely, $T_{s,k}(n) = 1$ for $1 \leq n \leq s + k$. These sequences
are introduced in \cite{cct}, but only the special case $s=0$ is analyzed in
detail. They are not monotone and display considerably more complex behavior
than that of the slowly growing sequences discussed in \cite{dr} and \cite{jr}.
See Figures~\ref{fig:series1}, \ref{fig:series2} and \ref{fig:series3}.  In
\cite{cct} the structure of these sequences is completely described for $s = 0$
and $k$ odd. In particular it is shown that the terms of the sequence
$T_{0,k}(n)$ that are equal to $k^{r}$ for any non-negative integer $r$
necessarily appear as a block of $k$ consecutive terms. Table \ref{table11}
illustrates this for $k = 3$ and $s = 0$; note the three consecutive
occurrences of the values 3, 9, 27 and 81.


In this paper we extend the analysis in \cite{cct} by allowing
arbitrary positive integer values for $s$. Specifically we prove
that for any odd $k \geq 3$ and any non-negative integer $s$ the
values in the sequence $T_{s,k}(n)$ and $T_{0,k}(n)$ are essentially
the same. The only differences in these sequences are that each
power of $k$ occurs precisely $k+s$ times in $T_{s,k}(n)$ and $k$
times in $T_{0,k}(n)$. Tables \ref{table11}, \ref{table12} and
\ref{table13} following illustrate this for $k = 3$ and $s = 0, 1$
and 2.

\begin{figure}[h!tpb]
	\begin{center}
	\input{series1}
	\end{center}
\caption{First 160 terms of $T_{0,3}(n)$ with initial values (1,1,1)}
\label{fig:series1}
\end{figure}

\begin{figure}[h!tpb]
	\begin{center}
	\input{series2}
	\end{center}
\caption{First 160 terms of $T_{1,3}(n)$ with initial values (1,1,1,1)}
\label{fig:series2}
\end{figure}

\begin{figure}[h!tpb]
	\begin{center}
	\input{series3}
	\end{center}
\caption{First 160 terms of $T_{2,3}(n)$ with initial values (1,1,1,1,1)}
\label{fig:series3}
\end{figure}

\newpage

\begin{table}[!p]
\fontsize{7}{7}\selectfont
\label{table01}
\begin{center}
\begin{threeparttable}
\caption{First 75 terms of $T_{s,k}(n)$, $s = 0, 1, 2$, $k = 3, 4,
5$, initial conditions $T_{s,k}(i) = 1$, $1 \leq i \leq s + 1$ and
$T_{s,k}(s + i) = i$, $2 \leq i \leq k$.}
\begin{tabular*}{0.80\textwidth}{@{\extracolsep{\fill}}l c c c c c c c c c}
    \hline
    {}&amp;{}&amp;$k = 3$&amp;{}&amp;{}&amp;$k = 4$&amp;{}&amp;{}&amp;$k = 5$&amp;{}\\
    \cline{2-4}\cline{5-7}\cline{8-10}
    n\slash s&amp;0&amp;1&amp;2&amp;0&amp;1&amp;2&amp;0&amp;1&amp;2\\
    \hline
    1&amp;1&amp;1&amp;1&amp;1&amp;1&amp;1&amp;1&amp;1&amp;1\\
    2&amp;2&amp;1&amp;1&amp;2&amp;1&amp;1&amp;2&amp;1&amp;1\\
    3&amp;3&amp;2&amp;1&amp;3&amp;2&amp;1&amp;3&amp;2&amp;1\\
    4&amp;3&amp;3&amp;2&amp;4&amp;3&amp;2&amp;4&amp;3&amp;2\\
    5&amp;4&amp;3&amp;3&amp;4&amp;4&amp;3&amp;5&amp;4&amp;3\\
    6&amp;5&amp;3&amp;3&amp;5&amp;4&amp;4&amp;5&amp;5&amp;4\\
    7&amp;6&amp;4&amp;3&amp;6&amp;4&amp;4&amp;6&amp;5&amp;5\\
    8&amp;6&amp;5&amp;3&amp;7&amp;5&amp;4&amp;7&amp;5&amp;5\\
    9&amp;7&amp;6&amp;4&amp;8&amp;6&amp;4&amp;8&amp;6&amp;5\\
    10&amp;8&amp;6&amp;5&amp;8&amp;7&amp;5&amp;9&amp;7&amp;5\\
    11&amp;9&amp;7&amp;6&amp;9&amp;8&amp;6&amp;10&amp;8&amp;6\\
    12&amp;9&amp;8&amp;6&amp;10&amp;8&amp;7&amp;10&amp;9&amp;7\\
    13&amp;9&amp;9&amp;7&amp;11&amp;9&amp;8&amp;11&amp;10&amp;8\\
    14&amp;10&amp;9&amp;8&amp;12&amp;10&amp;8&amp;12&amp;10&amp;9\\
    15&amp;11&amp;9&amp;9&amp;12&amp;11&amp;9&amp;13&amp;11&amp;10\\
    16&amp;12&amp;9&amp;9&amp;13&amp;12&amp;10&amp;14&amp;12&amp;10\\
    17&amp;12&amp;10&amp;9&amp;14&amp;12&amp;11&amp;15&amp;13&amp;11\\
    18&amp;13&amp;11&amp;9&amp;15&amp;13&amp;12&amp;15&amp;14&amp;12\\
    19&amp;14&amp;12&amp;9&amp;16&amp;14&amp;12&amp;16&amp;15&amp;13\\
    20&amp;15&amp;12&amp;10&amp;16&amp;15&amp;13&amp;17&amp;15&amp;14\\
    21&amp;15&amp;13&amp;11&amp;16&amp;16&amp;14&amp;18&amp;16&amp;15\\
    22&amp;16&amp;14&amp;12&amp;17&amp;16&amp;15&amp;19&amp;17&amp;15\\
    23&amp;17&amp;15&amp;12&amp;18&amp;16&amp;16&amp;20&amp;18&amp;16\\
    24&amp;18&amp;15&amp;13&amp;19&amp;16&amp;16&amp;20&amp;19&amp;17\\
    25&amp;18&amp;16&amp;14&amp;20&amp;17&amp;16&amp;21&amp;20&amp;18\\
    26&amp;18&amp;17&amp;15&amp;20&amp;18&amp;16&amp;22&amp;20&amp;19\\
    27&amp;19&amp;18&amp;15&amp;21&amp;19&amp;16&amp;23&amp;21&amp;20\\
    28&amp;20&amp;18&amp;16&amp;22&amp;20&amp;17&amp;24&amp;22&amp;20\\
    29&amp;21&amp;18&amp;17&amp;23&amp;20&amp;18&amp;25&amp;23&amp;21\\
    30&amp;21&amp;19&amp;18&amp;24&amp;21&amp;19&amp;25&amp;24&amp;22\\
    31&amp;22&amp;20&amp;18&amp;24&amp;22&amp;20&amp;25&amp;25&amp;23\\
    32&amp;23&amp;21&amp;18&amp;25&amp;23&amp;20&amp;26&amp;25&amp;24\\
    33&amp;24&amp;21&amp;19&amp;26&amp;24&amp;21&amp;27&amp;25&amp;25\\
    34&amp;24&amp;22&amp;20&amp;27&amp;24&amp;22&amp;28&amp;25&amp;25\\
    35&amp;25&amp;23&amp;21&amp;28&amp;25&amp;23&amp;29&amp;26&amp;25\\
    36&amp;26&amp;24&amp;21&amp;28&amp;26&amp;24&amp;30&amp;27&amp;25\\
    37&amp;27&amp;24&amp;22&amp;29&amp;27&amp;24&amp;30&amp;28&amp;25\\
    38&amp;27&amp;25&amp;23&amp;30&amp;28&amp;25&amp;31&amp;29&amp;26\\
    39&amp;27&amp;26&amp;24&amp;31&amp;28&amp;26&amp;32&amp;30&amp;27\\
    40&amp;27&amp;27&amp;24&amp;32&amp;29&amp;27&amp;33&amp;30&amp;28\\
    41&amp;28&amp;27&amp;25&amp;32&amp;30&amp;28&amp;34&amp;31&amp;29\\
    42&amp;29&amp;27&amp;26&amp;32&amp;31&amp;28&amp;35&amp;32&amp;30\\
    43&amp;30&amp;27&amp;27&amp;33&amp;32&amp;29&amp;35&amp;33&amp;30\\
    44&amp;30&amp;27&amp;27&amp;34&amp;32&amp;30&amp;36&amp;34&amp;31\\
    45&amp;31&amp;28&amp;27&amp;35&amp;32&amp;31&amp;37&amp;35&amp;32\\
    46&amp;32&amp;29&amp;27&amp;36&amp;33&amp;32&amp;38&amp;35&amp;33\\
    47&amp;33&amp;30&amp;27&amp;36&amp;34&amp;32&amp;39&amp;36&amp;34\\
    48&amp;33&amp;30&amp;27&amp;37&amp;35&amp;32&amp;40&amp;37&amp;35\\
    49&amp;34&amp;31&amp;28&amp;38&amp;36&amp;33&amp;40&amp;38&amp;35\\
    50&amp;35&amp;32&amp;29&amp;39&amp;36&amp;34&amp;41&amp;39&amp;36\\
    51&amp;36&amp;33&amp;30&amp;40&amp;37&amp;35&amp;42&amp;40&amp;37\\
    52&amp;36&amp;33&amp;30&amp;40&amp;38&amp;36&amp;43&amp;40&amp;38\\
    53&amp;36&amp;34&amp;31&amp;41&amp;39&amp;36&amp;44&amp;41&amp;39\\
    54&amp;37&amp;35&amp;32&amp;42&amp;40&amp;37&amp;45&amp;42&amp;40\\
    55&amp;38&amp;36&amp;33&amp;43&amp;40&amp;38&amp;45&amp;43&amp;40\\
    56&amp;39&amp;36&amp;33&amp;44&amp;41&amp;39&amp;46&amp;44&amp;41\\
    57&amp;39&amp;36&amp;34&amp;44&amp;42&amp;40&amp;47&amp;45&amp;42\\
    58&amp;40&amp;37&amp;35&amp;45&amp;43&amp;40&amp;48&amp;45&amp;43\\
    59&amp;41&amp;38&amp;36&amp;46&amp;44&amp;41&amp;49&amp;46&amp;44\\
    60&amp;42&amp;39&amp;36&amp;47&amp;44&amp;42&amp;50&amp;47&amp;45\\
    61&amp;42&amp;39&amp;36&amp;48&amp;45&amp;43&amp;50&amp;48&amp;45\\
    62&amp;43&amp;40&amp;37&amp;48&amp;46&amp;44&amp;50&amp;49&amp;46\\
    63&amp;44&amp;41&amp;38&amp;48&amp;47&amp;44&amp;51&amp;50&amp;47\\
    64&amp;45&amp;42&amp;39&amp;49&amp;48&amp;45&amp;52&amp;50&amp;48\\
    65&amp;45&amp;42&amp;39&amp;50&amp;48&amp;46&amp;53&amp;50&amp;49\\
    66&amp;45&amp;43&amp;40&amp;51&amp;48&amp;47&amp;54&amp;51&amp;50\\
    67&amp;46&amp;44&amp;41&amp;52&amp;49&amp;48&amp;55&amp;52&amp;50\\
    68&amp;47&amp;45&amp;42&amp;52&amp;50&amp;48&amp;55&amp;53&amp;50\\
    69&amp;48&amp;45&amp;42&amp;53&amp;51&amp;48&amp;56&amp;54&amp;51\\
    70&amp;48&amp;45&amp;43&amp;54&amp;52&amp;49&amp;57&amp;55&amp;52\\
    71&amp;49&amp;46&amp;44&amp;55&amp;52&amp;50&amp;58&amp;55&amp;53\\
    72&amp;50&amp;47&amp;45&amp;56&amp;53&amp;51&amp;59&amp;56&amp;54\\
    73&amp;51&amp;48&amp;45&amp;56&amp;54&amp;52&amp;60&amp;57&amp;55\\
    74&amp;51&amp;48&amp;45&amp;57&amp;55&amp;52&amp;60&amp;58&amp;55\\
    75&amp;52&amp;49&amp;46&amp;58&amp;56&amp;53&amp;61&amp;59&amp;56\\
\hline
\end{tabular*}
\end{threeparttable}
\end{center}
\end{table}

The proof of this simply stated and intuitively intriguing result is
highly technical and makes extensive use of the approaches and
results in \cite{cct}. It relies upon a series of nested induction
arguments that are essentially the same for any odd $k$. As such, we
proceed slowly and in stages, initially providing the details for
the special case $k = 3$, where they are easier to follow. In
Section 2 we establish the base case $s = 1$, namely, the result
holds for the pair of sequences $T_{0,3}(n)$ and $T_{1,3}(n)$. We
complete the induction for the case $k = 3$ and general $s$ in
Section 3. In Section 4 we sketch the induction argument for general
odd $k$.

In Section 5 we conclude with some brief observations about the
situation for $k$ even. Based upon substantial empirical evidence it
appears that our result also holds for this case. However, unlike
the situation for $k$ odd, there is no starting point for an
induction argument similar to the one we use below since to date
nothing has been proved about the sequences $T_{0,k}(n)$ for $k$
even (but see \cite{cct} for some conjectures).



\begin{table}[!p]
\fontsize{7}{7}\selectfont
\caption{First 160 terms of $T_{0,3}(n)$ \textsl{with initial values} $(1, 1, 1)$}\label{table11}
\center{
\begin{tabular*}{0.80\textwidth}{@{\extracolsep{\fill}}l c c l c c l c c l c c}
    \hline
    {}&amp;$n$&amp;{}&amp;{}&amp;$n$&amp;{}&amp;{}&amp;$n$&amp;{}&amp;{}&amp;$n$\\
    \cline{2-3}\cline{5-6}\cline{8-9}\cline{11-12}
    {}&amp;1&amp;2&amp;{}&amp;1&amp;2&amp;{}&amp;1&amp;2&amp;{}&amp;1&amp;2\\
    \hline
$T(n+0)$&amp;1&amp;1&amp;$T(n+40)$&amp;27&amp;27&amp;$T(n+80)$&amp;59&amp;49&amp;$T(n+120)$&amp;81&amp;81\\
$T(n+2)$&amp;1&amp;3&amp;$T(n+42)$&amp;29&amp;29&amp;$T(n+82)$&amp;59&amp;51&amp;$T(n+122)$&amp;81&amp;83\\
$T(n+4)$&amp;3&amp;3&amp;$T(n+44)$&amp;31&amp;29&amp;$T(n+84)$&amp;61&amp;53&amp;$T(n+124)$&amp;83&amp;85\\
$T(n+6)$&amp;5&amp;5&amp;$T(n+46)$&amp;33&amp;31&amp;$T(n+86)$&amp;61&amp;55&amp;$T(n+126)$&amp;83&amp;87\\
$T(n+8)$&amp;7&amp;5&amp;$T(n+48)$&amp;35&amp;31&amp;$T(n+88)$&amp;63&amp;57&amp;$T(n+128)$&amp;85&amp;89\\
$T(n+10)$&amp;7&amp;7&amp;$T(n+50)$&amp;37&amp;33&amp;$T(n+90)$&amp;63&amp;57&amp;$T(n+130)$&amp;85&amp;91\\
$T(n+12)$&amp;9&amp;9&amp;$T(n+52)$&amp;39&amp;33&amp;$T(n+92)$&amp;65&amp;59&amp;$T(n+132)$&amp;87&amp;93\\
$T(n+14)$&amp;9&amp;11&amp;$T(n+54)$&amp;41&amp;35&amp;$T(n+94)$&amp;67&amp;59&amp;$T(n+134)$&amp;87&amp;95\\
$T(n+16)$&amp;11&amp;13&amp;$T(n+56)$&amp;43&amp;35&amp;$T(n+96)$&amp;67&amp;61&amp;$T(n+136)$&amp;89&amp;97\\
$T(n+18)$&amp;11&amp;15&amp;$T(n+58)$&amp;43&amp;37&amp;$T(n+98)$&amp;69&amp;63&amp;$T(n+138)$&amp;89&amp;99\\
$T(n+20)$&amp;13&amp;17&amp;$T(n+60)$&amp;45&amp;39&amp;$T(n+100)$&amp;69&amp;63&amp;$T(n+140)$&amp;91&amp;101\\
$T(n+22)$&amp;13&amp;17&amp;$T(n+62)$&amp;45&amp;39&amp;$T(n+102)$&amp;71&amp;65&amp;$T(n+142)$&amp;91&amp;103\\
$T(n+24)$&amp;15&amp;19&amp;$T(n+64)$&amp;47&amp;41&amp;$T(n+104)$&amp;73&amp;65&amp;$T(n+144)$&amp;93&amp;105\\
$T(n+26)$&amp;17&amp;19&amp;$T(n+66)$&amp;49&amp;41&amp;$T(n+106)$&amp;73&amp;67&amp;$T(n+146)$&amp;93&amp;107\\
$T(n+28)$&amp;17&amp;21&amp;$T(n+68)$&amp;49&amp;43&amp;$T(n+108)$&amp;75&amp;69&amp;$T(n+148)$&amp;95&amp;109\\
$T(n+30)$&amp;19&amp;23&amp;$T(n+70)$&amp;51&amp;45&amp;$T(n+110)$&amp;75&amp;71&amp;$T(n+150)$&amp;95&amp;111\\
$T(n+32)$&amp;19&amp;23&amp;$T(n+72)$&amp;51&amp;45&amp;$T(n+112)$&amp;77&amp;73&amp;$T(n+152)$&amp;97&amp;113\\
$T(n+34)$&amp;21&amp;25&amp;$T(n+74)$&amp;53&amp;47&amp;$T(n+114)$&amp;77&amp;75&amp;$T(n+154)$&amp;97&amp;113\\
$T(n+36)$&amp;23&amp;25&amp;$T(n+76)$&amp;55&amp;47&amp;$T(n+116)$&amp;79&amp;77&amp;$T(n+156)$&amp;99&amp;115\\
$T(n+38)$&amp;25&amp;27&amp;$T(n+78)$&amp;55&amp;49&amp;$T(n+118)$&amp;79&amp;79&amp;$T(n+158)$&amp;101&amp;115\\
\hline
\end{tabular*}
}
\end{table}

\begin{table}[!p]
\fontsize{7}{7}\selectfont
\caption{First 160 terms of $T_{1,3}(n)$ \textsl{with initial values} $(1, 1, 1, 1)$}\label{table12}
\center{
\begin{tabular*}{0.80\textwidth}{@{\extracolsep{\fill}}l c c l c c l c c l c c}
    \hline
    {}&amp;$n$&amp;{}&amp;{}&amp;$n$&amp;{}&amp;{}&amp;$n$&amp;{}&amp;{}&amp;$n$\\
    \cline{2-3}\cline{5-6}\cline{8-9}\cline{11-12}
    {}&amp;1&amp;2&amp;{}&amp;1&amp;2&amp;{}&amp;1&amp;2&amp;{}&amp;1&amp;2\\
    \hline
$T(n+0)$&amp;1&amp;1&amp;$T(n+40)$&amp;25&amp;25&amp;$T(n+80)$&amp;55&amp;47&amp;$T(n+120)$&amp;79&amp;77\\
$T(n+2)$&amp;1&amp;1&amp;$T(n+42)$&amp;27&amp;27&amp;$T(n+82)$&amp;57&amp;49&amp;$T(n+122)$&amp;79&amp;79\\
$T(n+4)$&amp;3&amp;3&amp;$T(n+44)$&amp;27&amp;27&amp;$T(n+84)$&amp;59&amp;49&amp;$T(n+124)$&amp;81&amp;81\\
$T(n+6)$&amp;3&amp;3&amp;$T(n+46)$&amp;29&amp;29&amp;$T(n+86)$&amp;59&amp;51&amp;$T(n+126)$&amp;81&amp;81\\
$T(n+8)$&amp;5&amp;5&amp;$T(n+48)$&amp;31&amp;29&amp;$T(n+88)$&amp;61&amp;53&amp;$T(n+128)$&amp;83&amp;83\\
$T(n+10)$&amp;7&amp;5&amp;$T(n+50)$&amp;33&amp;31&amp;$T(n+90)$&amp;61&amp;55&amp;$T(n+130)$&amp;85&amp;83\\
$T(n+12)$&amp;7&amp;7&amp;$T(n+52)$&amp;35&amp;31&amp;$T(n+92)$&amp;63&amp;57&amp;$T(n+132)$&amp;87&amp;85\\
$T(n+14)$&amp;9&amp;9&amp;$T(n+54)$&amp;37&amp;33&amp;$T(n+94)$&amp;63&amp;57&amp;$T(n+134)$&amp;89&amp;85\\
$T(n+16)$&amp;9&amp;9&amp;$T(n+56)$&amp;39&amp;33&amp;$T(n+96)$&amp;65&amp;59&amp;$T(n+136)$&amp;91&amp;87\\
$T(n+18)$&amp;11&amp;11&amp;$T(n+58)$&amp;41&amp;35&amp;$T(n+98)$&amp;67&amp;59&amp;$T(n+138)$&amp;93&amp;87\\
$T(n+20)$&amp;13&amp;11&amp;$T(n+60)$&amp;43&amp;35&amp;$T(n+100)$&amp;67&amp;61&amp;$T(n+140)$&amp;95&amp;89\\
$T(n+22)$&amp;15&amp;13&amp;$T(n+62)$&amp;43&amp;37&amp;$T(n+102)$&amp;69&amp;63&amp;$T(n+142)$&amp;97&amp;89\\
$T(n+24)$&amp;17&amp;13&amp;$T(n+64)$&amp;45&amp;39&amp;$T(n+104)$&amp;69&amp;63&amp;$T(n+144)$&amp;99&amp;91\\
$T(n+26)$&amp;17&amp;15&amp;$T(n+66)$&amp;45&amp;39&amp;$T(n+106)$&amp;71&amp;65&amp;$T(n+146)$&amp;101&amp;91\\
$T(n+28)$&amp;19&amp;17&amp;$T(n+68)$&amp;47&amp;41&amp;$T(n+108)$&amp;73&amp;65&amp;$T(n+148)$&amp;103&amp;93\\
$T(n+30)$&amp;19&amp;17&amp;$T(n+70)$&amp;49&amp;41&amp;$T(n+110)$&amp;73&amp;67&amp;$T(n+150)$&amp;105&amp;93\\
$T(n+32)$&amp;21&amp;19&amp;$T(n+72)$&amp;49&amp;43&amp;$T(n+112)$&amp;75&amp;69&amp;$T(n+152)$&amp;107&amp;95\\
$T(n+34)$&amp;23&amp;19&amp;$T(n+74)$&amp;51&amp;45&amp;$T(n+114)$&amp;75&amp;71&amp;$T(n+154)$&amp;109&amp;95\\
$T(n+36)$&amp;23&amp;21&amp;$T(n+76)$&amp;51&amp;45&amp;$T(n+116)$&amp;77&amp;73&amp;$T(n+156)$&amp;111&amp;97\\
$T(n+38)$&amp;25&amp;23&amp;$T(n+78)$&amp;53&amp;47&amp;$T(n+118)$&amp;77&amp;75&amp;$T(n+158)$&amp;113&amp;97\\
\hline
\end{tabular*}
}
\end{table}

\begin{table}[!p]
\fontsize{7}{7}\selectfont
\caption{First 160 terms of $T_{2,3}(n)$ \textsl{with initial values} $(1, 1, 1, 1, 1)$}\label{table13}
\center{
\begin{tabular*}{0.80\textwidth}{@{\extracolsep{\fill}}l c c l c c l c c l c c}
    \hline
    {}&amp;$n$&amp;{}&amp;{}&amp;$n$&amp;{}&amp;{}&amp;$n$&amp;{}&amp;{}&amp;$n$&amp;{}\\
    \cline{2-3}\cline{5-6}\cline{8-9}\cline{11-12}
    {}&amp;1&amp;2&amp;{}&amp;1&amp;2&amp;{}&amp;1&amp;2&amp;{}&amp;1&amp;2\\
    \hline
$T(n+0)$&amp;1&amp;1&amp;$T(n+40)$&amp;21&amp;25&amp;$T(n+80)$&amp;51&amp;45&amp;$T(n+120)$&amp;77&amp;73\\
$T(n+2)$&amp;1&amp;1&amp;$T(n+42)$&amp;23&amp;25&amp;$T(n+82)$&amp;53&amp;47&amp;$T(n+122)$&amp;77&amp;75\\
$T(n+4)$&amp;1&amp;3&amp;$T(n+44)$&amp;25&amp;27&amp;$T(n+84)$&amp;55&amp;47&amp;$T(n+124)$&amp;79&amp;77\\
$T(n+6)$&amp;3&amp;3&amp;$T(n+46)$&amp;27&amp;27&amp;$T(n+86)$&amp;57&amp;49&amp;$T(n+126)$&amp;79&amp;79\\
$T(n+8)$&amp;3&amp;3&amp;$T(n+48)$&amp;27&amp;27&amp;$T(n+88)$&amp;59&amp;49&amp;$T(n+128)$&amp;81&amp;81\\
$T(n+10)$&amp;5&amp;5&amp;$T(n+50)$&amp;29&amp;29&amp;$T(n+90)$&amp;59&amp;51&amp;$T(n+130)$&amp;81&amp;81\\
$T(n+12)$&amp;7&amp;5&amp;$T(n+52)$&amp;31&amp;29&amp;$T(n+92)$&amp;61&amp;53&amp;$T(n+132)$&amp;81&amp;83\\
$T(n+14)$&amp;7&amp;7&amp;$T(n+54)$&amp;33&amp;31&amp;$T(n+94)$&amp;61&amp;55&amp;$T(n+134)$&amp;83&amp;85\\
$T(n+16)$&amp;9&amp;9&amp;$T(n+56)$&amp;35&amp;31&amp;$T(n+96)$&amp;63&amp;57&amp;$T(n+136)$&amp;83&amp;87\\
$T(n+18)$&amp;9&amp;9&amp;$T(n+58)$&amp;37&amp;33&amp;$T(n+98)$&amp;63&amp;57&amp;$T(n+138)$&amp;85&amp;89\\
$T(n+20)$&amp;9&amp;11&amp;$T(n+60)$&amp;39&amp;33&amp;$T(n+100)$&amp;65&amp;59&amp;$T(n+140)$&amp;85&amp;91\\
$T(n+22)$&amp;11&amp;13&amp;$T(n+62)$&amp;41&amp;35&amp;$T(n+102)$&amp;67&amp;59&amp;$T(n+142)$&amp;87&amp;93\\
$T(n+24)$&amp;11&amp;15&amp;$T(n+64)$&amp;43&amp;35&amp;$T(n+104)$&amp;67&amp;61&amp;$T(n+144)$&amp;87&amp;95\\
$T(n+26)$&amp;13&amp;17&amp;$T(n+66)$&amp;43&amp;37&amp;$T(n+106)$&amp;69&amp;63&amp;$T(n+146)$&amp;89&amp;97\\
$T(n+28)$&amp;13&amp;17&amp;$T(n+68)$&amp;45&amp;39&amp;$T(n+108)$&amp;69&amp;63&amp;$T(n+148)$&amp;89&amp;99\\
$T(n+30)$&amp;15&amp;19&amp;$T(n+70)$&amp;45&amp;39&amp;$T(n+110)$&amp;71&amp;65&amp;$T(n+150)$&amp;91&amp;101\\
$T(n+32)$&amp;17&amp;19&amp;$T(n+72)$&amp;47&amp;41&amp;$T(n+112)$&amp;73&amp;65&amp;$T(n+152)$&amp;91&amp;103\\
$T(n+34)$&amp;17&amp;21&amp;$T(n+74)$&amp;49&amp;41&amp;$T(n+114)$&amp;73&amp;67&amp;$T(n+154)$&amp;93&amp;105\\
$T(n+36)$&amp;19&amp;23&amp;$T(n+76)$&amp;49&amp;43&amp;$T(n+116)$&amp;75&amp;69&amp;$T(n+156)$&amp;93&amp;107\\
$T(n+38)$&amp;19&amp;23&amp;$T(n+78)$&amp;51&amp;45&amp;$T(n+118)$&amp;75&amp;71&amp;$T(n+158)$&amp;95&amp;109\\
\hline
\end{tabular*}
}
\end{table}

\newpage
\section{The behavior of $T_{1,3}(n)$}\label{sec2}
Consider the recursion \eqref{eq11} with $k = 3$ and $s = 0$ with
initial conditions $T(1) = T(2) = T(3) = 1$:
\begin{equation}\label{eq21}
T(n) = T(n - T(n - 1)) + T(n - 1 - T(n - 2)) + T(n - 2 - T(n - 3))
\tag{2.1}
\end{equation}

For convenience throughout this paper we omit either or both of the
subscripts $s$ and $k$ where this causes no confusion. Following
\cite{cct} we define $U(n) = T(n - T(n - 1))$, so $T(n) = U(n) + U(n
- 1) + U(n - 2)$. We determine bounds on $U(n)$. 

As in Definition 3.5 in \cite{cct}, for any $g&gt; 0$ call the interval (of the
domain of the sequence) $[m_{g}, m_{g+1} - 1]$ the $g^{th}$ generation of the
sequence $T(n)$, written as $gen(g)$, where $m_{g} = \frac{1}{2}(3^{g+1} + 5)$.
See Figure~\ref{fig:structure}. Notice that the value of $T(n)$ at the
endpoints of each generation are powers of 3.

\begin{figure}[h!tpb]
	\begin{center}
	\input{series1_structure}
	\end{center}
\caption{Initial portion of generation structure of $T_{0,3}(n)$}
\label{fig:structure}
\end{figure}

\begin{lemma}
\label{lemma21} Let $2 \leq g$, and suppose that $n$ is in the $(g -
1)^{th}$ generation, i.e. $n \in [m_{g-1}, m_{g} - 1] =
[(\frac{1}{2})3^{g} + \frac{5}{2}, (\frac{1}{2})3^{g+1} +
\frac{3}{2}]$. Then $3^{g-2} \leq U(n), U(n - 1), U(n - 2) \leq
3^{g-1}$. Moreover $U(m_{g} - 1) = U(m_{g} - 2) = U(m_{g} - 3) =
3^{g-1}$.
\end{lemma}

\begin{proof}
From Theorem 3.15 in \cite{cct} $T(m_{g+1} - 1) =
T(m_{g+1} - 2) = T(m_{g+1} - 3) = 3^{g+1}$. But by definition we
have that $T(m_{g+1} - 1) = U(m_{g+1} - 1) + U(m_{g+1} - 2) +
U(m_{g+1} - 3) = T(m_{g+1} - 2) = U(m_{g+1} - 2) + U(m_{g+1} - 3) +
U(m_{g+1} - 4)$. Hence it follows that $U(m_{g+1} - 1) = U(m_{g+1} -
4)$. Similarly we derive from $T(m_{g+1} - 2) = T(m_{g+1} - 3)$ that
$U(m_{g+1} - 2) = U(m_{g+1} - 5)$. By Proposition 2.2 in \cite{cct}
$\Delta_{2}U(t) = U(t + 2) - U(t) \in \{0, 2\}$ for any positive
integer $t$. Thus $U(m_{g+1} - 1) \geq U(m_{g+1} - 3) \geq U(m_{g+1}
- 5) = U(m_{g+1} - 2) \geq U(m_{g+1} - 4) = U(m_{g+1} - 1)$. So
$U(m_{g+1} - 1) = U(m_{g+1} - 2) = U(m_{g+1} - 3) =
\frac{1}{3}T(m_{g+1} - 1) = 3^{g}$. This completes the proof of the
second part of the statement of the lemma.

It remains to prove that for $n \in [m_{g}, m_{g+1} - 1]$, $3^{g-1}
\leq U(n), U(n - 1), U(n - 2) \leq 3^{g}$. By the above argument
we have $U(m_{g} - 1) = U(m_{g} - 2) = U(m_{g} - 3) =
(\frac{1}{3})T(m_{g} - 1) = 3^{g-1}$. Since $\Delta_{2}U(t) = U(t +
2) - U(t) \in \{0, 2\}$ for any positive integer $t$ it follows that
each of the subsequences of $U(n)$ defined on the sets $\{n \in
gen(g):n \equiv m_{g}$ (mod 2)\} and $\{n \in gen(g):n \equiv
m_{g+1}$ (mod 2)\} is monotone non-decreasing (since $\Delta_{2}U(n)
\in \{0, 2\}$ for all $n$), and that each of these subsequences for
generation $g$ begins with at least $3^{g-1}$ and ends no higher
than $3^{g}$. This concludes the proof.
\end{proof}

Now consider the recursion \eqref{eq11} with $k = 3$ and $s = 1$
(``shift parameter 1''), namely,
\begin{equation}\label{eq22}
T_{1}(n) = T_{1}(n - 1 - T_{1}(n - 1)) + T_{1}(n - 2 - T_{1}(n - 2))
+ T_{1}(n - 3 - T_{1}(n - 3)). \tag{2.2}
\end{equation}
Let $U_{1}(n) = T_{1}(n - 1 - T_{1}(n - 1))$, so $T_{1}(n) =
U_{1}(n) + U_{1}(n - 1) + U_{1}(n - 2)$. (Note that our notation
suppresses the parameter $k = 3$.) Four initial conditions are
required, and these are $T_{1}(1) = T_{1}(2) = T_{1}(3) = T_{1}(4) =
1$. For $2 \leq g$, we define the $(g - 1)^{th}$ generation of the
``shifted'' sequence $T_{1}(n)$ as the interval $n \in [m_{g-1} + g,
m_{g} + g]$. For brevity we sometimes refer to this interval as the
``shifted'' $(g - 1)^{th}$ generation. The main result is the
following:

\begin{theorem}
\label{thm22}
Let $2 \leq g$. For $n \in [m_{g-1} + g, m_{g} + g]$, the shifted $(g - 1)^{th}$ generation, the following two statements about the values of $T_{1}(n)$ and $U_{1}(n)$ hold:

(\texttt{\textbf{1}}) For $n \in [m_{g-1} + g, m_{g} + g - 4]$,
$3^{g-1} &lt; T_{1}(n) &lt; 3^{g}$ and $3^{g-2} \leq U_{1}(n), U_{1}(n -
1), U_{1}(n - 2) \leq 3^{g-1}$. For $n \in [m_{g} + g - 3, m_{g} +
g]$, $T_{1}(n) = 3^{g}$ and $U_{1}(n)=U_{1}(n - 1)=U_{1}(n - 2) =
3^{g-1}$.

(\texttt{\textbf{2}}) For $n \in [m_{g-1} + g, m_{g} + g - 1]$, $T_{1}(n) = T_{0}(n - g)$. For $n \in [m_{g} + g - 2, m_{g} + g]$, $T_{1}(n) = T_{0}(n - g - 1)$.
\end{theorem}

Note that the second part of (\textbf{2}) follows from (\textbf{1}); we include it for convenience as we'll use it directly below. From (\textbf{1}) it follows that the sequence $T_1(n)$ hits powers
of 3 exactly 4 times at the end of each generation (recall that the
sequence $T_{0}(n)$ hits powers of 3 exactly 3 times at the end of
each generation). From (\textbf{2}) we have that otherwise the
sequences are the same, since for $r \in [m_{g-1}, m_{g} - 1],
T_{0}(r) = T_{1}(r + g)$ (since if $r \in [m_{g-1}, m_{g} - 1]$,
then $r + g \in [m_{g-1} + g, m_{g} + g - 1]$. Thus we have that the sequences are identical except for
the frequency of the occurrences of the powers of 3. Compare Tables
\ref{table11} and \ref{table12} for an illustration of this.

\begin{proof}
Here we require a nested induction, on both $g$ and $n$. We begin
with the induction on $g$, the ``outer induction''. For $g = 2$ we
check each of the statements numerically for the shifted first
generation. We begin with (\textbf{1}). Here $n \in [m_{g-1} + g,
m_{g} + g - 4] = [(\frac{1}{2})3^{g} + \frac{5}{2} + g,
(\frac{1}{2})3^{g+1} + \frac{5}{2} + g - 4] = [9, 14]$. For $n$ in
this interval it follows from the definition of $U_{1}(n)$ that each
of $U_{1}(n), U_{1}(n - 1), U_{1}(n - 2)$ are contained in the set
$\{T_{1}(3), T_{1}(4), \ldots , T_{1}(8)\} = \{1, 3\}$ so the first part
of (\textbf{1}) holds. Further, $U_{1}(16) = U_{1}(15) = U_{1}(14) =
T_{1}(8) = 3$, so this completes the proof of (\textbf{1}). In a
similar way we confirm that (\textbf{2}) holds. Thus the base case
is done.

Suppose both (\textbf{1}) and (\textbf{2}) hold for the $1^{st},
2^{nd}, \ldots, (g - 2)^{th}$ shifted generations with $g \geq 3$. We
complete the induction on $g$ by proving that they both hold for the
$(g - 1)^{th}$ shifted generation, which is the interval $n \in
[m_{g-1} + g, m_{g} + g]$. Once again we proceed by induction, this
time on $n$; this is what we call the ``inner induction''.

We begin by confirming that (\textbf{1}) and (\textbf{2}) hold for
the initial value of this interval, namely $n = m_{g-1} + g$.
Specifically, we need to confirm that for this value of $n$,
$T_{1}(n) \in (3^{g-1}$, $3^{g}), U_{1}(n), U_{1}(n - 1), U_{1}(n -
2) \in [3^{g-2}, 3^{g-1}]$, and further $T_{1}(n) = T_{0}(n - g)$.

Since $n = m_{g-1} + g$ is the first term of the $(g - 1)^{th}$
shifted generation, $n - 1 = m_{g-1} + g - 1$ is the last term of
the $(g - 2)^{th}$ shifted generation. But by the induction
assumption on $g$,  (\textbf{1}) holds for the $(g - 2)^{th}$
shifted generation. Thus, $T_{1}(n - 1) = 3^{g-1}$, while $U_{1}(n -
1) = U_{1}(n - 2) = U_{1}(n - 3) = 3^{g-2}$. Also, $U_{1}(n) =
T_{1}(n - 1 - T_{1}(n - 1)) = T_{1}(m_{g-1} + g - 1 - 3^{g-1}) =
T_{1}(m_{g-2} + g - 1)$. Note that $m_{g-2} + g - 1$ is the first
member of the $(g - 2)^{th}$ shifted generation (so it's not among
the last four terms of the generation). It follows by the induction
assumption on $g$ that $U_{1}(n) = T_{1}(m_{g-2} + g - 1) \in
(3^{g-2}, 3^{g-1})$. So $T_{1}(n) = U_{1}(n) + U_{1}(n - 1) +
U_{1}(n - 2) \in (3^{g-1}, 3^{g})$ and $U_{1}(n), U_{1}(n - 1),
U_{1}(n - 2) \in [3^{g-2}, 3^{g-1}]$. This confirms (\textbf{1}).

We prove (\textbf{2}) similarly. By the above argument $U_{1}(n) =
T_{1}(m_{g-2} + g - 1)$ so by the induction assumption on $g$ for
(\textbf{2}) for the $(g - 2)^{th}$ shifted generation we have
$U_1(n) = T_1(m_{g-2} + g - 1) = T_{0}(m_{g-2})$. Since $n = m_{g-1}
+ g$,  we have $T_{0}(n - g - 1) = T_{0}(m_{g-1} - 1) = 3^{g-1}$ by
Theorem 4.3 in \cite{cct}, so $U_{0}(n - g) = T_{0}(n - g - T_{0}(n
- g - 1)) = T_{0}(m_{g-1} - 3^{g-1}) = T_{0}(m_{g-2})$. Thus we get
$U_{1}(n) = T_{0}(m_{g-2}) = U_{0}(n - g)$. By Theorem 4.3 in
\cite{cct} again, $T_{0}(n - g - 2) = T_{0}(m_{g-1} - 2) = 3^{g-1}$
and $T_{0}(n - g - 3) = T_{0}(m_{g-1} - 3) = 3^{g-1}$, so direct
substitution gives us $U_{0}(n - g - 1) = T_{0}(n - g - 1 - T_{0}(n
- g - 2)) = T_{0}(m_{g-1} - 1 - 3^{g-1}) = T_{0}(m_{g-2} - 1) =
3^{g-2}$, and $U_{0}(n - g - 2) = T_{0}(n - g - 2 - T_{0}(n - g -
3)) = T_{0}(m_{g-1} - 2 - 3^{g-1}) = T_{0}(m_{g-2} - 2) = 3^{g-2}$.
Recall that above we have shown that $U_{1}(n - 1) = U_{1}(n - 2) =
3^{g-2}$, thus $U_{1}(n - 1) = U_{0}(n - g - 1)$ and $U_{1}(n - 2) =
U_{0}(n - g - 2)$. Combining this with $U_{1}(n) = U_{0}(n - g)$, we
have $T_{1}(n) = T_{0}(n - g)$. This concludes the base case for the
``inner induction''.

For $n$ in the $(g - 1)^{th}$ shifted generation with $n &gt; m_{g-1} + g$, we suppose the theorem is true for any number in this generation smaller than $n$, i.e. we suppose for any $i \in [m_{g-1} + g, n - 1] = I(g; n - 1)$, the following two statements hold:

(\textbf{1}) For $i \in [m_{g-1} + g, m_{g} + g - 4] \cap I(g; n - 1)$, $3^{g-1} &lt; T_{1}(i) &lt; 3^{g}$ and $3^{g-2} \leq U_{1}(i), U_{1}(i - 1), U_{1}(i - 2) \leq 3^{g-1}$. For $i \in [m_{g} + g - 3, m_{g} + g] \cap I(g; n - 1)$, $T_{1}(i) = 3^{g}$ and $U_{1}(i) = U_{1}(i - 1) = U_{1}(i - 2) = 3^{g-1}$.

(\textbf{2}) For $i \in [m_{g-1} + g, m_{g} + g - 1] \cap I(g; n - 1)$, $T_{1}(i) = T_{0}(i - g)$.
%we need to change the numbering above to 3) &amp; 4) so there is no confusion between the other two statements in the theorem?

We need to show the theorem is true for $i = n$. This time we begin
with (\textbf{2}). It's sufficient to show $U_{1}(n) = U_{0}(n - g),
U_{1}(n - 1) = U_{0}(n - g - 1), U_{1}(n - 2) = U_{0}(n - g - 2)$,
from which we conclude that $T_{1}(n) = T_{0}(n - g)$ by definition.
From \cite{cct} we have a thorough understanding of the values of
$T_{0}$, so we deal with $U_{0}$ first, working backwards. Since $n
\in [m_{g-1} + g, m_{g} + g - 1]$, then $n - g \in [m_{g-1}, m_{g} -
1]$, which is the $(g - 1)^{th}$ generation (non-shifted). Thus by
Theorem 3.15 in \cite{cct} and Lemma \ref{lemma21} above we have
$3^{g-1} &lt; T_{0}(n - g) \leq 3^{g}$ and $3^{g-2} \leq U_{0}(n - g),
U_{0}(n - g - 1), U_{0}(n - g - 2) \leq 3^{g-1}$. Note that $U_{0}(n
- g) = T_{0}(n - g - T_{0}(n - g - 1)) \in [3^{g-2}, 3^{g-1}]$, by
Theorem 3.15 in \cite{cct} again, and $n - g - T_{0}(n - g - 1) \in
[m_{g-2} - 3, m_{g-1} - 1]$. Hence $n - g - T_{0}(n - g - 1) + g - 1
\in [m_{g-2} + g - 4, m_{g-1} + g - 2]$. For $g\geq 4$ this latter interval is in the union of the $(g -
2)^{th}$ shifted generation and the $(g - 3)^{th}$ shifted
generation, so (\textbf{2}) holds for this interval by the induction
assumption on $g$. For $g=3$, $[m_{g-2} + g - 4, m_{g-1} + g - 2] = [6,17]$, which equals the union of the intervals $[6,8]$ and $[9,17]$. Further, $[9,17]$ is contained in the first generation where (\textbf{2}) holds by induction. So we need only check the values 6,7 and 8. By Tables \ref{table11} and \ref{table12} we confirm that $T_{1}(6) = T_{0}(4)$, $T_{1}(7) = T_{0}(5)$, $T_{1}(8) = T_{0}(6)$. Thus $T_{0}(n - g - T_{0}(n - g - 1)) = T_{1}(n -
g - T_{0}(n - g - 1) + g - 1)$. And by the induction assumption on
$n$, (\textbf{2}) holds for $i = n - 1$, so $T_{1}(n - 1) = T_{0}(n
- g - 1)$. In summary, we have $U_{0}(n - g) = T_{0}(n - g - T_{0}(n
- g - 1)) = T_{1}(n - g - T_{0}(n - g - 1) + g - 1) = T_{1}(n - g -
T_{1}(n - 1) + g - 1) = U_{1}(n)$. Similarly, $U_{0}(n - g - 1) =
T_{0}(n - g - 1 - T_{0}(n - g - 2)) \in [3^{g-2}, 3^{g-1}]$ yields
$n - g - 1 - T_{0}(n - g - 2) \in [m_{g-2} - 3, m_{g-1} - 1]$ by the
same reason above, while the same holds for $T_{0}(n - g - 1 -
T_{0}(n - g - 2)) = T_{1}(n - g - 1 - T_{0}(n - g - 2) + g - 1)$ and
$T_{1}(n - 2) = T_{0}(n - g - 2)$. Direct substitution gives
$U_{0}(n - g - 1) = T_{1}(n - g - 1 - T_{1}(n - 2) + g - 1) =
U_{1}(n - 1)$. Further by the same reasoning, we have $U_{0}(n - g -
2) = U_{1}(n - 2)$. Combining the three equations above gives
$T_{1}(n) = T_{0}(n - g)$, which completes the proof of
(\textbf{2}).

To prove (\textbf{1}) first notice that the value of $T_{1}(n)$ is
just the value of $T_0(n - g)$, and the values of $U_{1}(n), U_{1}(n
- 1), U_{1}(n - 2)$ are just the values of $U_{0}(n - g), U_{0}(n -
g - 1)$ and $U_{0}(n - g - 2)$, where $n - g \in [m_{g-1}, m_{g} -
1]$ is in the $(g - 1)^{th}$ generation (non-shifted). By \cite{cct} and Lemma \ref{lemma21}
we know exactly the range of these values, so (\textbf{1}) follows
immediately. Finally, the value of $T_{1}(m_{g} + g)$ is readily
computed as follows: by definition $T_{1}(m_{g} + g) = U_{1}(m_{g} +
g) + U_{1}(m_{g} + g - 1) + U_{1}(m_{g} + g - 2) = 3^{g}$. By
Theorem 4.3 in \cite{cct} again, $T_{0}(m_{g} - 1) = T_{0}(m_{g} -
2) = T_{0}(m_{g} - 3) = 3^{g}$, so by the induction assumption on
$g$ and direct substitution we have $U_{1}(m_{g} + g) = T_{1}(m_{g}
+ g - 1 - T_{1}(m_{g} + g - 1)) = T_{1}(m_{g} + g - 1 - T_{0}(m_{g}
+ g - 1 - g)) = T_{1}(m_{g} + g - 1 - 3^{g}) =
T_{1}((\frac{1}{2})3^{g+1} + \frac{1}{2} + g - 1 - 3^{g}) =
T_{1}((\frac{1}{2})3^{g} + g - \frac{1}{2}) = T_{1}(m_{g-1} - 1 + g)
= 3^{g-1}$. Similarly we have $U_{1}(m_{g} + g - 1) = T_{1}(m_{g} +
g - 2 - T_{1}(m_{g} + g - 2)) = T_{1}(m_{g} + g - 2 - T_{0}(m_{g} +
g - 2 - g)) = T_{1}(m_{g} + g - 2 - 3^{g}) = T_{1}(m_{g-1} - 2 + g)
= 3^{g-1}$ and $U_{1}(m_{g} + g - 2) = T_{1}(m_{g} + g - 3 -
T_{1}(m_{g} + g - 3)) = T_{1}(m_{g} + g - 3 - T_{0}(m_{g} + g - 3 -
g)) = T_{1}(m_{g} + g - 3 - 3^{g}) = T_{1}(m_{g-1} - 3 + g) =
3^{g-1}$. Summing these we obtain $T_{1}(m_{g} + g) = 3^{g} =
T_{0}(m_{g}  - 1)$. Thus both (\textbf{1}) and (\textbf{2}) are
confirmed for $T_{1}(m_{g} + g)$. This completes the ``inner
induction'' on $n$, so the theorem is true for $n \in [m_{g-1} + g,
m_{g} + g]$, the $(g - 1)^{th}$ shifted generation, as required.
This completes the outer induction on $g$ and hence the proof of
Theorem \ref{thm22}.
\end{proof}

\section{The behavior of $T_{s,3}(n)$ for $s \geq 1$}\label{sec3}
Now we consider the behavior of the sequence generated by
\eqref{eq11} with $k = 3$, shift parameter $s \geq 1$ and initial
conditions $T_{s}(1) = T_{s}(2) = T_{s}(3) = . . . = T_{s}(s + 3) =
1$. Let $U_{s}(n) = T_{s}(n - s - T_{s}(n - 1))$, so $T_{s}(n) =
U_{s}(n) + U_{s}(n - 1) + U_{s}(n - 2)$. (Note that here our
notation omits the subscript $k = 3$). Our goal is to generalize
Theorem \ref{thm22} as follows:

\begin{theorem}
\label{thm31} Let $2 \leq g$. For $n \in [m_{g-1} + gs, m_{g} + (g +
1)s - 1]$, the shifted $(g - 1)^{th}$ generation, the following two
statements hold:

(\texttt{\textbf{1}}) For $n \in [m_{g-1} + gs, m_{g} + gs - 4]$,
$3^{g-1} &lt; T_{s}(n) &lt; 3^{g}$ and $3^{g-2} \leq U_{s}(n), U_{s}(n -
1), U_{s}(n - 2) \leq 3^{g-1}$. For $n \in [m_{g} + gs - 3, m_{g} +
(g + 1)s - 1]$, $T_{s}(n) = 3^{g}$ and $U_{s}(n) = U_{s}(n - 1) =
U_{s}(n - 2) = 3^{g-1}$. We say (\texttt{\textbf{1}}) holds for the
pair $(s, g-1)$.

(\texttt{\textbf{2}}) For $n \in [m_{g-1} + gs, m_{g} + (g + 1)s -
2]$, $T_{s}(n) = T_{s-1}(n - g)$. For $n \in [m_{g} + gs - 2, m_{g}
+ (g + 1)s - 1]$, $T_{s}(n) = T_{s-1}(n - g - 1)$. For $r \in
[m_{g-1}+ g(s - 1), m_{g} + (g + 1)(s - 1) - 1]$, $T_{s-1}(r) =
T_{s}(r + g)$. We say (\texttt{\textbf{2}}) holds for the triple $(s
- 1, s, g-1)$.
\end{theorem}



\begin{proof}
Observe that for $s = 1$ we know that (\textbf{1}) holds for $(1,
g)$ for all $g$ by Theorem \ref{thm22}, as does (\textbf{2}) for the
triple $(s - 1, s, g)= (0, 1, g)$ for all $g$.

For an arbitrary positive integer $s$ greater than 1, we proceed by
induction on $s$. By this we mean that for all $g$ we assume that
(\textbf{1}) holds for all the $s$ pairs $(0, g), (1, g), \ldots, (s-1,
g)$ and that (\textbf{2}) holds for the $s-1$ triples $(0, 1, g),
(1, 2, g),\ldots, (s - 2, s-1, g)$. Our immediately preceding observation
establishes the base case for the induction argument.

We need to show that (\textbf{1}) holds for the pair $(s, g)$ and
(\textbf{2}) holds for the triple $(s - 1, s, g)$. To do this we
imitate the proof of Theorem \ref{thm22}, once again applying a
double induction on both $g$ and $n$ (so overall a triple
induction!). We begin with the so called ``outer induction'' on $g$.

We first establish the base case for $g = 2$. From the initial
conditions $T_{s}(1) = T_{s}(2) = T_{s}(3) = . . . = T_{s}(s + 3) =
1$ we have, by direct substitution, $T_{s}(s + 4) = T_{s}(s + 5) = .
. .= T_{s}(2s + 6) = 3$. Further direct computation yields that for
$n \in [m_{g-1} + gs, m_{g} + gs - 4] = [7 + 2s, 12 + 2s]$ we have
$T_{s}(n) \in (3, 9)$ and $U_{s}(n), U_{s}(n - 1), U_{s}(n - 2) \in
[1, 3]$. And similar computation shows that for $n \in [m_{g} + gs -
3, m_{g} + (g + 1)s - 1] = [13 + 2s, 15 + 3s]$, $T_s(n) = 9$ and
$U_{s}(n) = U_{s}(n - 1) = U_{s}(n - 2) = 3$. This confirms
(\textbf{1}).

In a similar way we compute the values of $T_{s-1}(n - g)$.
Combining these with the values of $T_{s}(n)$, we find that
(\textbf{2}) is immediate. This concludes the base case for the
``outer induction'', that is, (\textbf{1}) holds for the pair
$(s,1)$ and (\textbf{2}) holds for the triple $(s-1, s, 1)$.

The induction assumption is that (\textbf{1}) holds for the pairs
$(s,1), (s,2), \ldots, (s, g-2)$ and (\textbf{2}) holds for the triples
$(s-1, s, 1), (s-1, s, 2), \ldots, (s-1, s, g-2)$. We want to show that
(\textbf{1}) holds for the pair $(s, g-1)$ and (\textbf{2}) holds
for the triple $(s-1, s, g-1)$.

We proceed by an ``inner induction'' on $n$ within the $(g -
1)^{th}$ shifted generation, which is the interval $n \in [m_{g-1} +
gs, m_{g} + (g + 1)s - 1]$. First we check the initial value $n =
m_{g-1} + gs$. Specifically, we confirm that for this value of $n$,
$T_{s}(n) \in (3^{g-1}, 3^{g})$, $U_{s}(n), U_{s}(n - 1), U_{s}(n -
2) \in [3^{g-2}, 3^{g-1}]$, and further $T_{s}(n) = T_{s-1}(n - g)$.

Since $n = m_{g-1} + gs$ is the first term of the $(g - 1)^{th}$
shifted generation, $n - 1 = m_{g-1} + gs - 1$ is the last term of
the $(g - 2)^{th}$ shifted generation. By the induction assumption
on $g$, (\textbf{1}) holds for $(s, g-2)$. Thus $T_{s}(n - 1) =
3^{g-1}$, while $U_{s}(n - 1) = U_{s}(n - 2) = U_{s}(n - 3) =
3^{g-2}$. So $U_{s}(n) = T_{s}(n - s - T_{s}(n - 1)) = T_{s}(m_{g-1}
+ gs - s - 3^{g-1}) = T_{s}(m_{g-2} + (g - 1)s)$. Note that $m_{g-2}
+ (g - 1)s$ is the first member of the $(g - 2)^{th}$ shifted
generation. Since there are more than $s+3$ terms in the generation and only the last $s+3$ terms are powers of 3 it follows by the induction assumption on $g$ that
$U_{s}(n) = T_{s}(m_{g-2} + (g - 1)s) \in (3^{g-2}, 3^{g-1})$. So
$T_{s}(n) = U_{s}(n) + U_{s}(n - 1) + U_{s}(n - 2) \in (3^{g-1},
3^{g})$ and $U_{s}(n), U_{s}(n - 1), U_{s}(n - 2) \in [3^{g-2},
3^{g-1}]$. This confirms (\textbf{1}).

We prove (\textbf{2}) similarly. By the above argument $U_{s}(n) =
T_{s}(m_{g-2} + (g - 1)s)$, so by the induction assumption on $g$
that (\textbf{2}) holds for $(s - 1, s, g-2)$ we have $U_{s}(n) =
T_{s}(m_{g-2} + (g - 1)s) = T_{s-1}(m_{g-2} + (g - 1)(s - 1))$.
Since $n = m_{g-1} + gs$, we have $T_{s-1}(n - g - 1) =
T_{s-1}(m_{g-1} + g(s - 1) - 1) = 3^{g-1}$ by the induction
assumption on $s$ that (\textbf{1}) holds for $(s - 1, g-2)$. So
$U_{s-1}(n - g) = T_{s-1}(n - g - s - T_{s-1}(n - g - 1)) =
T_{s-1}(m_{g-1} + g(s - 1) - (s - 1) - T_{s-1}(m_{g-1} + gs - g -
1)) = T_{s-1}(m_{g-1} - 3^{g-1} + (g - 1)(s - 1)) = T_{s-1}(m_{g-2}
+ (g - 1)(s - 1))$. Thus we get $U_{s}(n) = T_{s-1}(m_{g-2} + (g -
1)(s - 1)) = U_{s-1}(n - g)$.

Note that $n - g - 1 = m_{g-1} + g(s - 1) - 1$ is the last term of
the $(g - 2)^{th}$ shifted generation for the parameter $(s - 1)$.
Hence by the induction assumption on $s$, $U_{s-1}(n - g - 1) =
U_{s-1}(n - g - 2) = U_{s-1}(n - g - 3) = 3^{g-2}$. Recall we have
shown above that $U_{s}(n - 1) = U_{s}(n - 2) = 3^{g-2}$. Thus
$U_{s}(n - 1) = U_{s-1}(n - g - 1)$ and $U_{s}(n - 2) = U_{s-1}(n -
g - 2)$. Combining this with $U_{s}(n) = U_{s-1}(n - g)$, we have
$T_{s}(n) = T_{s-1}(n - g)$. This concludes the base case for the
``inner induction''.

For general $n$ in the shifted $(g - 1)^{th}$ generation, with $n
&gt; m_{g-1} + gs$, we suppose the theorem is true for any number in
this generation smaller than $n$, i.e. we suppose for any $i \in
[m_{g-1} + gs, n - 1] = I(s, g; n - 1)$, the following two
statements hold:

(\textbf{1}) For $i \in [m_{g-1} + gs, m_{g} + gs - 4] \cap I(s, g;
n - 1)$, $3^{g-1} &lt; T_{s}(i) &lt; 3^{g}$ and $3^{g-2} \leq U_{s}(i),
U_{s}(i - 1), U_{s}(i - 2) \leq 3^{g-1}$. For $i \in [m_{g} + gs -
3, m_g + (g + 1)s - 1] \cap I(s, g; n - 1)$, $T_{s}(i) = 3^{g}$ and
$U_{s}(i) = U_{s}(i - 1) = U_{s}(i - 2) = 3^{g-1}$. We say
(\textbf{1}) holds for $i$.

(\textbf{2}) For $i \in [m_{g-1} + gs, m_g + (g + 1)s - 2] \cap I(s,
g; n - 1)$, $T_{s}(i) = T_{s-1}(i - g)$. We say (\textbf{2}) holds
for $i$.

We show now that both (\textbf{1}) and (\textbf{2}) are true for $i
= n$. This time we begin with (\textbf{2}). Since $T_{s}(n) =
U_{s}(n) + U_{s}(n - 1) + U_{s}(n - 2)$ it's sufficient to show
$U_{s}(n) = U_{s-1}(n - g), U_{s}(n - 1) = U_{s-1}(n - g - 1),
U_{s}(n - 2) = U_{s-1}(n - g - 2)$, from which we conclude that
$T_{s}(n) = T_{s-1}(n - g)$. By the induction assumption on $s$ we
have that (\textbf{1}) holds for $(s-1,1), (s-1,2), \ldots, (s-1,
g-1)$. Thus we have a thorough understanding of the values of
$T_{s-1}$, so we deal with $U_{s-1}$ first, working backwards.

As in the statement of (\textbf{2}) above, first we consider $n \in
[m_{g-1} + gs, m_{g} + (g + 1)s - 2]$. Then $n - g \in [m_{g-1} +
g(s - 1), m_{g} + (g + 1)(s - 1) - 1]$, which is the $(g - 1)^{th}$
shifted generation for parameter $s - 1$. Therefore by (\textbf{1})
for $(s-1,g-1)$ we have $3^{g-1} &lt; T_{s-1}(n - g) \leq 3^{g}$ and
$3^{g-2} \leq U_{s-1}(n - g), U_{s-1}(n - g - 1), U_{s-1}(n - g - 2)
\leq 3^{g-1}$. By the definition of $U$ we have $U_{s-1}(n - g) =
T_{s-1}(n - g - (s - 1) - T_{s-1}(n - g - 1))$. But $3^{g-2} \leq
U_{s-1}(n - g) \leq 3^{g-1}$ so $T_{s-1}(n - g - (s - 1) - T_{s-1}(n
- g - 1)) \in [3^{g-2}, 3^{g-1}$.

Further, by the induction assumption on (\textbf{1}) for $(s-1,g-3)$
and $(s-1,g-2)$ we have that $n - g - (s - 1) - T_{s-1}(n - g - 1)
\in [m_{g-2} + (g - 2)(s - 1) - 3, m_{g-1} + g(s - 1) - 1]$. But
note that this interval consists of the last three members of the
$(g-3)^{th}$ shifted generation for parameter $s-1$ together with
all of the $(g-2)^{th}$ shifted generation for parameter $s-1$. By
the induction assumption on $g$ it follows that (\textbf{2}) holds
for $(s-1, s, g-3)$ and $(s-1, s, g-2)$ so it holds on this
interval. Now let $r= n - g - (s - 1) - T_{s-1}(n - g - 1)$ which
is in this interval. Then we have $T_{s-1}(r) = T_{s}(r + g - 1)$.

But by the induction assumption on the parameter $n$ that
(\textbf{2}) holds for $n-1$ we have $T_{s}(n - 1) = T_{s-1}(n - g -
1)$. Thus $T_{s}(r + g - 1)= T_{s}(n - g - (s - 1) - T_{s-1}(n - g -
1)+g-1)=T_{s}(n - g - (s - 1) - T_{s}(n - 1)+g-1)$. The last term is
just $U_{s}(n)$. But $T_{s-1}(r)=U_{s-1}(n - g)$. Thus $U_{s-1}(n -
g)=U_{s}(n)$.

Similarly, $U_{s-1}(n - g - 1) = T_{s-1}(n - g - 1 - (s - 1) -
T_{s-1}(n - g - 2)) \in [3^{g-2}, 3^{g-1}]$ yields $n - g - 1 - (s -
1) - T_{s-1}(n - g - 2) \in [m_{g-2} + (g - 2)(s - 1) - 3, m_{g-1} +
g (s - 1) - 1]$ by the same reason as above, while the same holds
for $T_{s-1}(n - g - 1 - (s - 1) - T_{s-1}(n - g - 2)) = T_{s}(n - g
- 1 - (s - 1) - T_{s-1}(n - g - 2) + g - 1)$ and $T_{s}(n - 2) =
T_{s-1}(n - g - 2)$. Direct substitution gives $U_{s-1}(n - g - 1) =
T_{s}(n - 1 - s - T_{s}(n - 2)) = U_{s}(n - 1)$. Further, by the
same reasoning, we have $U_{s-1}(n - g - 2) = U_{s}(n - 2)$.
Combining the three equations above we get $T_{s}(n) = T_{s-1}(n -
g)$.

This proves the initial claim in (\textbf{2}). We conclude the proof
of (\textbf{2}) below by directly computing the value of
$T_{s}(m_{g} + (g + 1)s - 1)$, which is the value of $T$ at the last
term in the shifted $(g-1)^{th}$ generation for parameter $s$.

To prove (\textbf{1}) first notice that the value of $T_{s}(n)$ is
just the value of $T_{s-1}(n - g)$, and the values of $U_{s}(n),
U_{s}(n - 1), U_{s}(n - 2)$ are just the values of $U_{s-1}(n - g),
U_{s-1}(n - g - 1)$ and $U_{s-1}(n - g - 2)$, where $n - g \in
[m_{g-1} + g(s - 1) + 1, m_{g} + (g + 1)(s - 1) - 1]$ is in the $(g
- 1)^{th}$ shifted generation for parameter $s - 1$. By the
induction assumption on $s$ we know exactly the range of these
values, so (\textbf{1}) follows immediately.

Finally, we compute the value of $T_{s}(m_{g} + (g + 1)s - 1)$
as follows: by definition $T_{s}(m_{g} + (g + 1)s - 1) = U_{s}(m_{g}
+ (g + 1)s - 1) + U_{s}(m_{g} + (g + 1)s - 2) + U_{s}(m_{g} + (g +
1)s - 3) = 3^{g}$. By the induction assumption on $s$,
$T_{s-1}(m_{g} + (g + 1)(s - 1) - 1) = T_{s-1}(m_{g} + (g + 1)(s -
1) - 2) = T_{s-1}(m_{g} + (g + 1)(s - 1) - 3) = 3^{g}$. So by the
induction assumption on $g$ and direct substitution we have
$U_{s}(m_{g} + (g + 1)s - 1) = T_{s}(m_{g} + (g + 1)s - 1 - s -
T_{s}(m_{g} + (g + 1)s - 2)) = T_{s}(m_{g }+ (g + 1)s - 1 - s -
T_{s-1}(m_{g} + (g + 1)(s - 1) - 1)) = T_{s}(m_{g} + gs - 1 - 3^{g})
= T_{s}(m_{g-1} - 1 + gs) = 3^{g-1}$. Recall above we've shown that
$U_{s}(m_{g} + (g + 1)s - 2) = U_{s}(m_{g} + (g + 1)s - 3) =
3^{g-1}$ since $m_{g} + (g + 1)s - 2$ is in the $(g - 1)^{th}$
shifted generation and is not the last term. Summing these we obtain
$T_{s}(m_{g} + (g + 1)s - 1) = 3^{g} = T_{s-1}(m_{g} + (g + 1)(s -
1) - 1) = T_{s-1}(m_{g} + (g + 1)s - 1 - (g + 1))$. Thus both
(\textbf{1}) and (\textbf{2}) are confirmed for $T_{s}(m_{g} + (g +
1)s - 1)$. This finishes the proof of both (\textbf{1})and
(\textbf{2}) for $i=n$.  Thus the theorem is true for $n \in
[m_{g-1} + gs, m_{g} + (g + 1)s - 1]$, the $(g - 1)^{th}$ shifted
generation, thereby completing the ``inner induction'' on $n$.

This completes the ``outer induction'' on $g$ and hence the
induction on $s$.
\end{proof}

\begin{table}[!p]
\fontsize{7}{7}\selectfont
\caption{First 180 terms of $T_{0,4}(n)$ \textsl{with initial values} $(1, 1, 1, 1)$}\label{table51}
\center{
\begin{tabular*}{0.80\textwidth}{@{\extracolsep{\fill}}l c c c l c c c l c c c}
    \hline
    {}&amp;{}&amp;$n$&amp;{}&amp;{}&amp;{}&amp;$n$&amp;{}&amp;{}&amp;{}&amp;$n$\\
    \cline{2-4}\cline{6-8}\cline{10-12}
    {}&amp;1&amp;2&amp;3&amp;{}&amp;1&amp;2&amp;3&amp;{}&amp;1&amp;2&amp;3\\
    \hline
$T(n+0)$&amp;1&amp;1&amp;1&amp;$T(n+60)$&amp;46&amp;46&amp;49&amp;$T(n+120)$&amp;94&amp;91&amp;91\\
$T(n+3)$&amp;1&amp;4&amp;4&amp;$T(n+63)$&amp;49&amp;46&amp;52&amp;$T(n+123)$&amp;94&amp;94&amp;94\\
$T(n+6)$&amp;4&amp;4&amp;7&amp;$T(n+66)$&amp;52&amp;49&amp;55&amp;$T(n+126)$&amp;97&amp;97&amp;94\\
$T(n+9)$&amp;7&amp;7&amp;10&amp;$T(n+69)$&amp;52&amp;52&amp;58&amp;$T(n+129)$&amp;100&amp;100&amp;97\\
$T(n+12)$&amp;7&amp;10&amp;13&amp;$T(n+72)$&amp;55&amp;55&amp;58&amp;$T(n+132)$&amp;103&amp;100&amp;100\\
$T(n+15)$&amp;10&amp;13&amp;13&amp;$T(n+75)$&amp;55&amp;58&amp;61&amp;$T(n+135)$&amp;106&amp;103&amp;103\\
$T(n+18)$&amp;13&amp;16&amp;16&amp;$T(n+78)$&amp;58&amp;61&amp;61&amp;$T(n+138)$&amp;106&amp;103&amp;106\\
$T(n+21)$&amp;16&amp;16&amp;16&amp;$T(n+81)$&amp;61&amp;64&amp;64&amp;$T(n+141)$&amp;109&amp;106&amp;109\\
$T(n+24)$&amp;19&amp;19&amp;19&amp;$T(n+84)$&amp;64&amp;64&amp;64&amp;$T(n+144)$&amp;109&amp;109&amp;112\\
$T(n+27)$&amp;22&amp;19&amp;22&amp;$T(n+87)$&amp;64&amp;67&amp;67&amp;$T(n+147)$&amp;112&amp;112&amp;112\\
$T(n+30)$&amp;25&amp;22&amp;25&amp;$T(n+90)$&amp;67&amp;70&amp;67&amp;$T(n+150)$&amp;112&amp;115&amp;115\\
$T(n+33)$&amp;25&amp;25&amp;28&amp;$T(n+93)$&amp;70&amp;73&amp;70&amp;$T(n+153)$&amp;115&amp;118&amp;115\\
$T(n+36)$&amp;28&amp;28&amp;28&amp;$T(n+96)$&amp;73&amp;73&amp;73&amp;$T(n+156)$&amp;118&amp;121&amp;118\\
$T(n+39)$&amp;31&amp;31&amp;31&amp;$T(n+99)$&amp;76&amp;76&amp;76&amp;$T(n+159)$&amp;121&amp;121&amp;121\\
$T(n+42)$&amp;34&amp;31&amp;34&amp;$T(n+102)$&amp;76&amp;79&amp;79&amp;$T(n+162)$&amp;124&amp;124&amp;124\\
$T(n+45)$&amp;37&amp;34&amp;37&amp;$T(n+105)$&amp;79&amp;82&amp;79&amp;$T(n+165)$&amp;124&amp;127&amp;127\\
$T(n+48)$&amp;37&amp;34&amp;40&amp;$T(n+108)$&amp;82&amp;85&amp;82&amp;$T(n+168)$&amp;127&amp;130&amp;127\\
$T(n+51)$&amp;40&amp;37&amp;43&amp;$T(n+111)$&amp;85&amp;85&amp;82&amp;$T(n+171)$&amp;130&amp;133&amp;130\\
$T(n+54)$&amp;40&amp;40&amp;46&amp;$T(n+114)$&amp;88&amp;88&amp;85&amp;$T(n+174)$&amp;133&amp;133&amp;130\\
$T(n+57)$&amp;43&amp;43&amp;46&amp;$T(n+117)$&amp;91&amp;88&amp;88&amp;$T(n+177)$&amp;136&amp;136&amp;133\\
\hline
\end{tabular*}
}
\end{table}

\begin{table}[!p]
\fontsize{7}{7}\selectfont
\caption{First 180 terms of $T_{1,4}(n)$ \textsl{with initial values} $(1, 1, 1, 1, 1)$}\label{table52}
\center{
\begin{tabular*}{0.80\textwidth}{@{\extracolsep{\fill}}l r r r l r r r l r r r}
    \hline
    {}&amp;{}&amp;$n$&amp;{}&amp;{}&amp;{}&amp;$n$&amp;{}&amp;{}&amp;{}&amp;$n$&amp;\\
    \cline{2-4}\cline{6-8}\cline{10-12}
    {}&amp;1&amp;2&amp;3&amp;{}&amp;1&amp;2&amp;3&amp;{}&amp;1&amp;2&amp;3\\
    \hline
$T(n+0)$&amp;1&amp;1&amp;1&amp;$T(n+60)$&amp;43&amp;43&amp;46&amp;$T(n+120)$&amp;85&amp;91&amp;88\\
$T(n+3)$&amp;1&amp;1&amp;4&amp;$T(n+63)$&amp;46&amp;46&amp;49&amp;$T(n+123)$&amp;88&amp;94&amp;91\\
$T(n+6)$&amp;4&amp;4&amp;4&amp;$T(n+66)$&amp;49&amp;46&amp;52&amp;$T(n+126)$&amp;91&amp;94&amp;94\\
$T(n+9)$&amp;4&amp;7&amp;7&amp;$T(n+69)$&amp;52&amp;49&amp;55&amp;$T(n+129)$&amp;94&amp;97&amp;97\\
$T(n+12)$&amp;7&amp;10&amp;7&amp;$T(n+72)$&amp;52&amp;52&amp;58&amp;$T(n+132)$&amp;94&amp;100&amp;100\\
$T(n+15)$&amp;10&amp;13&amp;10&amp;$T(n+75)$&amp;55&amp;55&amp;58&amp;$T(n+135)$&amp;97&amp;103&amp;100\\
$T(n+18)$&amp;13&amp;13&amp;13&amp;$T(n+78)$&amp;55&amp;58&amp;61&amp;$T(n+138)$&amp;100&amp;106&amp;103\\
$T(n+21)$&amp;16&amp;16&amp;16&amp;$T(n+81)$&amp;58&amp;61&amp;61&amp;$T(n+141)$&amp;103&amp;106&amp;103\\
$T(n+24)$&amp;16&amp;16&amp;16&amp;$T(n+84)$&amp;61&amp;64&amp;64&amp;$T(n+144)$&amp;106&amp;109&amp;106\\
$T(n+27)$&amp;19&amp;19&amp;19&amp;$T(n+87)$&amp;64&amp;64&amp;64&amp;$T(n+147)$&amp;109&amp;109&amp;109\\
$T(n+30)$&amp;22&amp;19&amp;22&amp;$T(n+90)$&amp;64&amp;64&amp;67&amp;$T(n+150)$&amp;112&amp;112&amp;112\\
$T(n+33)$&amp;25&amp;22&amp;25&amp;$T(n+93)$&amp;67&amp;67&amp;70&amp;$T(n+153)$&amp;112&amp;112&amp;115\\
$T(n+36)$&amp;25&amp;25&amp;28&amp;$T(n+96)$&amp;67&amp;70&amp;73&amp;$T(n+156)$&amp;115&amp;115&amp;118\\
$T(n+39)$&amp;28&amp;28&amp;28&amp;$T(n+99)$&amp;70&amp;73&amp;73&amp;$T(n+159)$&amp;115&amp;118&amp;121\\
$T(n+42)$&amp;31&amp;31&amp;31&amp;$T(n+102)$&amp;73&amp;76&amp;76&amp;$T(n+162)$&amp;118&amp;121&amp;121\\
$T(n+45)$&amp;34&amp;31&amp;34&amp;$T(n+105)$&amp;76&amp;76&amp;79&amp;$T(n+165)$&amp;121&amp;124&amp;124\\
$T(n+48)$&amp;37&amp;34&amp;37&amp;$T(n+108)$&amp;79&amp;79&amp;82&amp;$T(n+168)$&amp;124&amp;124&amp;127\\
$T(n+51)$&amp;37&amp;34&amp;40&amp;$T(n+111)$&amp;79&amp;82&amp;85&amp;$T(n+171)$&amp;127&amp;127&amp;130\\
$T(n+54)$&amp;40&amp;37&amp;43&amp;$T(n+114)$&amp;82&amp;85&amp;85&amp;$T(n+174)$&amp;127&amp;130&amp;133\\
$T(n+57)$&amp;40&amp;40&amp;46&amp;$T(n+117)$&amp;82&amp;88&amp;88&amp;$T(n+177)$&amp;130&amp;133&amp;133\\
\hline
\end{tabular*}
}
\end{table}

\begin{table}[!p]
\fontsize{7}{7}\selectfont
\caption{First 180 terms of $T_{2,4}(n)$ \textsl{with initial values} $(1, 1, 1, 1, 1, 1)$}\label{table53}
\center{
\begin{tabular*}{0.80\textwidth}{@{\extracolsep{\fill}}l r r r l r r r l r r r}
    \hline
    {}&amp;{}&amp;$n$&amp;{}&amp;{}&amp;{}&amp;$n$&amp;{}&amp;{}&amp;{}&amp;$n$\\
    \cline{2-4}\cline{6-8}\cline{10-12}
    {}&amp;1&amp;2&amp;3&amp;{}&amp;1&amp;2&amp;3&amp;{}&amp;1&amp;2&amp;3\\
    \hline
$T(n+0)$&amp;1&amp;1&amp;1&amp;$T(n+60)$&amp;40&amp;40&amp;46&amp;$T(n+120)$&amp;85&amp;82&amp;88\\
$T(n+3)$&amp;1&amp;1&amp;1&amp;$T(n+63)$&amp;43&amp;43&amp;46&amp;$T(n+123)$&amp;88&amp;85&amp;91\\
$T(n+6)$&amp;4&amp;4&amp;4&amp;$T(n+66)$&amp;46&amp;46&amp;49&amp;$T(n+126)$&amp;88&amp;88&amp;94\\
$T(n+9)$&amp;4&amp;4&amp;4&amp;$T(n+69)$&amp;49&amp;46&amp;52&amp;$T(n+129)$&amp;91&amp;91&amp;94\\
$T(n+12)$&amp;7&amp;7&amp;7&amp;$T(n+72)$&amp;52&amp;49&amp;55&amp;$T(n+132)$&amp;94&amp;94&amp;97\\
$T(n+15)$&amp;10&amp;7&amp;10&amp;$T(n+75)$&amp;52&amp;52&amp;58&amp;$T(n+135)$&amp;97&amp;94&amp;100\\
$T(n+18)$&amp;13&amp;10&amp;13&amp;$T(n+78)$&amp;55&amp;55&amp;58&amp;$T(n+138)$&amp;100&amp;97&amp;103\\
$T(n+21)$&amp;13&amp;13&amp;16&amp;$T(n+81)$&amp;55&amp;58&amp;61&amp;$T(n+141)$&amp;100&amp;100&amp;106\\
$T(n+24)$&amp;16&amp;16&amp;16&amp;$T(n+84)$&amp;58&amp;61&amp;61&amp;$T(n+144)$&amp;103&amp;103&amp;106\\
$T(n+27)$&amp;16&amp;16&amp;16&amp;$T(n+87)$&amp;61&amp;64&amp;64&amp;$T(n+147)$&amp;103&amp;106&amp;109\\
$T(n+30)$&amp;19&amp;19&amp;19&amp;$T(n+90)$&amp;64&amp;64&amp;64&amp;$T(n+150)$&amp;106&amp;109&amp;109\\
$T(n+33)$&amp;22&amp;19&amp;22&amp;$T(n+93)$&amp;64&amp;64&amp;64&amp;$T(n+153)$&amp;109&amp;112&amp;112\\
$T(n+36)$&amp;25&amp;22&amp;25&amp;$T(n+96)$&amp;67&amp;67&amp;67&amp;$T(n+156)$&amp;112&amp;112&amp;112\\
$T(n+39)$&amp;25&amp;25&amp;28&amp;$T(n+99)$&amp;70&amp;67&amp;70&amp;$T(n+159)$&amp;115&amp;115&amp;115\\
$T(n+42)$&amp;28&amp;28&amp;28&amp;$T(n+102)$&amp;73&amp;70&amp;73&amp;$T(n+162)$&amp;118&amp;115&amp;118\\
$T(n+45)$&amp;31&amp;31&amp;31&amp;$T(n+105)$&amp;73&amp;73&amp;76&amp;$T(n+165)$&amp;121&amp;118&amp;121\\
$T(n+48)$&amp;34&amp;31&amp;34&amp;$T(n+108)$&amp;76&amp;76&amp;76&amp;$T(n+168)$&amp;121&amp;121&amp;124\\
$T(n+51)$&amp;37&amp;34&amp;37&amp;$T(n+111)$&amp;79&amp;79&amp;79&amp;$T(n+171)$&amp;124&amp;124&amp;124\\
$T(n+54)$&amp;37&amp;34&amp;40&amp;$T(n+114)$&amp;82&amp;79&amp;82&amp;$T(n+174)$&amp;127&amp;127&amp;127\\
$T(n+57)$&amp;40&amp;37&amp;43&amp;$T(n+117)$&amp;85&amp;82&amp;85&amp;$T(n+177)$&amp;130&amp;127&amp;130\\
\hline
\end{tabular*}
}
\end{table}

\section{The behavior of $T_{s,k}(n)$ for $s \geq 1$ and odd $k$}\label{sec4}
The arguments in Section \ref{sec2} and Section \ref{sec3} for the
case $k=3$ rely on several key results from \cite{cct}, analogues of
which hold for any odd $k$. It follows that we can generalize all of
the preceding, in particular Lemma \ref{lemma21} and Theorem
\ref{thm31}, in a natural way. Because the proofs would be entirely
analogous to (but even more tedious than) the ones given above we
limit ourselves to a statement of these extensions.

Consider the recursion \eqref{eq11} with $s \geq 0$, odd $k \geq 3$,
and the initial conditions $T_{s,k}(n) = 1$ for $1 \leq n \leq s +
k$. Define $U_{s,k}(n) = T_{s,k}(n - s - T_{s,k}(n - 1))$. Once again, as in Definition
5.7 in \cite{cct}, for any $g&gt; 0$ call the interval (of the domain
of the sequence) $[m_{g}, m_{g+1} - 1]$ the $g^{th}$ generation of
the sequence $T_{s,k}(n)$, written as $gen(g)$, where $m_{g} =
\frac{1}{k-1}(k^{g+1} + k^{2} - k - 1)$.


\begin{lemma}
\label{lemma41} Let $2 \leq g$, and suppose that $n$ is in the $(g -
1)^{th}$ generation. Then $k^{g-2} \leq U_{s,k}(n), U_{s,k}(n - 1),
\ldots, U_{s,k}(n - k + 1) \leq k^{g-1}$. Moreover, if $n$ is the last
term of the generation, then $U_{s,k}(n) = U_{s,k}(n - 1) = \cdots =
U_{s,k}(n - k + 1) = k^{g-1}$.
\end{lemma}


\begin{theorem}
\label{thm42} Let $s \geq 1$ and $2 \leq g$. For $n \in [m_{g-1} + gs, m_{g} + (g +
1)s - 1]$, the shifted $(g - 1)^{th}$ generation, the following two
statements hold:

(\texttt{\textbf{1}}) If $n$ is one of the last $k + s$ terms of the
generation, then $T_{s,k}(n) = k^{g}$ and $U_{s,k}(n) = U_{s,k}(n -
1) = \cdots =  U_{s,k}(n - k + 1) = k^{g-1}$. If $n$ is any other
member of the generation, then $k^{g-1} &lt; T_{s,k}(n) &lt; k^{g}$ and
$k^{g-2} \leq U_{s,k}(n), U_{s,k}(n - 1), \ldots , U_{s,k}(n - k + 1)
\leq k^{g-1}$.

(\texttt{\textbf{2}}) If $n$ is the last term of the generation,
$T_{s,k}(n) = T_{s-1,k}(n - g - 1)$. If $n$ is any other member of
the generation, then $T_{s,k}(n) = T_{s-1,k}(n - g)$.
\end{theorem}



\section{Conjectures for even $k$}\label{sec5}

For even $k$ the effect of the shift parameter $s$ on the behavior
of the sequences generated by \eqref{eq11} with the initial
conditions $T_{s,k}(n) = 1$ for $1 \leq n \leq s + k$ appears to be
quite similar. We conjecture that the sequences $T_{s,k}(n)$ and
$T_{0,k}(n)$ are essentially the same, with the only differences in
these sequences occurring in the frequencies with which the powers
of $k$ occur. In particular, in the sequence $T_{s,k}(n)$ we
conjecture that each value $k^r$ occurs precisely $s + k + (r-1)$
times. See Tables \ref{table51}, \ref{table52}, and \ref{table53}
for an example of this for $k = 4$ and $s = 0$, 1 and 2.

Observe that if the conjectures relating to even $k$ in \cite{cct}
hold then it should be possible to prove our present conjectures by
following an approach analogous to the one adopted above.


\section{Acknowledgements}
The authors are grateful to Wendy Wu for her substantial assistance in the preparation of this manuscript.

\begin{thebibliography}{9}

\bibitem{blt} B. Balmohan, Z. Li and S. Tanny, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Tanny/tanny7.html}{A combinatorial interpretation for certain relatives of} the Conolly sequence,
    \emph{J. Integer Sequences},
    \textbf{11} (2008), Article 08.2.1.

\bibitem{cct} J. Callaghan, J. J. Chew and S. M. Tanny, On the
    behavior of a family of meta-Fibonacci sequences,
    \emph{SIAM J. Discrete Math.} \textbf{18} (2005), 794--824.

\bibitem{bwc} B. W. Conolly, Meta-Fibonacci sequences, in S. Vajda, ed.,
    \emph{Fibonacci \&amp; Lucas Numbers, and the Golden Section},
    Wiley, 1986, pp.\ 127--137.

\bibitem{dt} B. Dalton  and S. M. Tanny, Generational
    structure of meta-Fibonacci sequences, unpublished manuscript, 2005.

\bibitem{dr} C. Deugau and F. Ruskey, Complete $k$-ary trees and generalized
    meta-Fibonacci sequences, in \emph{Fourth Colloquium on Mathematics and
    Computer Science: Algorithms, Trees, Combinatorics and
    Probabilities}, DMTCS Proceedings Series, 2006 AG, pp.\ 203--214.

\bibitem{jr} B. Jackson and F. Ruskey, \href{http://www.combinatorics.org/Volume_13/Abstracts/v13i1r26.html}{Meta-Fibonacci sequences, binary trees
    and extremal compact} codes, \emph{Electronic J. Combinatorics}
    \textbf{13} (2006), \#R26.  

\bibitem{hts1} J. Higham and S. M. Tanny, More well-behaved
    meta-Fibonacci sequences, \emph{Congressus Numerantium}
    \textbf{98} (1993), 3--17.


\bibitem{hts2} J. Higham and S. M. Tanny, A tamely chaotic
    meta-Fibonacci sequence, \emph{Congressus Numerantium}
    \textbf{99} (1994), 67--94.


\bibitem{r} F. Ruskey, private communication (2007).


\bibitem{sna} N. J. A. Sloane, \emph{Online Encyclopedia of
    Integer Sequences}, \hfil\break
\href{http://www.research.att.com/~njas/sequences}{\tt http://www.research.att.com/$\sim$njas/sequences}.

\bibitem{tsm} S. M. Tanny, A well-behaved cousin of the
    Hofstadter sequence, \emph{Discrete Math.} \textbf{105}
    (1992), 227--239.

\end{thebibliography}




\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary  11B37;
Secondary 11B39, 11B99. \\

\noindent \emph{Keywords: } 
Hofstadter, iterated recursion, meta-Fibonacci, Q sequence.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received June 2 2008;
revised version received  August 15 2008.
Published in {\it Journal of Integer Sequences}, August 17 2008.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                

</pre></body></html>