\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 > 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 > 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 {}&{}&$k = 3$&{}&{}&$k = 4$&{}&{}&$k = 5$&{}\\ \cline{2-4}\cline{5-7}\cline{8-10} n\slash s&0&1&2&0&1&2&0&1&2\\ \hline 1&1&1&1&1&1&1&1&1&1\\ 2&2&1&1&2&1&1&2&1&1\\ 3&3&2&1&3&2&1&3&2&1\\ 4&3&3&2&4&3&2&4&3&2\\ 5&4&3&3&4&4&3&5&4&3\\ 6&5&3&3&5&4&4&5&5&4\\ 7&6&4&3&6&4&4&6&5&5\\ 8&6&5&3&7&5&4&7&5&5\\ 9&7&6&4&8&6&4&8&6&5\\ 10&8&6&5&8&7&5&9&7&5\\ 11&9&7&6&9&8&6&10&8&6\\ 12&9&8&6&10&8&7&10&9&7\\ 13&9&9&7&11&9&8&11&10&8\\ 14&10&9&8&12&10&8&12&10&9\\ 15&11&9&9&12&11&9&13&11&10\\ 16&12&9&9&13&12&10&14&12&10\\ 17&12&10&9&14&12&11&15&13&11\\ 18&13&11&9&15&13&12&15&14&12\\ 19&14&12&9&16&14&12&16&15&13\\ 20&15&12&10&16&15&13&17&15&14\\ 21&15&13&11&16&16&14&18&16&15\\ 22&16&14&12&17&16&15&19&17&15\\ 23&17&15&12&18&16&16&20&18&16\\ 24&18&15&13&19&16&16&20&19&17\\ 25&18&16&14&20&17&16&21&20&18\\ 26&18&17&15&20&18&16&22&20&19\\ 27&19&18&15&21&19&16&23&21&20\\ 28&20&18&16&22&20&17&24&22&20\\ 29&21&18&17&23&20&18&25&23&21\\ 30&21&19&18&24&21&19&25&24&22\\ 31&22&20&18&24&22&20&25&25&23\\ 32&23&21&18&25&23&20&26&25&24\\ 33&24&21&19&26&24&21&27&25&25\\ 34&24&22&20&27&24&22&28&25&25\\ 35&25&23&21&28&25&23&29&26&25\\ 36&26&24&21&28&26&24&30&27&25\\ 37&27&24&22&29&27&24&30&28&25\\ 38&27&25&23&30&28&25&31&29&26\\ 39&27&26&24&31&28&26&32&30&27\\ 40&27&27&24&32&29&27&33&30&28\\ 41&28&27&25&32&30&28&34&31&29\\ 42&29&27&26&32&31&28&35&32&30\\ 43&30&27&27&33&32&29&35&33&30\\ 44&30&27&27&34&32&30&36&34&31\\ 45&31&28&27&35&32&31&37&35&32\\ 46&32&29&27&36&33&32&38&35&33\\ 47&33&30&27&36&34&32&39&36&34\\ 48&33&30&27&37&35&32&40&37&35\\ 49&34&31&28&38&36&33&40&38&35\\ 50&35&32&29&39&36&34&41&39&36\\ 51&36&33&30&40&37&35&42&40&37\\ 52&36&33&30&40&38&36&43&40&38\\ 53&36&34&31&41&39&36&44&41&39\\ 54&37&35&32&42&40&37&45&42&40\\ 55&38&36&33&43&40&38&45&43&40\\ 56&39&36&33&44&41&39&46&44&41\\ 57&39&36&34&44&42&40&47&45&42\\ 58&40&37&35&45&43&40&48&45&43\\ 59&41&38&36&46&44&41&49&46&44\\ 60&42&39&36&47&44&42&50&47&45\\ 61&42&39&36&48&45&43&50&48&45\\ 62&43&40&37&48&46&44&50&49&46\\ 63&44&41&38&48&47&44&51&50&47\\ 64&45&42&39&49&48&45&52&50&48\\ 65&45&42&39&50&48&46&53&50&49\\ 66&45&43&40&51&48&47&54&51&50\\ 67&46&44&41&52&49&48&55&52&50\\ 68&47&45&42&52&50&48&55&53&50\\ 69&48&45&42&53&51&48&56&54&51\\ 70&48&45&43&54&52&49&57&55&52\\ 71&49&46&44&55&52&50&58&55&53\\ 72&50&47&45&56&53&51&59&56&54\\ 73&51&48&45&56&54&52&60&57&55\\ 74&51&48&45&57&55&52&60&58&55\\ 75&52&49&46&58&56&53&61&59&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 {}&$n$&{}&{}&$n$&{}&{}&$n$&{}&{}&$n$\\ \cline{2-3}\cline{5-6}\cline{8-9}\cline{11-12} {}&1&2&{}&1&2&{}&1&2&{}&1&2\\ \hline $T(n+0)$&1&1&$T(n+40)$&27&27&$T(n+80)$&59&49&$T(n+120)$&81&81\\ $T(n+2)$&1&3&$T(n+42)$&29&29&$T(n+82)$&59&51&$T(n+122)$&81&83\\ $T(n+4)$&3&3&$T(n+44)$&31&29&$T(n+84)$&61&53&$T(n+124)$&83&85\\ $T(n+6)$&5&5&$T(n+46)$&33&31&$T(n+86)$&61&55&$T(n+126)$&83&87\\ $T(n+8)$&7&5&$T(n+48)$&35&31&$T(n+88)$&63&57&$T(n+128)$&85&89\\ $T(n+10)$&7&7&$T(n+50)$&37&33&$T(n+90)$&63&57&$T(n+130)$&85&91\\ $T(n+12)$&9&9&$T(n+52)$&39&33&$T(n+92)$&65&59&$T(n+132)$&87&93\\ $T(n+14)$&9&11&$T(n+54)$&41&35&$T(n+94)$&67&59&$T(n+134)$&87&95\\ $T(n+16)$&11&13&$T(n+56)$&43&35&$T(n+96)$&67&61&$T(n+136)$&89&97\\ $T(n+18)$&11&15&$T(n+58)$&43&37&$T(n+98)$&69&63&$T(n+138)$&89&99\\ $T(n+20)$&13&17&$T(n+60)$&45&39&$T(n+100)$&69&63&$T(n+140)$&91&101\\ $T(n+22)$&13&17&$T(n+62)$&45&39&$T(n+102)$&71&65&$T(n+142)$&91&103\\ $T(n+24)$&15&19&$T(n+64)$&47&41&$T(n+104)$&73&65&$T(n+144)$&93&105\\ $T(n+26)$&17&19&$T(n+66)$&49&41&$T(n+106)$&73&67&$T(n+146)$&93&107\\ $T(n+28)$&17&21&$T(n+68)$&49&43&$T(n+108)$&75&69&$T(n+148)$&95&109\\ $T(n+30)$&19&23&$T(n+70)$&51&45&$T(n+110)$&75&71&$T(n+150)$&95&111\\ $T(n+32)$&19&23&$T(n+72)$&51&45&$T(n+112)$&77&73&$T(n+152)$&97&113\\ $T(n+34)$&21&25&$T(n+74)$&53&47&$T(n+114)$&77&75&$T(n+154)$&97&113\\ $T(n+36)$&23&25&$T(n+76)$&55&47&$T(n+116)$&79&77&$T(n+156)$&99&115\\ $T(n+38)$&25&27&$T(n+78)$&55&49&$T(n+118)$&79&79&$T(n+158)$&101&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 {}&$n$&{}&{}&$n$&{}&{}&$n$&{}&{}&$n$\\ \cline{2-3}\cline{5-6}\cline{8-9}\cline{11-12} {}&1&2&{}&1&2&{}&1&2&{}&1&2\\ \hline $T(n+0)$&1&1&$T(n+40)$&25&25&$T(n+80)$&55&47&$T(n+120)$&79&77\\ $T(n+2)$&1&1&$T(n+42)$&27&27&$T(n+82)$&57&49&$T(n+122)$&79&79\\ $T(n+4)$&3&3&$T(n+44)$&27&27&$T(n+84)$&59&49&$T(n+124)$&81&81\\ $T(n+6)$&3&3&$T(n+46)$&29&29&$T(n+86)$&59&51&$T(n+126)$&81&81\\ $T(n+8)$&5&5&$T(n+48)$&31&29&$T(n+88)$&61&53&$T(n+128)$&83&83\\ $T(n+10)$&7&5&$T(n+50)$&33&31&$T(n+90)$&61&55&$T(n+130)$&85&83\\ $T(n+12)$&7&7&$T(n+52)$&35&31&$T(n+92)$&63&57&$T(n+132)$&87&85\\ $T(n+14)$&9&9&$T(n+54)$&37&33&$T(n+94)$&63&57&$T(n+134)$&89&85\\ $T(n+16)$&9&9&$T(n+56)$&39&33&$T(n+96)$&65&59&$T(n+136)$&91&87\\ $T(n+18)$&11&11&$T(n+58)$&41&35&$T(n+98)$&67&59&$T(n+138)$&93&87\\ $T(n+20)$&13&11&$T(n+60)$&43&35&$T(n+100)$&67&61&$T(n+140)$&95&89\\ $T(n+22)$&15&13&$T(n+62)$&43&37&$T(n+102)$&69&63&$T(n+142)$&97&89\\ $T(n+24)$&17&13&$T(n+64)$&45&39&$T(n+104)$&69&63&$T(n+144)$&99&91\\ $T(n+26)$&17&15&$T(n+66)$&45&39&$T(n+106)$&71&65&$T(n+146)$&101&91\\ $T(n+28)$&19&17&$T(n+68)$&47&41&$T(n+108)$&73&65&$T(n+148)$&103&93\\ $T(n+30)$&19&17&$T(n+70)$&49&41&$T(n+110)$&73&67&$T(n+150)$&105&93\\ $T(n+32)$&21&19&$T(n+72)$&49&43&$T(n+112)$&75&69&$T(n+152)$&107&95\\ $T(n+34)$&23&19&$T(n+74)$&51&45&$T(n+114)$&75&71&$T(n+154)$&109&95\\ $T(n+36)$&23&21&$T(n+76)$&51&45&$T(n+116)$&77&73&$T(n+156)$&111&97\\ $T(n+38)$&25&23&$T(n+78)$&53&47&$T(n+118)$&77&75&$T(n+158)$&113&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 {}&$n$&{}&{}&$n$&{}&{}&$n$&{}&{}&$n$&{}\\ \cline{2-3}\cline{5-6}\cline{8-9}\cline{11-12} {}&1&2&{}&1&2&{}&1&2&{}&1&2\\ \hline $T(n+0)$&1&1&$T(n+40)$&21&25&$T(n+80)$&51&45&$T(n+120)$&77&73\\ $T(n+2)$&1&1&$T(n+42)$&23&25&$T(n+82)$&53&47&$T(n+122)$&77&75\\ $T(n+4)$&1&3&$T(n+44)$&25&27&$T(n+84)$&55&47&$T(n+124)$&79&77\\ $T(n+6)$&3&3&$T(n+46)$&27&27&$T(n+86)$&57&49&$T(n+126)$&79&79\\ $T(n+8)$&3&3&$T(n+48)$&27&27&$T(n+88)$&59&49&$T(n+128)$&81&81\\ $T(n+10)$&5&5&$T(n+50)$&29&29&$T(n+90)$&59&51&$T(n+130)$&81&81\\ $T(n+12)$&7&5&$T(n+52)$&31&29&$T(n+92)$&61&53&$T(n+132)$&81&83\\ $T(n+14)$&7&7&$T(n+54)$&33&31&$T(n+94)$&61&55&$T(n+134)$&83&85\\ $T(n+16)$&9&9&$T(n+56)$&35&31&$T(n+96)$&63&57&$T(n+136)$&83&87\\ $T(n+18)$&9&9&$T(n+58)$&37&33&$T(n+98)$&63&57&$T(n+138)$&85&89\\ $T(n+20)$&9&11&$T(n+60)$&39&33&$T(n+100)$&65&59&$T(n+140)$&85&91\\ $T(n+22)$&11&13&$T(n+62)$&41&35&$T(n+102)$&67&59&$T(n+142)$&87&93\\ $T(n+24)$&11&15&$T(n+64)$&43&35&$T(n+104)$&67&61&$T(n+144)$&87&95\\ $T(n+26)$&13&17&$T(n+66)$&43&37&$T(n+106)$&69&63&$T(n+146)$&89&97\\ $T(n+28)$&13&17&$T(n+68)$&45&39&$T(n+108)$&69&63&$T(n+148)$&89&99\\ $T(n+30)$&15&19&$T(n+70)$&45&39&$T(n+110)$&71&65&$T(n+150)$&91&101\\ $T(n+32)$&17&19&$T(n+72)$&47&41&$T(n+112)$&73&65&$T(n+152)$&91&103\\ $T(n+34)$&17&21&$T(n+74)$&49&41&$T(n+114)$&73&67&$T(n+154)$&93&105\\ $T(n+36)$&19&23&$T(n+76)$&49&43&$T(n+116)$&75&69&$T(n+156)$&93&107\\ $T(n+38)$&19&23&$T(n+78)$&51&45&$T(n+118)$&75&71&$T(n+158)$&95&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> 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} < T_{1}(n) < 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 > 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} < T_{1}(i) < 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) & 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} < 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} < T_{s}(n) < 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 > 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} < T_{s}(i) < 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} < 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 {}&{}&$n$&{}&{}&{}&$n$&{}&{}&{}&$n$\\ \cline{2-4}\cline{6-8}\cline{10-12} {}&1&2&3&{}&1&2&3&{}&1&2&3\\ \hline $T(n+0)$&1&1&1&$T(n+60)$&46&46&49&$T(n+120)$&94&91&91\\ $T(n+3)$&1&4&4&$T(n+63)$&49&46&52&$T(n+123)$&94&94&94\\ $T(n+6)$&4&4&7&$T(n+66)$&52&49&55&$T(n+126)$&97&97&94\\ $T(n+9)$&7&7&10&$T(n+69)$&52&52&58&$T(n+129)$&100&100&97\\ $T(n+12)$&7&10&13&$T(n+72)$&55&55&58&$T(n+132)$&103&100&100\\ $T(n+15)$&10&13&13&$T(n+75)$&55&58&61&$T(n+135)$&106&103&103\\ $T(n+18)$&13&16&16&$T(n+78)$&58&61&61&$T(n+138)$&106&103&106\\ $T(n+21)$&16&16&16&$T(n+81)$&61&64&64&$T(n+141)$&109&106&109\\ $T(n+24)$&19&19&19&$T(n+84)$&64&64&64&$T(n+144)$&109&109&112\\ $T(n+27)$&22&19&22&$T(n+87)$&64&67&67&$T(n+147)$&112&112&112\\ $T(n+30)$&25&22&25&$T(n+90)$&67&70&67&$T(n+150)$&112&115&115\\ $T(n+33)$&25&25&28&$T(n+93)$&70&73&70&$T(n+153)$&115&118&115\\ $T(n+36)$&28&28&28&$T(n+96)$&73&73&73&$T(n+156)$&118&121&118\\ $T(n+39)$&31&31&31&$T(n+99)$&76&76&76&$T(n+159)$&121&121&121\\ $T(n+42)$&34&31&34&$T(n+102)$&76&79&79&$T(n+162)$&124&124&124\\ $T(n+45)$&37&34&37&$T(n+105)$&79&82&79&$T(n+165)$&124&127&127\\ $T(n+48)$&37&34&40&$T(n+108)$&82&85&82&$T(n+168)$&127&130&127\\ $T(n+51)$&40&37&43&$T(n+111)$&85&85&82&$T(n+171)$&130&133&130\\ $T(n+54)$&40&40&46&$T(n+114)$&88&88&85&$T(n+174)$&133&133&130\\ $T(n+57)$&43&43&46&$T(n+117)$&91&88&88&$T(n+177)$&136&136&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 {}&{}&$n$&{}&{}&{}&$n$&{}&{}&{}&$n$&\\ \cline{2-4}\cline{6-8}\cline{10-12} {}&1&2&3&{}&1&2&3&{}&1&2&3\\ \hline $T(n+0)$&1&1&1&$T(n+60)$&43&43&46&$T(n+120)$&85&91&88\\ $T(n+3)$&1&1&4&$T(n+63)$&46&46&49&$T(n+123)$&88&94&91\\ $T(n+6)$&4&4&4&$T(n+66)$&49&46&52&$T(n+126)$&91&94&94\\ $T(n+9)$&4&7&7&$T(n+69)$&52&49&55&$T(n+129)$&94&97&97\\ $T(n+12)$&7&10&7&$T(n+72)$&52&52&58&$T(n+132)$&94&100&100\\ $T(n+15)$&10&13&10&$T(n+75)$&55&55&58&$T(n+135)$&97&103&100\\ $T(n+18)$&13&13&13&$T(n+78)$&55&58&61&$T(n+138)$&100&106&103\\ $T(n+21)$&16&16&16&$T(n+81)$&58&61&61&$T(n+141)$&103&106&103\\ $T(n+24)$&16&16&16&$T(n+84)$&61&64&64&$T(n+144)$&106&109&106\\ $T(n+27)$&19&19&19&$T(n+87)$&64&64&64&$T(n+147)$&109&109&109\\ $T(n+30)$&22&19&22&$T(n+90)$&64&64&67&$T(n+150)$&112&112&112\\ $T(n+33)$&25&22&25&$T(n+93)$&67&67&70&$T(n+153)$&112&112&115\\ $T(n+36)$&25&25&28&$T(n+96)$&67&70&73&$T(n+156)$&115&115&118\\ $T(n+39)$&28&28&28&$T(n+99)$&70&73&73&$T(n+159)$&115&118&121\\ $T(n+42)$&31&31&31&$T(n+102)$&73&76&76&$T(n+162)$&118&121&121\\ $T(n+45)$&34&31&34&$T(n+105)$&76&76&79&$T(n+165)$&121&124&124\\ $T(n+48)$&37&34&37&$T(n+108)$&79&79&82&$T(n+168)$&124&124&127\\ $T(n+51)$&37&34&40&$T(n+111)$&79&82&85&$T(n+171)$&127&127&130\\ $T(n+54)$&40&37&43&$T(n+114)$&82&85&85&$T(n+174)$&127&130&133\\ $T(n+57)$&40&40&46&$T(n+117)$&82&88&88&$T(n+177)$&130&133&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 {}&{}&$n$&{}&{}&{}&$n$&{}&{}&{}&$n$\\ \cline{2-4}\cline{6-8}\cline{10-12} {}&1&2&3&{}&1&2&3&{}&1&2&3\\ \hline $T(n+0)$&1&1&1&$T(n+60)$&40&40&46&$T(n+120)$&85&82&88\\ $T(n+3)$&1&1&1&$T(n+63)$&43&43&46&$T(n+123)$&88&85&91\\ $T(n+6)$&4&4&4&$T(n+66)$&46&46&49&$T(n+126)$&88&88&94\\ $T(n+9)$&4&4&4&$T(n+69)$&49&46&52&$T(n+129)$&91&91&94\\ $T(n+12)$&7&7&7&$T(n+72)$&52&49&55&$T(n+132)$&94&94&97\\ $T(n+15)$&10&7&10&$T(n+75)$&52&52&58&$T(n+135)$&97&94&100\\ $T(n+18)$&13&10&13&$T(n+78)$&55&55&58&$T(n+138)$&100&97&103\\ $T(n+21)$&13&13&16&$T(n+81)$&55&58&61&$T(n+141)$&100&100&106\\ $T(n+24)$&16&16&16&$T(n+84)$&58&61&61&$T(n+144)$&103&103&106\\ $T(n+27)$&16&16&16&$T(n+87)$&61&64&64&$T(n+147)$&103&106&109\\ $T(n+30)$&19&19&19&$T(n+90)$&64&64&64&$T(n+150)$&106&109&109\\ $T(n+33)$&22&19&22&$T(n+93)$&64&64&64&$T(n+153)$&109&112&112\\ $T(n+36)$&25&22&25&$T(n+96)$&67&67&67&$T(n+156)$&112&112&112\\ $T(n+39)$&25&25&28&$T(n+99)$&70&67&70&$T(n+159)$&115&115&115\\ $T(n+42)$&28&28&28&$T(n+102)$&73&70&73&$T(n+162)$&118&115&118\\ $T(n+45)$&31&31&31&$T(n+105)$&73&73&76&$T(n+165)$&121&118&121\\ $T(n+48)$&34&31&34&$T(n+108)$&76&76&76&$T(n+168)$&121&121&124\\ $T(n+51)$&37&34&37&$T(n+111)$&79&79&79&$T(n+171)$&124&124&124\\ $T(n+54)$&37&34&40&$T(n+114)$&82&79&82&$T(n+174)$&127&127&127\\ $T(n+57)$&40&37&43&$T(n+117)$&85&82&85&$T(n+177)$&130&127&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> 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} < T_{s,k}(n) < 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 \& 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}