\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf On the Behavior of a Variant of \\ \vskip .1in Hofstadter's Q-Sequence } \vskip 1cm \large B. Balamohan, A. Kuznetsov and Stephen Tanny \thanks{Corresponding author.}\\ 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 .2 in \begin{abstract} We completely solve the meta-Fibonacci recursion $$V(n) = V(n - V(n - 1)) + V(n - V(n - 4)),$$ a variant of Hofstadter's meta-Fibonacci $Q$-sequence. For the initial conditions $V(1) = V(2) = V(3) = V(4) = 1$ we prove that the sequence $V(n)$ is monotone, with successive terms increasing by 0 or 1, so the sequence hits every positive integer. We demonstrate certain special structural properties and fascinating periodicities of the associated frequency sequence (the number of times $V(n)$ hits each positive integer) that make possible an iterative computation of $V(n)$ for any value of $n$. Further, we derive a natural partition of the $V$-sequence into blocks of consecutive terms (``\emph{generations}'') with the property that terms in one block determine the terms in the next. We conclude by examining all the other sets of four initial conditions for which this meta-Fibonacci recursion has a solution; we prove that in each case the resulting sequence is essentially the same as the one with initial conditions all ones. \end{abstract} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \section{Introduction}\label{sec1} Hofstadter \cite{hds} introduced several integer sequences by self-referencing recurrences, including his now-famous $Q$-sequence defined as \begin{equation}\label{eq1} Q(n) = Q(n - Q(n - 1)) + Q(n - Q(n - 2)),\ n > 2 \end{equation} with initial conditions $Q(1) = Q(2) = 1$. Virtually nothing has been proved about the enigmatic behavior of this sequence (see Table~\ref{tab11} and Figure~\ref{fig11}), including whether or not the sequence remains well defined for all positive $n$.\footnote{That is, whether or not $Q(n-1)$ and $Q(n-2)$ are both less than $n$ for all positive $n$. If this is not the case we say the sequence ``dies''. In a private communication Hofstadter indicates that the $Q$-sequence has been computed to billions of terms. On this basis it seems highly unlikely that the sequence dies.} \begin{table}[!p] \fontsize{6}{6}\selectfont \caption{First 200 terms of Hofstadter's $Q(n)$}\label{tab11} \center{ \begin{tabular}{l r r r r r l r r r r r} \hline {}&{}&{}&$n$&{}&{}&{}&{}&{}&$n$&{}&{}\\ \cline{2-6}\cline{8-12} {}&1&2&3&4&5&{}&1&2&3&4&5\\ \hline $Q(n+0)$&1&1&2&3&3&$Q(n+100)$&48&54&54&50&60\\ $Q(n+5)$&4&5&5&6&6&$Q(n+105)$&52&54&58&60&53\\ $Q(n+10)$&6&8&8&8&10&$Q(n+110)$&60&60&52&62&66\\ $Q(n+15)$&9&10&11&11&12&$Q(n+115)$&55&62&68&62&58\\ $Q(n+20)$&12&12&12&16&14&$Q(n+120)$&72&58&61&78&57\\ $Q(n+25)$&14&16&16&16&16&$Q(n+125)$&71&68&64&63&73\\ $Q(n+30)$&20&17&17&20&21&$Q(n+130)$&63&71&72&72&80\\ $Q(n+35)$&19&20&22&21&22&$Q(n+135)$&61&71&77&65&80\\ $Q(n+40)$&23&23&24&24&24&$Q(n+140)$&71&69&77&75&73\\ $Q(n+45)$&24&24&32&24&25&$Q(n+145)$&77&79&76&80&79\\ $Q(n+50)$&30&28&26&30&30&$Q(n+150)$&75&82&77&80&80\\ $Q(n+55)$&28&32&30&32&32&$Q(n+155)$&78&83&83&78&85\\ $Q(n+60)$&32&32&40&33&31&$Q(n+160)$&82&85&84&84&88\\ $Q(n+65)$&38&35&33&39&40&$Q(n+165)$&83&87&88&87&86\\ $Q(n+70)$&37&38&40&39&40&$Q(n+170)$&90&88&87&92&90\\ $Q(n+75)$&39&42&40&41&43&$Q(n+175)$&91&92&92&94&92\\ $Q(n+80)$&44&43&43&46&44&$Q(n+180)$&93&94&94&96&94\\ $Q(n+85)$&45&47&47&46&48&$Q(n+185)$&96&96&96&96&96\\ $Q(n+90)$&48&48&48&48&48&$Q(n+190)$&96&128&72&96&115\\ $Q(n+95)$&64&41&52&54&56&$Q(n+195)$&100&84&114&110&93\\ \hline \end{tabular} } \end{table} \begin{table}[!p] \fontsize{6}{6}\selectfont \caption{First 200 terms of $W(n)$}\label{tab12} \center{ \begin{tabular}{l r r r r r l r r r r r} \hline {}&{}&{}&$n$&{}&{}&{}&{}&{}&$n$&{}&{}\\ \cline{2-6}\cline{8-12} {}&1&2&3&4&5&{}&1&2&3&4&5\\ \hline $W(n+0)$&1&1&1&1&2&$W(n+100)$&51&51&64&64&49\\ $W(n+5)$&4&6&7&7&5&$W(n+105)$&48&59&50&54&71\\ $W(n+10)$&3&8&9&11&12&$W(n+110)$&65&68&62&58&61\\ $W(n+15)$&9&9&13&11&9&$W(n+115)$&55&60&65&73&58\\ $W(n+20)$&13&16&13&19&16&$W(n+120)$&49&63&82&55&55\\ $W(n+25)$&11&14&16&21&22&$W(n+125)$&76&62&81&89&56\\ $W(n+30)$&14&14&19&17&22&$W(n+130)$&66&61&61&91&97\\ $W(n+35)$&27&25&16&20&28&$W(n+135)$&65&57&72&63&91\\ $W(n+40)$&22&22&26&25&24&$W(n+140)$&93&63&83&89&81\\ $W(n+45)$&32&26&22&29&29&$W(n+145)$&73&61&81&100&85\\ $W(n+50)$&32&35&32&27&26&$W(n+150)$&89&72&65&85&85\\ $W(n+55)$&34&30&33&40&25&$W(n+155)$&84&82&99&94&56\\ $W(n+60)$&27&46&40&33&32&$W(n+160)$&68&88&97&79&107\\ $W(n+65)$&28&36&50&44&31&$W(n+165)$&99&56&98&108&74\\ $W(n+70)$&36&38&46&53&41&$W(n+170)$&101&100&70&111&102\\ $W(n+75)$&29&41&45&32&54&$W(n+175)$&61&100&96&73&121\\ $W(n+80)$&57&41&43&48&38&$W(n+180)$&107&67&100&100&83\\ $W(n+85)$&40&54&50&54&57&$W(n+185)$&113&118&91&84&95\\ $W(n+90)$&50&44&46&54&53&$W(n+190)$&105&108&104&94&107\\ $W(n+95)$&57&57&47&54&58&$W(n+195)$&101&103&121&101&86\\ \hline \end{tabular} } \end{table} \begin{table}[!p] \fontsize{6}{6}\selectfont \caption{First 200 terms of $V(n)$}\label{tab13} \center{ \begin{tabular}{l r r r r r l r r r r r} \hline {}&{}&{}&$n$&{}&{}&{}&{}&{}&$n$&{}&{}\\ \cline{2-6}\cline{8-12} {}&1&2&3&4&5&{}&1&2&3&4&5\\ \hline $V(n+0)$&1&1&1&1&2&$V(n+100)$&53&54&55&55&56\\ $V(n+5)$&3&4&5&5&6&$V(n+105)$&56&57&57&58&58\\ $V(n+10)$&6&7&8&8&9&$V(n+110)$&58&59&59&60&61\\ $V(n+15)$&9&10&11&11&11&$V(n+115)$&61&62&62&63&63\\ $V(n+20)$&12&12&13&14&14&$V(n+120)$&64&65&65&65&66\\ $V(n+25)$&15&15&16&17&17&$V(n+125)$&66&67&67&68&68\\ $V(n+30)$&17&18&18&19&20&$V(n+130)$&68&69&69&70&71\\ $V(n+35)$&20&21&21&22&22&$V(n+135)$&71&72&72&73&73\\ $V(n+40)$&22&23&23&24&25&$V(n+140)$&74&75&75&75&76\\ $V(n+45)$&25&26&26&27&27&$V(n+145)$&76&77&77&78&79\\ $V(n+50)$&28&29&29&29&30&$V(n+150)$&79&80&80&81&81\\ $V(n+55)$&30&31&32&32&33&$V(n+155)$&82&82&82&83&83\\ $V(n+60)$&33&34&34&34&35&$V(n+160)$&84&85&85&85&86\\ $V(n+65)$&35&36&37&37&38&$V(n+165)$&86&87&87&88&88\\ $V(n+70)$&38&39&39&40&41&$V(n+170)$&88&89&89&90&91\\ $V(n+75)$&41&41&42&42&43&$V(n+175)$&91&92&92&93&93\\ $V(n+80)$&43&44&44&44&45&$V(n+180)$&94&95&95&95&96\\ $V(n+85)$&45&46&47&47&48&$V(n+185)$&96&97&97&98&99\\ $V(n+90)$&48&49&49&50&51&$V(n+190)$&99&100&100&101&101\\ $V(n+95)$&51&51&52&52&53&$V(n+195)$&102&102&102&103&103\\ \hline \end{tabular} } \end{table} Around 1999 Hofstadter and Huber \cite{hhg} introduced the following family of sequences $Q_{r,s}(n)$: for arbitrary positive integers $r$ and $s$, with $r$$<$$s$, \begin{equation}\label{eq2} Q_{r,s} (n) = Q_{r,s} (n - Q_{r,s} (n - r)) + Q_{r,s} (n - Q_{r,s} (n - s)),\ n > s. \end{equation} They explored extensively the behavior of \eqref{eq2} for a wide range of $(r,s)$ values and for various sets of initial conditions ($Q_{r,s}(1)$, $Q_{r,s}(2)$,\ldots, $Q_{r,s}(s)$). Among their outstanding conjectures from this largely empirical work is that for the initial values all ones the only values of $(r,s)$ for which the recurrence \eqref{eq2} does not eventually become undefined (``dies'') are (1,2), (1,4) and (2,4). Notice that the case $(r,s) = (1,2)$ is Hofstadter's original $Q$-sequence (which in the course of their latest work Hofstadter and Huber renamed the $U$-sequence). For $(r,s) = (2,4)$, the sequence $Q_{2,4}(n)$ (renamed $W(n)$) appears to display even more inscrutably wild behavior; compare Table~\ref{tab12} and Figure~\ref{fig12} to Table~\ref{tab11} and Figure~\ref{fig11}, respectively. Like the original $Q$-sequence, to date nothing has been proved about this sequence. \begin{figure}[!p] \center{ \includegraphics[scale=0.6]{q.eps} \caption{Graph of first 200 values of Hofstadter's $Q(n)$}\label{fig11} } \end{figure} \begin{figure}[!p] \center{ \includegraphics[scale=0.6]{w.eps} \caption{Graph of first 200 values of $W(n)$}\label{fig12} } \end{figure} The focus of this paper is on the remaining case, where $(r,s) = (1,4)$. In Table~\ref{tab13} we provide the first 200 values of the sequence $Q_{1,4}(n)$, which Hofstadter and Huber renamed $V(n)$. That is, in the following by $V(n)$ we mean \begin{equation}\label{eq3} V(n) = V(n - V(n - 1)) + V(n - V(n - 4)),\ n > 4 \end{equation} and initial conditions $V(1) = V(2) = V(3) = V(4) = 1$.\footnote{Note that $V(n)$ appears in \cite{sna} as ``Sequence \seqnum{A063882}'' where it is called $v(n)$.} Despite its apparent simplicity, the $V$-sequence has many interesting properties.\footnote{Some of the charms of $V(n)$ are described poetically by Gutman \cite{gk}. To date, this poem and the listing in \cite{sna} are all that has been published about the $V$-sequence.} We begin in Section \ref{sec2} by proving that, like the Conolly and Conway meta-Fibonacci sequences (see \cite{cct, ktv, mcl1}), $V(n)$ is monotone increasing and successive terms differ by at most 1. However, in contrast to its better known cousins, $V(n)$ never hits any number (other than 1) more than 3 times. We also estimate some bounds for $V(n)$ and provide initial results relating to a generational structure for the $V$-sequence that we explore more fully in Section \ref{sec4}. Evidently the $V$-sequence is determined by its frequency sequence, namely, the number of times that $V(n)$ hits each positive integer. In Section \ref{sec3} we derive a precise understanding of the behavior of the frequency sequence. As a result, we are able to prove three recursive rules for generating the frequency sequence first conjectured by Gutman \cite{hhg}. We conclude this section by noting some interesting patterns that occur in the frequency sequence. Many meta-Fibonacci sequences, including the Conolly and Conway sequences with which $V(n)$ shares some properties, can be partitioned naturally into successive finite blocks of consecutive terms with common characteristics. In Section \ref{sec4} we define such a partition for the $V(n)$ sequence. Each term of $V(n)$ in the $k^{th}$ block (suggestively called the ``$k^{th}$ \emph{generation}'') of this partition is a sum of two earlier terms, the first of which is in the $(k-1)^{th}$ block (generation) of the sequence. We provide general formulas for the starting and ending indices for each block, and we deduce some periodicity properties concerning the frequencies of the sequence values at these starting and ending indices. In Section \ref{sec5} we examine all the sequences that result from \eqref{eq3} together with different sets of four initial conditions. We prove that there are only eight sets of initial conditions that generate a sequence that does not die. Each of the resulting sequences are essentially slightly truncated versions of the original $V$-sequence (with initial conditions all 1s). We provide brief concluding remarks in Section \ref{sec6}. \section{Monotonicity}\label{sec2} We begin by showing that the $V$-sequence is nondecreasing and hits every positive integer (other than 1) no more than 3 times.\footnote{This result was first observed in 1999 by Hofstadter and Huber \cite{hhg}. They have never published the details of their proof, which, according to Huber, is ``a long, tedious, case by case tracking down of many branches of cases and sub-cases'' involving the application of something he called ``K-tables'' (after Kellie Gutman).} More precisely we show \begin{theorem}\label{thm21} For $V(n)$ defined in \eqref{eq3} above, the following holds \begin{equation}\label{eq21} V(n) - V(n - 1)\in\{0, 1\} \ for \ n > 1 \end{equation} \begin{equation}\label{eq22} V(n) - V(n - 3)\in\{1, 2\} \ for \ n > 8 \end{equation} \end{theorem} \begin{proof} As in earlier work on meta-Fibonacci sequences (see, for example, \cite{cct, hts2, tsm}) it is necessary to use a multi-statement induction proof on both \eqref{eq21} and \eqref{eq22} simultaneously. From Table~\ref{tab13} \eqref{eq21} is true for $n \leq 20$ while \eqref{eq22} holds for $9 \leq n \leq 20$. For the induction step we assume that \eqref{eq21} is true for all $i20$. We proceed to prove that these statements hold for $n$. We begin with \eqref{eq21}. By the definition \eqref{eq3} of $V$ we have \begin{eqnarray}\label{eq23} V(n) - V(n - 1) &=& V(n - V(n - 1)) + V(n - V(n - 4))\\ & &-V(n - 1 - V(n - 2)) - V(n - 1 - V(n - 5))\nonumber \end{eqnarray} For ease of reference we adopt some suggestive ``family-related'' terminology.\footnote{This terminology seems to originate with Pinn \cite{pks1}. We will have more to say about it in Section \ref{sec4}.} We say that the term $V(n)$ in ``\emph{spot}'' $n$ (the index of the term) is the child of the two $V$-sequence summands defined by the recursion \eqref{eq3}, namely its \emph{mother} $V(n - V(n - 1))$ in spot $(n - V(n - 1))$ and its \emph{father} $V(n - V(n - 4))$ in spot $(n - V(n - 4))$. By the induction hypothesis on \eqref{eq21} we have $V(n - 1)-V(n - 2)\in \{0, 1\}$ and $V(n - 4)-V(n - 5)\in \{0, 1\}$. Thus, in \eqref{eq23} , the difference between the mother spots of $V(n)$ and $V(n - 1)$, that is, $(n - V(n - 1)) - (n - 1 - V(n - 2)) = 1 - (V(n - 1) - V(n - 2))$ is also 0 or 1. By a similar argument we also have that the difference between the father spots of $V(n)$ and $V(n - 1)$, that is, $(n - V(n - 4)) - (n - 1 - V(n - 5)) = 1 - (V(n - 4) - V(n - 5))$, is also 0 or 1. Suppose that $V(n - 1) - V(n - 2) = 1$. Then $V(n - V(n - 1))=V(n - 1 - V(n - 2))$ and so the difference $V(n) - V(n - 1)$ in \eqref{eq23} is determined by the difference $V(n - V(n - 4)) - V(n - 1 - V(n - 5))$ of the fathers of $V(n)$ and $V(n - 1)$. But since the difference between the fathers' spots is 0 or 1, it follows from the induction hypothesis the difference between the fathers of $V(n)$ and $V(n-1)$ is also 0 or 1 . Therefore statement \eqref{thm21} holds. Similarly if $V(n - 4) - V(n - 5) = 1$ then $V(n - V(n - 4)) = V(n - 1 - V(n - 5))$ and \eqref{thm21} holds. The only other case is both $V(n - 1) - V(n - 2) = 0$ and $V(n - 4) - V(n - 5) = 0$. Then the father spots (respectively, the mother spots) of $V(n)$ and $V(n-1)$ differ by 1. Observe that if $V(n - V(n - 1)) = V(n - 1 - V(n - 2))$ then $V(n) - V(n - 1) = V(n - V(n - 4)) - V(n - 1 - V(n - 5))\in \{0, 1\}$, as desired. So we may assume that $V(n - V(n - 1)) = V(n - 1 - V(n - 2)) + 1$. Thus, besides the induction hypothesis we have the following set of assumptions: \begin{equation}\label{eq24} V(n - 1) = V(n - 2)\end{equation} \begin{equation}\label{eq25} V(n - 4) = V(n - 5)\end{equation} \begin{equation}\label{eq26} V(n - V(n - 1)) = V(n - 1 - V(n - 2)) + 1\end{equation} We now show that under all of the above assumptions we must have $V(n - V(n - 4)) = V(n - 1 - V(n - 5))$, from which it follows by \eqref{eq23} that $V(n) - V(n-1) = 1$ and \eqref{thm21} holds for $n$. By the induction hypothesis for \eqref{eq22} $V(n - 1) - V(n - 4)\in \{1, 2\}$. But $V(n - 1) = V(n - 2)$ so $V(n - 2) - V(n - 4) \in \{1, 2\}$. We have to consider two cases, namely, $V(n - 2) = V(n - 4) + 2$ and $V(n - 2) = V(n - 4) + 1$. Case 1: $V(n - 2) = V(n - 4) + 2$. This together with \eqref{eq24} means that \eqref{eq26} becomes \begin{equation}\label{eq27} V(n - 2 - V(n - 4)) = V(n - 3 - V(n - 4)) + 1. \end{equation} Since $V(n - 2) = V(n - 4) + 2$ we must have $V(n - 2) = V(n - 3) + 1$ and $V(n - 3) = V(n - 4) + 1$. But by the definition of the $V$ function $V(n - 2) = V(n - 3) + 1$ is equivalent to $V(n - 2 - V(n - 3)) + V(n - 2 - V(n - 6)) = V(n - 3 - V(n - 4)) + V(n - 3 - V(n - 7)) + 1$. Since $V(n - 3) = V(n - 4) + 1$, $V(n - 2 - V(n - 3)) = V(n - 2 - (V(n - 4) + 1)) = V(n - 3 - V(n - 4))$. Therefore \begin{equation}\label{eq28} V(n - 2 - V(n - 6)) = V(n - 3 - V(n - 7)) + 1. \end{equation} Consequently we must have $V(n - 6) = V(n - 7)$. But then since $V(n - 6) = V(n - 7)$ and $V(n - 4) = V(n - 5)$ (by \eqref{eq25}), we can use the induction hypothesis for \eqref{eq22} to conclude that $V(n - 5) = V(n - 6) + 1$. Considering the last equation and the fact that $V(n - 4) = V(n - 5)$ (by \eqref{eq25} again), equation \eqref{eq28} can be rewritten as: \begin{equation}\label{eq29} V(n - 1 - V(n - 4)) = V(n - 2 - V(n - 4)) + 1. \end{equation} From \eqref{eq27} and \eqref{eq29} we conclude that $V(n - 1 - V(n - 4)) - V(n - 3 - V(n - 4)) = 2$. But the induction hypothesis for \eqref{eq22} implies $V(n - V(n - 4)) - V(n - 3 - V(n - 4))\in \{1, 2\}$. Therefore, by \eqref{eq25} and the induction assumption on \eqref{eq21} we have $V(n - V(n - 4)) = V(n - 1 - V(n - 4)) = V(n - 1 - V(n - 5))$. This completes the proof of Case 1. Case 2: $V(n - 2) = V(n - 4) + 1$. By \eqref{eq24} and the definition of $V(n)$ we can rewrite this as: \begin{eqnarray}\label{eq210} &&V(n - 1 - V(n - 2)) + V(n - 1 - V(n - 5))\\ &&=V(n - 4 - V(n - 5)) + V(n - 4 - V(n - 8)) + 1.\nonumber \end{eqnarray} But \eqref{eq24} and \eqref{eq25} also imply that $V(n - 1) = V(n - 2) = V(n - 5) + 1$. Rewrite \eqref{eq26} as \begin{equation}\label{eq211} V(n - 1- V(n - 5)) = V(n - 2 - V(n - 5)) + 1. \end{equation} Substituting \eqref{eq211} into \eqref{eq210} we get \begin{eqnarray}\label{eq212} &&V(n - 1 - V(n - 2)) + V(n - 2 - V(n - 5))\\ &&=V(n - 4 - V(n - 5)) + V(n - 4 - V(n - 8)).\nonumber \end{eqnarray} Equivalently: \begin{eqnarray}\label{eq213} &&V(n - 2 - V(n - 5)) - V(n - 4 - V(n - 8))\\ &&=V(n - 4 - V(n - 5)) - V(n - 2 - V(n - 5)).\nonumber \end{eqnarray} But by the induction assumption for \eqref{eq22} we have $V(n - 5) - V(n - 8)\in \{1, 2\}$. Thus $V(n - 2 - V(n - 5)) -V(n - 4 - V(n - 8))\geq 0$. At the same time, the induction assumption for \eqref{eq21} means that $V(n - 4 - V(n - 5)) - V(n - 2 - V(n - 5))\leq 0$. Hence both sides of\eqref{eq213} equal 0. \begin{equation}\label{eq214} V(n - 2 - V(n - 5)) - V(n - 4 - V(n - 5)) = 0. \end{equation} But \eqref{eq214} and the induction hypotheses \eqref{eq21} and \eqref{eq22} imply \begin{equation}\label{eq215} V(n - 4 - V(n - 5)) - V(n - 5 - V(n - 5)) = 1. \end{equation} Let $k = n - V(n - 5)$. Then by \eqref{eq3} \begin{eqnarray}\label{eq216} V(k) - V(k - 1) &=& V(k - V(k - 1)) + V(k - V(k - 4))\\ &&- V(k - 1 - V(k - 2)) - V(k - 1 - V(k - 5)).\nonumber \end{eqnarray} Equation \eqref{eq211} is equivalent to $V(k - 1) = V(k - 2) + 1$ and equation \eqref{eq215} implies that $V(k - 4) = V(k - 5) + 1$. Substituting these equalities into \eqref{eq216} we get that $V(k) - V(k - 1) = 0$, as desired. Thus, \eqref{eq21} holds for $n$ in Case 2 so the proof of \eqref{eq21} is complete. We complete the induction by showing that \eqref{eq22} also holds for $n$. Observe the identity \begin{equation}\label{eq217} V(n) - V(n - 3) = (V(n) - V(n - 1)) + (V(n - 1) - V(n - 3)). \end{equation} From what we have just proved, $V(n) - V(n - 1)$ is 0 or 1. Clearly $V(n - 1) - V(n - 3)$ $\in$ \{0, 1, 2\} by the induction assumption for \eqref{eq21}. We consider three cases. Case 1: $V(n - 1) - V(n - 3) = 1$. Then $V(n) - V(n - 3)$ is 1 or 2, by \eqref{eq217} and the fact that $V(n) - V(n - 1)$ is 0 or 1. Case 2: $V(n - 1) - V(n - 3) = 2$. We show that $V(n) = V(n - 1)$. Write $V(n - 1) - V(n - 3) = (V(n - 1) - V(n - 2)) + (V(n - 2) - V(n - 3))$. By the induction hypothesis for \eqref{eq21} each of the differences on the right-hand side is either 0 or 1. Thus $V(n - 1) = V(n - 3) + 2$ implies that $V(n - 1) = V(n - 2) + 1$ and $V(n - 2) = V(n - 3) + 1$. But by the induction hypothesis on \eqref{eq22} we have $V(n - 1) - V(n - 4) \in \{1, 2\}$, so $V(n - 4) = V(n - 3)$. Using the above relationships together with \eqref{eq3} we have \begin{eqnarray*} 1&=&V(n - 1) - V(n - 2)\\ &=&V(n - 1 - V(n - 2)) + V(n - 1 - V(n - 5))-V(n - 2 - V(n - 3)) \\ &&- V(n - 2 - V(n - 6))\\ &=&V(n - 1 - V(n - 5)) - V(n - 2 - V(n - 6)). \end{eqnarray*} Therefore $V(n - 5) = V(n - 6)$. Since $V(n - 4) = V(n - 3)$ the induction assumption on \eqref{eq21} and \eqref{eq22} implies that $V(n - 4) = V(n - 5) + 1$. Again, by \eqref{eq3}, \begin{eqnarray*} V(n) - V(n - 1)&=&V(n - V(n - 1)) + V(n - V(n - 4))\\ &&-V(n - 1 - V(n - 2)) - V(n - 1 - V(n - 5)) \end{eqnarray*} Substituting $V(n - 1) = V(n - 2) + 1$ and $V(n - 4) = V(n - 5) + 1$ into the above equation we get the desired result $V(n) - V(n - 1) = 0$. Case 3: $V(n - 1) - V(n - 3) = 0$. We show that $V(n) = V(n - 1) + 1$, which together with \eqref{eq217} completes this case and the proof of \eqref{eq22}. By \eqref{eq3} we have \begin{eqnarray}\label{eq218} V(n) - V(n - 3) &=& V(n - V(n - 1)) + V(n - V(n - 4))\\ &&- V(n - 3 - V(n - 4)) - V(n - 3 - V(n - 7)).\nonumber \end{eqnarray} Since $V(n - 1) - V(n - 3) = 0$ by the induction hypothesis on \eqref{eq22} we must have $V(n - 3) - V(n - 4) = 1$. Using these two relations we rewrite \eqref{eq218} as \begin{eqnarray*} V(n) - V(n - 3) &=& V(n - 1 - V(n - 4)) + V(n - V(n - 4))\\ &&- V(n - 3 - V(n - 4)) - V(n - 3 - V(n - 7)). \end{eqnarray*} By the induction hypothesis for \eqref{eq22} we have that $V(n - V(n - 4)) - V(n - 3 - V(n - 4))\in \{1, 2\}$, while $V(n - V(n - 1)) = V(n - V(n - 3)) = V(n - 1 - V(n - 4))\geq V(n - 3 - V(n - 7))$. (To see the last inequality, observe that by the induction on \eqref{eq22} we have $V(n - 4) - V(n - 7)\in \{1, 2\}$. Thus, either $V(n - 1 - V(n - 4)) = V(n - 2 - V(n - 7))$, in which case we know the inequality by monotonicity, or $V(n - 1 - V(n - 4)) = V(n - 3 - V(n - 7))$, in which case the two terms are identical and the difference is 0.) Thus $V(n) - V(n - 3)> 0$, and therefore we must have $V(n) - V(n - 1) = 1$. This completes Case 3, the proof of \eqref{eq22} and the overall induction. \end{proof} We now prove several relationships between the mother and father spots. These simple results provide some essential tools for establishing our main findings in the following section. \begin{corollary}\label{col22} Suppose the mother spot of $V(n)$ is $m$ and the father spot of $V(n)$ is $f$. Then: \begin{enumerate} \item[(i)] the mother spot of $V(n + 1)$ is $m$ if $V(n) = V(n - 1) + 1$ and $m + 1$ otherwise; \item[(ii)] the father spot of $V(n + 1)$ is $f$ if $V(n - 3) = V(n - 4) + 1$ and $f + 1$ otherwise. \end{enumerate} \end{corollary} \begin{proof} Recall from the proof of Theorem \ref{thm21} that the difference in the mother (respectively, father) spots for the two consecutive indices $n$ and $n + 1$ is $1 - (V(n) - V(n - 1))$ and $(1 - (V(n - 3) - V(n - 4)))$ . The corollary now follows immediately from the results of Theorem \ref{thm21}. \end{proof} Remark: It follows immediately from Corollary \ref{col22} and Theorem \ref{thm21} that there is a natural definition for the sequences of the mother spot and the father spot, respectively, and for the mother and father sequences. All these sequences are monotonic increasing, and have successive differences that are either 0 or 1. \begin{corollary}\label{col24} Suppose that the mother spot of $V(n)$ is m. Then the father spot of $V(n)$ is $m + 1$ if $V(n - 1) = V(n - 4) + 1$ and $m + 2$ if $V(n - 1) = V(n - 4) + 2$. \end{corollary} \begin{proof} The proof is analogous to the preceding result. By definition, the mother and father spots of $V(n)$ are $n - V(n - 1)$ and $n - V(n - 4)$ respectively. If $V(n - 1) = V(n - 4) + 1$ then father spot of $V(n)$ is $n - V(n - 4) = n - (V(n - 1) - 1) = n + 1 - V(n - 1) = m + 1$. By Theorem \ref{thm21} the only other possible situation is $V(n - 1) = V(n - 4) + 2$, in which case the father spot of $V(n)$ is $n - V(n - 4) = n - (V(n - 1) - 2) = n + 2 - V(n - 1) = m + 2$. \end{proof} \begin{corollary}\label{col25} The father and mother of $V(n)$ differ by $0$, $1$ or $2$. More precisely, $V(n - V(n - 4)) - V(n - V(n - 1))\in \{0, 1, 2\}$. \end{corollary} \begin{proof} By Corollary \ref{col24} the father spot $f$ and mother spot $m$ differ by 1 or 2. If $f = m + 1$, then $V(f) - V(m)\in \{0, 1\}$, while if $f = m + 2$, then $V(f) - V(m) = (V(f) - V(f - 1)) + (V(f - 1) - V(m)) \in \{0, 1, 2\}$. \end{proof} We conclude this section with an estimate for the size of $V(n)$. \begin{proposition}\label{pps26} For all $n > 6$, we have $\displaystyle\frac{n}{2}< V(n) \leq \displaystyle\frac{n}{2} + \log_2 n - 1$. \end{proposition} \begin{proof} We prove both these bounds by induction. We start with the lower bound. The base case is evident from Table~\ref{tab13} for many small values of $n > 6$. Assume it holds up to $K > 6$. For $K + 1$ we have the following inequalities: $V(K + 1)\geq 2V(K + 1 - V(K))$ (by Theorem \ref{thm21}) $> K + 1 - V(K)$ (by the induction assumption) $\geq K + 1 - V(K + 1)$ (by Theorem \ref{thm21}). The required result now follows. For the upper bound, we proceed as follows. Let $V(n) = a$, where $a > 1$. Note that $a < n$. We show an even stronger result, namely, $V(n) = a\leq\displaystyle\frac{n}{2} - 1 +\log_2 (a)$. From Table~\ref{tab13} we readily verify that this inequality holds for $2 \leq a \leq 4$. Assume it holds for all $a \leq A - 1$, where $A \geq 5$, and let $V(n) = A$. Then $A = V(n) = V(n - V(n - 1)) + V(n - V(n - 4))$. Applying the induction hypothesis to the terms on the right-hand side we get \begin{eqnarray*} V(n) &\leq& (n - V(n - 1))/2 + \log_2(V(n - V(n - 1)) + (n - V(n - 4))/2 +\log_2 (V(n - V(n - 4)) - 2 \\ &\leq& (n - V(n - 1))/2 + (n - V(n - 4))/2 +\log_2(V(n - V(n - 1))(V(n - V(n - 4)))) - 2. \end{eqnarray*} By Theorem \ref{thm21} $V(n) - V(n - 1)\leq 1$ and $V(n) - V(n - 4) = V(n) - V(n - 1) + V(n - 1) - V(n - 4)\leq 1 + 2 = 3$. Thus $V(n - 1)\geq V(n) - 1$ and $V(n - 4)\geq V(n) - 3$. Let $V(n - V(n - 1)) = B$ and $V(n - V(n - 4)) = C$. Then $A = B + C$. It follows that $B \cdot C\leq\displaystyle(\frac{A}{2})^2$. That is, $V(n - V(n - 1)) \cdot V(n - V(n - 4))\leq (\displaystyle\frac{A^2}{4})$. Substituting these bounds in the last of the above inequalities, we get $$V(n)\leq\displaystyle\frac{n - V(n) + 1}{2} + \frac{n - V(n) + 3}{2} + \log_2(\displaystyle\frac{A^2}{4}) - 2.$$ Rearranging the terms we get $2V(n)\leq n + 2\log_2 A - 2$. Since $A < n$ we conclude that $V(n)\leq\displaystyle\frac{n}{2} +\log_2 n - 1$, as desired. \end{proof} Since $V(n)$ is an integer the following corollary is immediate. \begin{corollary}\label{col27} For all $n > 6$, $\displaystyle\lceil \frac{n}{2} \rceil \leq V(n) \leq \lfloor \frac{n}{2} + \log_2 n - 1 \rfloor$. Further, $\displaystyle \lim_{n \to \infty}{\frac{V(n)}{n}} = \frac{1}{2}$. \end{corollary} We have found empirically that the midpoint $P(n)$ of the interval defined by the bounds in Corollary \ref{col27} provides a very good estimate for the value of $V(n)$. We empirically determined the error \begin{equation} E(I(k))=\displaystyle\max_{n \in I(k)}\{\frac{100\left|V(n)-P(n)\right|}{P(n)}\} \end{equation} for intervals $I(k)=\{2^{k},\ldots,2^{k+1}-1\}$ for $k=0$ to $k=20$. We find that $E(I(k)) < 1$ for $k > 6$.For $k > 14$ error $E(I(k+1))$ is approximately half of $E(I(k))$. For example, for $k=17$,$18$,$19$ and $20$, $E(I(k))$ is $0.005294$, $0.002667$, $0.001512$ and $0.0007621$ respectively. \section{Frequency Sequence Properties}\label{sec3} The behavior of $V(n)$ is completely determined by the frequency with which it hits each positive integer.\footnote{See, for example, \cite{ktv, tsm}, where this approach is used for the Conway and Conolly meta-Fibonacci sequences.} For any positive integer $a$, let $F(a)$ (the ``\emph{frequency}'' of $a$) denote the number of occurrences of $a$ in the sequence $V(n)$. By Theorem \ref{thm21}, for $a > 1$, we have $1 \leq F(a) \leq 3$. Table~\ref{tab31} shows the first 200 values of the frequency sequence. \begin{table}[!ht] \fontsize{6}{6}\selectfont \caption{First 200 values of frequency sequence $F(a)$ of $V(n)$}\label{tab31} \center{ \begin{tabular}{l r r r r r l r r r r r} \hline {}&{}&{}&$a$&{}&{}&{}&{}&{}&$a$&{}&{}\\ \cline{2-6}\cline{8-12} {}&1&2&3&4&5&{}&1&2&3&4&5\\ \hline $F(a+0)$&4&1&1&1&2&$F(a+100)$&2&3&2&1&3\\ $F(a+5)$&2&1&2&2&1&$F(a+105)$&2&1&2&2&1\\ $F(a+10)$&3&2&1&2&2&$F(a+110)$&3&2&2&1&3\\ $F(a+15)$&1&3&2&1&2&$F(a+115)$&3&2&1&2&2\\ $F(a+20)$&2&3&2&1&2&$F(a+120)$&2&1&3&2&2\\ $F(a+25)$&2&2&1&3&2&$F(a+125)$&1&2&2&2&3\\ $F(a+30)$&1&2&2&3&2&$F(a+130)$&2&1&3&2&2\\ $F(a+35)$&1&2&2&2&1&$F(a+135)$&3&2&1&2&2\\ $F(a+40)$&3&2&2&3&2&$F(a+140)$&2&1&3&2&2\\ $F(a+45)$&1&2&2&2&1&$F(a+145)$&1&2&2&2&3\\ $F(a+50)$&3&2&2&1&2&$F(a+150)$&2&1&3&2&1\\ $F(a+55)$&2&2&3&2&1&$F(a+155)$&2&2&1&3&2\\ $F(a+60)$&2&2&2&1&3&$F(a+160)$&2&1&3&3&2\\ $F(a+65)$&2&2&3&2&1&$F(a+165)$&1&2&2&2&3\\ $F(a+70)$&2&2&2&1&3&$F(a+170)$&2&1&3&2&2\\ $F(a+75)$&2&2&1&2&2&$F(a+175)$&3&2&1&2&2\\ $F(a+80)$&2&3&2&1&3&$F(a+180)$&2&1&3&2&2\\ $F(a+85)$&2&2&3&2&1&$F(a+185)$&1&2&2&2&3\\ $F(a+90)$&2&2&2&1&3&$F(a+190)$&2&1&3&2&1\\ $F(a+95)$&2&2&1&2&2&$F(a+195)$&2&2&1&3&2\\ \hline \end{tabular} } \end{table} The frequency sequence exhibits many interesting ``local'' properties (see Lemmas \ref{lem33}-\ref{lem36} below). For example, no two consecutive 1s appear, and there are never more than three consecutive 2s. The pair 12 is always followed by a 2. No more than two consecutive 3s occur, and indeed, such occurrences of consecutive 3s in the frequency sequence are relatively rare. The frequency sequence also exhibits the following ``remote'' characteristic: for any positive integer $a$ the frequencies with which $2a$ and $2a + 1$ occur depend upon the frequency of $a$ in certain cases, and of $a$ and some of its neighbors ($a - 2$, $a - 1$, and $a + 1$) in others (see Lemmas \ref{lem37}-\ref{lem313}). We refer to this as the ``\emph{index doubling}'' property. The index doubling results, which are summarized in Table~\ref{tab32}, are key to proving a set of three rules first observed by Gutman \cite{gk} for generating the frequency sequence of $V(n)$ recursively. We conclude this section by describing some additional properties of the frequency sequence that follow from Table~\ref{tab32}. The following assertions are all for $a \geq 6$ and for $n \geq 21$. We begin with two technical results on the size of the mother and father values for even and odd values of the $V$-sequence. \begin{lemma}\label{lem31} Suppose that for some positive integer a $V(n) = 2a$. Then: \begin{enumerate} \item[(i)] the mother and father are both equal to $a$, which occurs if and only if $F(a) > 1$; \item[(ii)] the mother is equal to $a - 1$ and the father is equal to $a + 1$, which occurs if and only if $F(a) = 1$. \end{enumerate} \end{lemma} \begin{proof} By Corollary \ref{col25} the father and mother of $V(n)$ differ by 0, 1 or 2. Since $V(n) = 2a$ the mother and father cannot differ by 1. Thus either both the mother and father are equal to $a$, or they differ by 2, so that the mother is equal to $a - 1$ and father is equal to $a + 1$. By Corollary \ref{col24} the mother and father spots always differ by 1 or 2. It follows that if both the mother and father of $n$ are equal to $a$, then $F(a) > 1$. Conversely, suppose $F(a) > 1$. By Corollary \ref{col24} the difference between the father spot and the mother spot is at most 2. Since $F(a) > 1$ it follows (since the $V$-sequence is monotonic with successive differences either 0 or 1) that the mother and father can differ by at most 1. But we have already observed that when $V(n) = 2a$ the mother and father cannot differ by 1. Thus the mother and father of $V(n)$ are both equal to $a$. This proves \emph{(i)}. In the second case, if the mother is equal to $a - 1$ and the father is equal to $a + 1$, then $F(a) = 1$, since otherwise the difference between the mother and father spots must be greater than 2 which is impossible by Corollary \ref{col24}. Conversely suppose $F(a) = 1$. Then both the mother and father cannot be equal to $a$ since by Corollary \ref{col24} the mother spot and father spot differ by 1 or 2. It follows that the mother and father equal $a - 1$ and $a + 1$ respectively. \end{proof} \begin{lemma}\label{lem32} If $V(n) = 2a + 1$ for some positive integer $a$, then mother and father are respectively $a$ and $a + 1$. \end{lemma} \begin{proof} By Corollary \ref{col25} the mother and father differ by 0, 1 or 2. If their difference is 0 or 2 then their sum is an even number. So their difference must be 1. Thus the mother and father are $a$ and $a + 1$, respectively. \end{proof} We now prove some local properties of the $V$-sequence. \begin{lemma}\label{lem33} Suppose $F(a) = 1$. Then $F(a + 1) > 1$. \end{lemma} \begin{proof} Let $m$ be the maximum of \{$i$ : $V$($i$) = $a - 1$\} and suppose $F(a + 1) = 1$. Then $V(m + 1) = a$, $V(m + 2) = a + 1$ and $V(m + 3) = a + 2$. So $V(m + 3) - V(m) = 3$. This contradicts Theorem \ref{thm21}. Therefore $F(a + 1) > 1$. \end{proof} An immediate consequence of Lemma \ref{lem33}, first observed by Huber \cite{hhg}, is that $V(n)$ does not have a string of four consecutive strictly increasing terms. \begin{lemma}\label{lem34} Suppose $F(a) = 1$. Then $F(a + 2) > 1$ and $F(a - 1) = 2$. \end{lemma} \begin{proof} Let $n$ be the unique index such that $V(n) = a$. Applying Lemma \ref{lem33} (twice) and Theorem \ref{thm21} we deduce that there are the following two possibilities: \begin{enumerate} \item[(i)] $V(n - 2) = V(n - 1) = a - 1$, $V(n) = a$, $V(n + 1) = a + 1$, $V(n + 2) = a + 1$, $V(n + 3) = a + 2$; \item[(ii)] $V(n - 2) = V(n - 1) = a - 1$, $V(n) = a$, $V(n + 1) = a + 1$, $V(n + 2) = a + 1$, $V(n + 3) = a + 1$, $V(n + 4) = a + 2$. \end{enumerate} In case (i), since $V(n + 3) = V(n + 2) + 1$ and $V(n) = V(n - 1) + 1$, $V(n + 4) = V(n + 4 - V(n + 3)) + V(n + 4 - V(n)) = V(n + 3 - V(n + 2)) + V(n + 3 -V(n - 1)) = V(n + 3) = a + 2$. Thus, $F(a + 2) > 1$, as required. Now, by the definition of the V-sequence, $V(n + 1) = V(n) + 1$ is equivalent to $V(n + 1 - V(n)) + V(n + 1 - V(n - 3)) = V(n - V(n - 1)) + V(n - V(n - 4)) + 1$. Since $V(n) = V(n - 1) + 1$ we have $V(n + 1 - V(n)) = V(n - V(n - 1))$. Hence \begin{equation}\label{eq31} V(n + 1 - V(n - 3)) = V(n - V(n - 4)) + 1. \end{equation} Since successive terms of the $V$-sequence differ by 0 or 1 this means that $V(n - 3) = V(n - 4)$. But $V(n - 1) = V(n - 2) = a - 1$ and since the frequency is always less than 4, Theorem \ref{thm21} implies that $V(n - 2) = V(n - 3) + 1$. Thus, $F(a - 1) = 2$. In case (ii), since $V(n + 4) = V(n + 3) + 1$ and $V(n + 1) = V(n) + 1, V(n + 5) = V(n + 5 - V(n + 4)) + V(n + 5 - V(n + 1)) = V(n + 4 -V(n + 3)) + V(n + 4 -V(n)) = V(n + 4) = a + 2$. Once again, $F(a + 2) > 1$. The proof that $F(a - 1) = 2$ in this case is identical to case (i). \end{proof} \begin{lemma}\label{lem35} If $F(a) = 1$ and $F(a + 1) = 2$ then $F(a + 2) = 2$. \end{lemma} \begin{proof} The setup is the same as case (i) in Lemma \ref{lem34}, with the additional condition $V(n + 4) = a + 2$, which follows from Lemma \ref{lem34}. Thus $V(n - 3) = V(n - 4) = V(n + 3) - 4 = V(n + 4) - 4$. We use these last equations to rewrite \eqref{eq31} as follows: \begin{equation}\label{eq32} V(n + 5 - V(n + 4)) = V(n + 4 - V(n + 3)) + 1 \end{equation} But \eqref{eq32} is precisely the difference between mothers of $V(n + 5)$ and $V(n + 4)$. Hence $V(n + 5) = V(n + 4) + 1$ and $F(a + 2) = 2$. \end{proof} \begin{lemma}\label{lem36} \item[(i)] If $F(a) = F(a + 1) = F(a + 2) = 2$ then $F(a + 3) \neq 2$. \item[(ii)]If $F(a - 1) = F(a - 2) = 3$, then $F(a) = 2$. \end{lemma} \begin{proof} \emph{(i)} Let $n$ be the minimum of $\{i : V(i) = a + 3\}$. From the given frequencies we have $V(n - 1) = V(n - 2) = a + 2$, $V(n - 3) = V(n - 4) = a + 1$, and $V(n - 5) = V(n - 6) = a$. Assume that $F(a + 3) = 2$. Then $V(n) = V(n + 1) = a + 3$ and $V(n + 2) - V(n + 1) = 1$. We show that this leads to a contradiction. Let $m$ be the mother spot of $V(n)$. As in the preceding proofs we apply Corollaries \ref{col22} and \ref{col24} to deduce each of the following in turn: \begin{eqnarray*} &&V(n) = V(m) + V(m + 1)\\ &&V(n + 1) = V(m) + V(m + 2)\\ &&V(n + 2) = V(m + 1) +V(m + 2)\\ &&V(n - 1) = V(m - 1) +V(m + 1)\\ &&V(n - 2) = V(m - 1) +V(m) \end{eqnarray*} From the above relations we have $V(n + 2) - V(n + 1) = V(m + 1) - V(m) = V(n - 1) - V(n - 2) = 0$, a contradiction. Thus $F(a + 3) \neq 2$. \emph{(ii)} Let $n$ be the minimum of \{$i$ : $V(i) = a$\}. Then $V(n - 1) = V(n - 2) = V(n - 3) = a - 1$ and $V(n - 4) = V(n - 5) = V(n - 6) = a - 2$. By definition, $V(n + 1) - V(n) = V(n + 1 - V(n)) + V(n + 1 - V(n - 3)) - V(n - V(n - 1)) - V(n - V(n - 4))$. But since $V(n) = V(n - 1) + 1$ and $V(n - 3) = V(n - 4) + 1$ it follows that $V(n + 1) = V(n)$. Similarly we have $V(n + 2) - V(n + 1) = V(n + 2 - V(n + 1)) + V(n + 2 - V(n - 2)) - V(n + 1 - V(n)) - V(n + 1 - V(n - 3))$. But $V(n + 1) = V(n) = V(n - 3) + 1$ so the first and last terms of this expression cancel and we are left with $V(n + 2) - V(n + 1) = V(n + 2 - V(n - 2)) - V(n + 1 - V(n))$. Further, since $V(n) = V(n - 2) + 1$ we also have that $V(n + 2) - V(n + 1) = V(n + 3 - V(n)) - V(n + 1 - V(n))$. In the same way, using \eqref{eq3} and the fact that $V(n - 2) = V(n - 6) + 1$, we derive that $V(n - 1) - V(n - 2) = V(n - 1 - V(n - 5)) - V(n - 2 - V(n - 3))$. But $V(n - 1) = V(n - 2)$ so $V(n - 1 - V(n - 5)) = V(n - 2 - V(n - 3))$. But since $V(n - 5) = V(n - 3) - 1 = V(n) - 2$ this means that $V(n + 1 - V(n)) = V(n - 1 - V(n))$. Thus we have $V(n + 2) - V(n + 1) = V(n + 3 - V(n)) - V(n + 1 - V(n)) = V(n + 3 - V(n)) - V(n - 1 - V(n)) > 0$, since the indices of these two terms differ by 4. Thus, $V(n + 2) > V(n + 1)$ and $F(a)=2$. \end{proof} Lemma \ref{lem36} completes our focus on the local properties of the frequency sequence. We now show how the frequency of $a$ and some of its neighbors determine the frequency of $2a$ and $2a + 1$. Once this is done, we have an implicit algorithm to determine any value in the frequency sequence, and hence we understand precisely the behavior of the original $V$-sequence. \begin{lemma}\label{lem37} If $F(a) = 1$ then $F(2a) = F(2a + 1) = 2$. \end{lemma} \begin{proof} Let $n$ be the minimum of $\{i : V(i) = 2a\}$ and $m$ be the unique index such that $V(m) = a$. By Lemma \ref{lem31}, together with the fact that the $V$-sequence is monotonic with successive differences either 0 or 1, it follows that $V(n) = V(m - 1) + V(m + 1)$. By the definition of $n$, we have $V(n) = V(n - 1) + 1$. By definition, the mother spot of $V(n)$ is $m - 1$, so by Corollary \ref{col22} the mother spot of $V(n + 1)$ is also $m - 1$. Since the father spot of $V(n)$ is $m + 1$, it follows from Corollary \ref{col22} that the father spot of $V(n + 1)$ is either $m + 1$ or $m + 2$. But by Corollary \ref{col24}, the father spot must be $m + 1$ since the mother and father spot differ by at most 2. Thus, $V(n + 1) = V(n) = 2a$, so $F(2a)$ is at least 2. Again, by Corollary \ref{col22} the mother spot of $V(n + 2)$ must be $m$. By Corollary \ref{col24} we must have $V(n + 2) = V(m) + V(m + 1)$ or $V(n + 2) = V(m) + V(m + 2)$. Hence $V(n + 2) = 2a + 1$ since by Lemma \ref{lem33} $V(m + 1) = V(m + 2) = a + 1$. Thus $F(2a) = 2$. The argument to show that $F(2a + 1) = 2$ is similar. By Corollary \ref{col22} the mother spot of $V(n + 3)$ is $m$. Hence $V(n + 3) = V(m) + V(m + 1)$ or $V(n + 3) = V(m) + V(m + 2)$. Since $V(m + 1) = V(m + 2)$ we have $V(n + 3) = V(n + 2) = 2a + 1$ and $F(2a + 1)$ is at least 2. Once again by Corollary \ref{col22} the mother spot of $V(n + 4)$ is $m + 1$. But $V(m + 1) = V(m) + 1$, thus $V(n + 4) > V(n + 3)$ and so $F(2a + 1) = 2$ as desired. \end{proof} \begin{lemma}\label{lem38} If $F(a) = 3$ then $F(2a) = 3$ and $F(2a + 1) = 2$. \end{lemma} \begin{proof} Let $n$, $m$ be the minimum of $\{ i : V(i) = 2a\}$ and $\{j : V(j) = a\}$ respectively. Since $F(a) > 1$, by Lemma \ref{lem31} we must have that both the mother and father of $V(n)$ are equal to $a$. Since $F(a) = 3$ then by Corollary \ref{col24} we know that either $V(n) = V(m) + V(m + 1)$ or $V(n) = V(m) + V(m + 2)$. By Corollary \ref{col22} the mother spot of $V(n + 1)$ is $m$. Thus $V(n + 1) = V(m) + V(m + 1)$ or $V(n + 1) = V(m) + V(m + 2)$. Hence $V(n + 1) = V(n) = 2a$ since $F(a) = 3$. Similarly, by Corollary \ref{col22}, the mother spot of $V(n + 2)$ is $m + 1$. Thus $V(n + 2) = V(m + 1) + V(m + 2)$ or $V(n + 2) = V(m + 1) + V(m + 3)$. If $V(n + 2) = V(m + 1) + V(m + 2)$ then $V(n + 2) = 2a$. If $V(n + 2) = V(m + 1) + V(m + 3)$ then the father spot of $V(n + 2)$ is two more than the mother spot. That is, $(n + 2 - V(n - 2)) = (n + 2 - V(n + 1)) + 2$. This is equivalent to $V(n - 2) = V(n + 1) - 2 = 2a - 2$. Now $V(n - 1) \geq 2 V(n - 1 - V(n - 2))$ as the mother is always less than or equal to the father. That is, $V(n - 1) \geq 2 V(n - 1 - (2a - 2)) = 2V(n + 1 - 2a)$. But $n + 1 - 2a$ is the mother spot of $V(n + 1)$, so we have $V(n - 1) \geq 2 V(m) = 2a$. But this contradicts the definition of $n$ as the minimum of \{$i$ : $V(i) = 2a$\}. Thus $V(n + 2) = V(m + 1) + V(m + 2) = 2a$, and $F(2a) = 3$. By Corollaries \ref{col22} and \ref{col24}, we can compute the following values: \begin{eqnarray*} &&V(n + 3) = V(m + 2) + V(m + 3) = 2a + 1\\ &&V(n + 4) = V(m + 2) + V(m + 3) = 2a + 1\\ &&V(n + 5) = V(m + 3) + V(m + 4) \geq 2V(m + 3) = 2a + 2 \end{eqnarray*} This shows that $F(2a + 1) = 2$, and completes the proof. \end{proof} \begin{lemma}\label{lem39} If $F(a - 1) = 1$ and $F(a) = 2$ then $F(2a) = 1$ and $F(2a + 1) = 3$. \end{lemma} \begin{proof} Let $n$, $m$ be the minimum of $\{i: V(i) = 2a\}$ and $\{j : V(j) = a\}$ respectively. Since $F(a - 1) = 1$, by Lemma \ref{lem37} $F(2a - 2) = F(2a - 1) = 2$. By the definition of $n$ this implies that $V(n - 1) = V(n - 2) = 2a - 1$ and $V(n - 3) = V(n - 4) = 2a - 2$. Since $F(a) = 2$, $V(m) = V(m + 1) = a$. Since $V(n) = 2a$ it follows by Corollary \ref{col24} and Lemma \ref{lem31} that $V(n) = V(m) + V(m + 1)$. Then by Corollary \ref{col22} the mother spot of $V(n + 1)$ is $m$. By Corollary \ref{col24}, the father spot of $V(n + 1)$ is $m + 2$, since $V(n) - V(n - 3) = 2a - (2a - 2) = 2$. But $F(a) = 2$ so $V(m + 2) = a + 1$. Thus $V(n + 1) = V(m) + V(m + 2) = 2a + 1$ so $F(2a) = 1$. In a similar way, we can show that $V(n + 2) = V(m) + V(m + 2) = 2a + 1$ and $V(n + 3) = V(m + 1) + V(m + 3) = 2a + 1$, so $F(2a + 1) = 3$. \end{proof} \begin{lemma}\label{lem310} If $F(a - 1) = 3$, $F(a) = 2$ and $F(a + 1) = 3$ or $2$ then $F(2a) = 1$ and $F(2a + 1) = 3$. \end{lemma} \begin{proof} Let $n$, $m$ be the minimum of $\{i: V(i) = 2a\}$ and $\{j : V(j) = a\}$ respectively. By Lemma \ref{lem38}, $V(n - 1) = V(n - 2) = 2a - 1$, and $V(n - 3) = V(n - 4) = V(n - 5) = 2a - 2$. By the now familiar argument, since $F(a) > 1$, we deduce using Lemma \ref{lem31} that $V(n) = V(m) + V(m + 1) = 2a$. Then by Corollary \ref{col22} we conclude that $V(n + 1) = V(m) + V(m + 2) = 2a + 1$. Similarly $V(n + 2) = V(m) + V(m + 2) = 2a + 1$ and $V(n + 3) = V(m + 1) + V(m + 3) = 2a + 1$. \end{proof} \begin{lemma}\label{lem311} If $F(a - 1) = 3$, $F(a) = 2$ and $F(a + 1) = 1$ then $F(2a) = 1$ and $F(2a + 1) = 2$. \end{lemma} \begin{proof} Let $n$, $m$ be the minimum of $\{i: V(i) = 2a\}$ and $\{j: V(j) = a\}$ respectively. Since $F(a-1) = 3$ Lemma \ref{lem38}, together with the definition of $n$, implies that $V(n - 1) = V(n - 2) = 2a - 1$ and $V(n - 3) = V(n - 4) = V(n - 5) = 2a - 2$. Then by Lemma \ref{lem31}, $V(n) = V(m) + V(m + 1) = 2a$. Once again we conclude the proof by invoking Corollary \ref{col22} to deduce the following relations: \begin{eqnarray*} &&V(n + 1) = V(m) + V(m + 2) = 2a + 1\\ &&V(n + 2) = V(m) + V(m + 2) = 2a + 1\\ &&V(n + 3) = V(m + 1) + V(m + 3) = 2a + 2 \end{eqnarray*} \end{proof} \begin{lemma}\label{lem312} If $F(a - 2) \neq 2$, and $F(a - 1) = F(a) = 2$ then $F(2a) = 2$. Moreover, if $F(a + 1) = 1$ then $F(2a + 1) = 1$; otherwise $F(2a + 1) = 2$. \end{lemma} \begin{proof} Let $n$, $m$ be the minimum of $\{i : V(i) = 2a\}$ and $\{j : V(j) = a\}$ respectively. By the given conditions on the frequencies of $a - 2$, $a - 1$ and $a$, we can apply Lemmas \ref{lem39} and \ref{lem310} to deduce that $F(2a - 2) = 1$ and $F(2a - 1) = 3$. Together with the definition of $n$ this yields $V(n - 4) = 2a - 2$ and $V(n - 3) = V(n - 2) = V(n - 1) = 2a - 1$. Then by Lemma \ref{lem31} and Corollary \ref{col24}, $V(n) = V(m) + V(m + 1) = 2a$. Now by Corollary \ref{col22} we deduce \begin{eqnarray*} &&V(n + 1) = V(m) + V(m + 1) = 2a\\ &&V(n + 2) = V(m + 1) + V(m + 2) = 2a + 1\\ &&V(n + 3) = V(m + 1) + V(m + 3). \end{eqnarray*} If $F(a + 1) = 1$ then $V(n + 3) = a + (a + 2) = 2a + 2$ and $F(2a + 1) = 1$. Otherwise $F(a + 1) = 2$ or 3 and then $V(n + 3) = 2a + 1$ while $V(n + 4) = V(m + 2) + V(m + 3) = 2a + 2$. Thus, $F(2a + 1) = 2$. \end{proof} \begin{lemma}\label{lem313} If $F(a - 2) = F(a - 1) = F(a) = 2$, then $F(2a) = 1$. Furthermore if $F(a + 1) = 1$ then $F(2a + 1) = 2$ and if $F(a + 1) = 3$ then $F(2a + 1) = 3$. \end{lemma} \begin{proof} By Lemma \ref{lem36} it follows that $F(a - 3) = 3$ or 1. By Lemmas \ref{lem39}, \ref{lem310} and \ref{lem312} $F(2a - 4) = 1$, $F(2a - 3) = 3$, $F(2a - 2) = 2$ and $F(2a - 1) = 2$. Let $n$, $m$ be the minimum of $\{i : V(i) = 2a\}$ and $\{j : V(j) = a\}$ respectively. Then $V(n - 1) = V(n - 2) = 2a - 1$, $V(n - 3) = V(n - 4) = 2a - 2$. By Corollary \ref{eq24} and Lemma \ref{lem31}, $V(n) = V(m) + V(m + 1) = 2a$. Now by Corollary \ref{col22} we have \begin{eqnarray*} &&V(n + 1) = V(m) + V(m + 2) = 2a + 1\\ &&V(n + 2) = V(m) + V(m + 2) = 2a + 1\\ &&V(n + 3) = V(m + 1) + V(m + 3) \end{eqnarray*} From these it follows that if $F(a + 1) = 1$ then $V(n + 3) = 2a + 2$ so $F(2a + 1) = 2$, while if $F(a + 1) = 3$ then $V(n + 3) = 2a + 1$ and $F(2a + 1) = 3$. This completes the proof. \end{proof} \begin{table}[!ht] \fontsize{8}{8}\selectfont \caption{Frequencies of $2a$ and $2a + 1$ in terms of the frequencies of $a$ and some of its neighbors.}\label{tab32} \center{ \begin{tabular}{|c|c|c|c|c|c|c|} \hline $F(a - 2)$&$F(a - 1)$&$F(a)$&$F(a + 1)$&$F(2a)$&$F(2a + 1)$&Lemma\\ \hline &&1&&2&2& \ref{lem37}\\ \hline &&3&&3&2& \ref{lem38}\\ \hline &1&2&&1&3& \ref{lem39}\\ \hline &3&2&3&1&3& \ref{lem310}\\ \hline &3&2&2&1&3& \ref{lem310}\\ \hline &3&2&1&1&2& \ref{lem311}\\ \hline 1 or 3&2&2&1&2&1& \ref{lem312}\\ \hline 1 or 3&2&2&2 or 3&2&2& \ref{lem312}\\ \hline 2&2&2&1&1&2& \ref{lem313}\\ \hline 2&2&2&3&1&3& \ref{lem313}\\ \hline \end{tabular} } \end{table} Table~\ref{tab32}, which summarizes the results of Lemmas \ref{lem37} through \ref{lem313}, covers all the possible cases that can arise in the frequency sequence and, together with the other findings in Sections \ref{sec2} and \ref{sec3}, completely characterizes its behavior. From Table~\ref{tab32} we can derive all the values of the frequency sequence iteratively. One natural way to do so is in successive intervals of length $2^k$ for $k > 2$. We illustrate what we mean. From Table~\ref{tab31} the frequency sequence for $a\in [4, 7]$ is 1, 2, 2, 1. It follows from Table~\ref{tab32} that the values of the frequency sequence from 8 to 15 must be 2, 2 (\ref{lem37}) 1, 3 (\ref{lem39}) 2, 1 (\ref{lem312}) 2, 2 (\ref{lem37}), where we have put the lemma number from the last column in Table~\ref{tab32} between consecutive pairs of frequency values to highlight how the table applies. In a similar way we can fill in the values of the frequency sequence from 16 to 31, 32 to 63, 64 to 127, and so on. Note, however, that because $F(2a)$ and $F(2a + 1)$ can depend upon the value of $F(a - 2)$, $F(a - 1)$ and $F(a + 1)$ it may be the case that the frequency values at the start and endpoints of an interval depend upon frequency values slightly outside the immediately preceding interval, either in the prior interval of length a power of 2 or in the current such interval. For example, $F(30)$ and $F(31)$ in $[16, 31]$ are determined by $F(13)$, $F(14)$, $F(15)$ and $F(16)$; $F(32)$ and $F(33)$ in $[32, 63]$ are determined by $F(14)$, $F(15)$, $F(16)$ and $F(17)$. In Table~\ref{tab33} we highlight the pattern in the frequencies at the start and endpoints of the intervals [$2^k$,$2^{k + 1}$ - 1] for $k = 2$ through 11. Perhaps not unexpectedly, these frequencies are periodic; that is, beginning with the interval starting at 64 and ending at 127, the frequencies for the start points for successive intervals are 1, 2, 2, 1, 2, 2,$\cdots$ while the frequencies for the endpoints for these same intervals are 2, 3, 2, 2, 3, 2,$\cdots$. This result follows directly from Table~\ref{tab32} by induction. \begin{table}[!ht] \fontsize{8}{8}\selectfont \caption{Values of the frequency sequence at the start and endpoints of the intervals [$2^k$,$2^{k + 1} - 1$].}\label{tab33} \center{ \begin{tabular}{|c|c|c|c|} \hline Start&End&$F( Start )$&$F( End )$\\ \hline 4&7&1&1\\ \hline 8&15&2&2\\ \hline 16&31&1&1\\ \hline 32&63&2&2\\ \hline 64&127&1&2\\ \hline 128&255&2&3\\ \hline 256&511&2&2\\ \hline 512&1023&1&2\\ \hline 1024&2047&2&3\\ \hline 2048&4095&2&2\\ \hline \end{tabular} } \end{table} Gutman \cite{hhg} identified (but never proved) a set of simply stated rules for recursively generating the frequency sequence of $V(n)$ (see Table~\ref{tab34}). These rules explain how the values of the frequency sequence starting at $2a$ can be derived from the values of the sequence starting at $a$. Rule 3 takes precedence over Rule 2, which in turn takes precedence over Rule 1. \begin{table}[!ht] \fontsize{8}{8}\selectfont \caption{Gutman's rules for generating the frequency sequence of $V(n)$}\label{tab34} \center{ \begin{tabular}{|c|l|l|} \hline Rule \#&Initial String Starting at $a$ &New String Starting at $2a$\\ \hline 1&1&2 2\\ &3&3 2\\ &2 1&1 2 2 2\\ &2 3&1 3 3 2\\ \hline 2&2 2 1&1 3 2 1 2 2\\ &2 2 3&1 3 2 2 3 2\\ \hline 3&2 2 2 1&1 3 2 2 1 2 2 2\\ &2 2 2 3&1 3 2 2 1 3 3 2\\ \hline \end{tabular} } \end{table} Each of Gutman's rules follow from Table~\ref{tab32} and the earlier lemmas. For example, the first part of Rule 1 is Lemma \ref{lem37} (note that Gutman has no rule covering the pair 11, which cannot occur by Lemma \ref{lem33}). Lemma \ref{lem36} assures that there is no need for a rule covering four consecutive 2s. To derive the first part of Rule 3, namely that the string 2 2 2 1 generates the new string 1 3 2 2 1 2 2 2 in the next interval, argue as follows: apply Lemmas \ref{lem39} and \ref{lem310} to the first 2 to get 1 3; apply Lemma \ref{lem312} to the next 2 to get 2 2; apply Lemma \ref{lem313} to the third 2 to get 1 2; finally, apply Lemma \ref{lem37} to the single 1 to get 2 2. In a similar way, we can justify all the other components of Gutman's rules, and verify that they cover all possible cases. We show below that taken together Gutman's rules generate the frequency sequence. However, it is no longer the case that successive intervals beginning at powers of 2 are the natural division points in this process. That's because the varying string lengths together with the precedence guidelines accompanying Gutman's rules may require that we pass these division points in order to apply the appropriate rule. As a result we gradually drift further and further away from the powers of 2 as natural division points in generating the sequence using Gutman's rules. For example, applying Gutman's rules, [8, 16] are required to generate [16, 33]; [17, 34] are required to generate [34, 69]; [35-70] are required to generate [70, 141]; and so on. To see that Gutman's rules will generate the frequency sequence, it is probably best to begin at a term like $F(11)$, which under her approach is a string of length 1 with value 3. This single 3 at 11 unambiguously becomes 3 2 at 22 and 23. Further, note that under Gutman's rules the 3 at the end of any string necessarily becomes the pair 3 2 in the new string, no matter what string the initial 3 is contained in. Thus, the 3 at 22 necessarily leads to a 3 at 44, and so on. In this way there is no drift (since it is not necessary to know the values of the sequence following the 3) and a straightforward induction argument using Table~\ref{tab32} yields the desired result. (Note that this same argument holds for our rules in Table~\ref{tab32} as well.) The frequency sequence has many other interesting properties, all of which can be proven using the results we have described above together with an induction argument.\footnote{The interested reader can contact us for an Appendix containing further details.} These include \begin{enumerate} \item[(P1)] The 1s are natural markers of the frequency sequence, since no two consecutive 1s occur. There are precisely ten different strings of 2s and 3s that can occur between successive 1s, all of which end with 2.\footnote{This result was observed (but not proved) by Huber \cite{hhg}.} \item[(P2)] The value 3 occurs relatively less often in the frequency sequence. There are precisely ten different strings of 1s and 2s that can occur between successive 3s, including the empty string corresponding to the pair 3 3; \item[(P3)] The string (3, 2, 2, 1, 3) always follows the string (3, 2, 1, 2, 2, 1, 3) (except for the first occurrence of the latter string beginning at 11). Note that the last 3 in (3, 2, 1, 2, 2, 1, 3) also is the first 3 in (3, 2, 2, 1, 3); \item[(P4)] Pairs of consecutive 3s occur very infrequently. There are 17 distinct strings of 1s, 2s and 3s that can occur between successive pairs of 3s. (Recall from Lemma \ref{lem36} that at most two consecutive 3s can occur; in fact, we can also show from Table~\ref{tab32} that the first 3 in any such pair of consecutive 3s occurs at an odd index of the frequency sequence.) \end{enumerate} \section{V-sequence Generational Structure}\label{sec4} Many meta-Fibonacci sequences have been shown to have an underlying structure that leads to a natural partition of the sequence into successive finite blocks of consecutive entries (see, for example, \cite{cct, ktv, mcl1, pks1, pks2, tsm}). Following Pinn \cite{pks1, pks2} we suggestively call these blocks ``\emph{generations}''. The basic idea for this partition is the observation that the terms of the sequence that make up the $k^{th}$ block (generation) are defined by the original recursion as sums of certain earlier terms in the sequence that come (at least in part - see below) from the $(k-1)^{th}$ generation. In this way we build a family tree for the terms of the meta-Fibonacci sequence. This procedure is analogous to a well-known approach to understanding the pedigree of the terms in the usual Fibonacci sequence (see, for example, \cite{gkp}, chapter 6). One such natural partition for the $V$-sequence is defined as follows\footnote{This approach, which can be substantially generalized, leads to a natural generation structure for a wide variety of meta-Fibonacci sequences. As such it may provide a unifying theme for certain similar types of meta-Fibonacci recursions, something which to date is sorely lacking. It will be the topic of a future communication. See \cite{dbs} for some initial results.}: for $n > 4$ define the ``\emph{maternal}'' sequence \begin{equation}\label{eq41} M(n) = M(n - V(n - 1)) + 1,\: with\: M(n) = 1\: for\: n = 1,\: 2,\: 3,\: and\: 4. \end{equation} See Table~\ref{tab41} for the first 100 values of $M(n)$. Notice that the value of $M(n)$ is one more than the value of the $M$-sequence at the mother spot $(n - V(n - 1))$ of $V(n)$. In this sense we are considering $V(n)$ as the ``next generation'' of its mother $V(n - V(n - 1))$ who is a member of the previous generation with number $M(n - V(n - 1))$. This is the motivation for calling $M(n)$ the \emph{maternal generation number} of $V(n)$. We say that $G(k) = \{n: M(n) = k\}$ is the $k^{th}$ \emph{maternal generation} of $V(n)$.\footnote{Completely analogous results to what we describe for the maternal generation structure can be obtained for the paternal generation structure defined with respect to the father of $V(n)$. In this case the corresponding paternal recursion is $P(n) = P(n - V(n - 4)) + 1$ for $n > 4$, and $P(1) = P(2) = P(3) = P(4) =1$. We omit the details.} Notice that we place no restriction on the pedigree of the father term $V(n - V(n - 4))$. \begin{table}[!ht] \fontsize{8}{8}\selectfont \caption{The first 100 values of $M(n)$}\label{tab41} \center{ \begin{tabular}{l r r r r r l r r r r r} \hline {}&{}&{}&$n$&{}&{}&{}&{}&{}&$n$&{}&{}\\ \cline{2-6}\cline{8-12} {}&1&2&3&4&5&{}&1&2&3&4&5\\ \hline $M(n+0)$&1&1&1&1&2&$M(n+50)$&5&5&5&5&5\\ $M(n+5)$&2&2&2&2&3&$M(n+55)$&5&5&5&5&5\\ $M(n+10)$&3&3&3&3&3&$M(n+60)$&5&5&5&5&5\\ $M(n+15)$&3&3&3&3&3&$M(n+65)$&5&5&5&5&5\\ $M(n+20)$&4&4&4&4&4&$M(n+70)$&5&5&5&5&5\\ $M(n+25)$&4&4&4&4&4&$M(n+75)$&5&5&5&5&5\\ $M(n+30)$&4&4&4&4&4&$M(n+80)$&5&5&5&5&5\\ $M(n+35)$&4&4&4&4&4&$M(n+85)$&5&5&5&5&5\\ $M(n+40)$&4&4&4&5&5&$M(n+90)$&5&6&6&6&6\\ $M(n+45)$&5&5&5&5&5&$M(n+95)$&6&6&6&6&6\\ \hline \end{tabular} } \end{table} A priori it is not evident that $M(n)$ necessarily induces a partition on the $V(n)$ sequence that conforms to our intuition about the way a generational structure should operate. However, we can easily show that this is the case. \begin{proposition}\label{pps41} Let $M(n)$ be defined as above. Then for all positive integers $n$, $M(n + 1) = M(n)$ or $M(n) + 1$. \end{proposition} Thus, $M(n)$ is an increasing sequence with successive differences either 0 or 1, so that the $k^{th}$ generation of the $V$-sequence is the interval of consecutive values of $n$ such that $M(n) = k$. Hence the sets $G(k)$ are non-empty disjoint intervals that partition the natural numbers. We call the \emph{starting index} or \emph{start point} (respectively, \emph{ending index} or \emph{end point}) of the $k^{th}$ \emph{generation} $G(k)$ the least (respectively, greatest) value of $n$ such that $M(n) = k$. \begin{proof} We proceed by induction. By definition, $M(1) = M(2) = M(3) = M(4) = 1$ and $M(5) = M(5 - V(4)) + 1 = M(4) + 1 = 2$. Assume the result up to $k \geq 4$. Then $M(k + 1) = M(k + 1 - V(k)) + 1$. Now $V(k) = V(k - 1)$ or $V(k - 1) + 1$. In the latter case, $M(k + 1) = M(k + 1 - (V(k - 1) + 1)) + 1 = M(k - V(k - 1)) + 1 = M(k)$, as required. If $V(k) = V(k - 1)$, then $M(k + 1) = M((k - V(k - 1)) + 1) + 1$. Since $(k - V(k - 1)) + 1 < k + 1$, we have by the induction assumption that $M((k - V(k - 1)) + 1) = M(k - V(k - 1))$ or $M(k - V(k - 1)) + 1$. In the first case we conclude that $M(k + 1) = M(k - V(k - 1)) + 1 = M(k)$. In the second case we have $M(k + 1) = M(k - V(k - 1)) + 1 + 1 = M(k) + 1$.\footnote{Note that the proof of Proposition \ref{pps41} only requires that $V(n)$ is a sequence that is non-decreasing, where successive terms increase by 0 or 1, and where $(k - V(k - 1)) + 1 < k$ for all k large enough, so Proposition \ref{pps41} holds for any such sequence $V(n)$.} \end{proof} In Table~\ref{tab42} we illustrate the sets corresponding to the first 18 generations of $V(n)$, together with the associated frequencies of the start and endpoints of each generation. \begin{table}[!ht] \fontsize{8}{8}\selectfont \caption{Maternal generation structure of $V(n)$ and the frequencies of the $V$-values of the start and end points of first 18 generations.} \label{tab42} \center{ \begin{tabular}{|c|c|c|c|c|c|c|} \hline Generation&Start&End&$V(start)$&$V(End)$&$F(V(start))$&$F(V(End))$\\ \hline 1& 1 &4 &1 &1 &4 &4\\ \hline 2& 5 &9 &2 &5 &1 &2\\ \hline 3& 10 &20 &6 &11 &2 &3\\ \hline 4& 21 &43 &12 &23 &2 &2\\ \hline 5& 44 &91 &24 &48 &1 &2\\ \hline 6& 92 &188 &49 &97 &2 &2\\ \hline 7& 189 &384 &98 &196 &1 &2\\ \hline 8& 385 &777 &197 &393 &2 &3\\ \hline 9& 778 &1564 &394 &787 &2 &2\\ \hline 10& 1565 &3140 &788 &1576 &1 &2\\ \hline 11& 3141 &6293 &1577 &3153 &2 &2\\ \hline 12& 6294 &12601 &3154 &6308 &1 &2\\ \hline 13& 12602 &25218 &6309 &12617 &2 &3\\ \hline 14& 25219 &50453 &12618 &25235 &2 &2\\ \hline 15& 50454 &100925 &25236 &50472 &1 &2\\ \hline 16& 100926 &201870 &50473 &100945 &2 &2\\ \hline 17& 201871 &403762 &100946 &201892 &1 &2\\ \hline 18& 403763 &807547 &201893 &403785 &2 &3\\ \hline \end{tabular} } \end{table} The maternal generation concept is very appealing as a natural way to identify the generation structure for the $V$-sequence. From Table~\ref{tab42} it is evident that after generation 2 the length of successive maternal generations approximately doubles. This seems natural based on what we already know about the sequence from Sections \ref{sec2} and \ref{sec3}. Further, as we prove below (see Proposition \ref{pps43}), the start point for each generation coincides with the first occurrence of a new $V$-sequence value while the end point of each generation marks the last occurrence of some $V$-sequence value. For example, we see from Tables~\ref{tab42} and ~\ref{tab13} that generation 3 has start point (or begins) at 10, which is the index for the first 6 in the sequence (there are 2) and has end point (or ends) at index 20, where the $V$-sequence value is the last of three consecutive 11s that occur in the sequence. In this sense these generational division points appear to be quite natural ones. Finally, and as our intuition might demand, the mother spot of the $V$-value for the starting index of the $k^{th}$ generation point is the starting index of the $(k-1)^{th}$ generation. More precisely, we have the following: \begin{lemma}\label{lem42} For any fixed $k > 2$ let $s$ and $s'$ be the starting indices of generations $k$ and $k + 1$ respectively. Then the mother spot of $V(s')$ is $s$. That is, $s' - V(s' - 1) = s$. \end{lemma} \begin{proof} By the definition of $s$ as the starting index for the $k^{th}$ generation, $M(n) < k$ for $n < s$. But $M(s') = M(s' - V(s' - 1)) + 1 = k + 1$, and $M(n)$ is a monotonic increasing function. This implies that $s' - V(s' - 1)\geq s$. To show the opposite inequality, we proceed by contradiction. Suppose instead that $s' - V(s' - 1) > s$. By Corollary \ref{col22} the sequence $n - V(n - 1)$ increases by 0 or 1. Hence there is an $s'' < s'$ such that $s'' - V(s'' - 1)\geq s$. But since $M(n)$ is an increasing sequence it follows that $M(s'') = M(s'' - V(s'' - 1)) + 1$ $\geq M(s) + 1 = k + 1$. This contradicts the definition of $s'$ as the starting index for generation $k + 1$.Thus $s' - V(s' - 1)\leq s$. \end{proof} Using Lemma \ref{lem42} we show that each start point for a new generation coincides with the first occurrence of some $V$-sequence value while each end point of a generation marks the last occurrence of some $V$-sequence value. \begin{proposition}\label{pps43} For any fixed $k > 2$ let $s$ and $t$ be the starting and ending indices of generation $k$. Then:\\ 1. $V(s) = V(s - 1) + 1$ and $F(V(s))$ is either $1$ or $2$.\\ 2. $V(t + 1) = V(t) + 1$ and $F(V(t))$ is either $2$ or $3$. \end{proposition} \begin{proof} We proceed by induction on each statement. Clearly assertion 1 holds for $k = 2$. Now assume that it holds for generation $K$. Let $s$ and $s'$ be the starting indices of generation $K$ and $K + 1$ respectively. By definition, $V(s') = V(s' - V(s' - 1)) + V(s' - V(s' - 4))$. By Lemma \ref{lem42}, $s' - V(s' - 1) = s$. Thus, $V(s') = V(s) + V(s' - V(s' - 4))$. But by the induction hypothesis $V(s) = V(s - 1) + 1$. Thus $V(s') = V(s - 1) + 1 + V(s' - V(s' - 4))$. Since $s' - V(s' - 1) = s$, we know by Corollary \ref{col22} that $s' - 1 - V(s' - 2) = s$ or $s - 1$. If $s' - 1 - V(s' - 2) = s$ then $M(s' - 1) = M(s' - 1 - V(s' - 2)) + 1 = M(s) + 1 = K + 1$, which contradicts the definition of $s'$. So s$' - 1 - V(s' - 2) = s - 1$, from which it follows that $V(s') = V(s' - 1 - V(s' - 2)) + 1 + V(s' - V(s' - 4))$. But $V(s' - V(s' - 4))\geq V(s' - 1 - V(s' - 5))$ by Corollary \ref{col22} and Theorem \ref{thm21}. Hence we have $V(s')\geq V(s' - 1 - V(s' - 2)) + 1 + V(s' - 1 - V(s' - 5)) = V(s' - 1) + 1$. But by the Theorem \ref{thm21} $V(s') - V(s' - 1) = 0$ or 1 so $V(s') = V(s' - 1) + 1$ as desired. If $V(s' + 1) > V(s')$ then $F(V(s')) = 1$ as required. If not then $V(s') = V(s' + 1)$. We show that $V(s' + 2) > V(s' + 1)$. By definition $V(s' + 2) = V(s' + 2 - V(s' + 1)) + V(s' + 2 - V(s' - 2)) = V(s' + 2 - V(s')) + V(s' + 2 - V(s' - 2))$. But since $V(s') = V(s' - 1) + 1$, we have $V(s' + 2) = V(s' + 1 - V(s' - 1)) + V(s' + 2 - V(s' - 2))$. Since we have shown above that $s' - V(s' - 1) = s$ and $s' - 1 - V(s' - 2) = s - 1$ we can rewrite the last equality as $V(s' + 2) = V(s + 1) + V(s + 2)$. Recall that $(s' - 1 - V(s' - 2)) = s - 1$ is the mother spot of $V(s' - 1)$ so by Corollary \ref{col24} we have that $V(s' - 1) = V(s - 1) + V(s)$ or $V(s' - 1) = V(s - 1) + V(s + 1)$. Similarly, since $s' - V(s' - 1) = s$ is the mother spot of $V(s')$ we have that $V(s') = V(s) + V(s + 1)$ or $V(s') = V(s) + V(s + 2)$. But by the definition of the starting point of a generation we know that $V(s) = V(s - 1) + 1$, $V(s') = V(s' - 1) + 1$. Further, by the induction assumption on the frequency of $V(s)$, it follows that $V(s + 2) = V(s + 1) + 1$ or $V(s + 2) = V(s + 1) = V(s) + 1$. In the first case it follows that we cannot have $V(s') = V(s) + V(s + 2)$ since this would imply that $V(s') - V(s' - 1) = 2$ in both of the two alternatives $V(s' - 1) = V(s - 1) + V(s)$ or $V(s' - 1) = V(s - 1) + V(s + 1)$. Thus, in this case $V(s') = V(s) + V(s + 1)$ which is strictly less than $V(s' + 2) = V(s + 1) + V(s + 2)$. In the second case, where $V(s + 2) = V(s + 1)$, we must have $V(s') = V(s) + V(s + 1)$. But in this case $V(s' + 2) = 2 V(s + 1)$ so $V(s' + 2) - V(s') = V(s + 1) - V(s) = 1$ by the induction assumption. If $t$ is the ending index of generation $K$ then $t + 1$ is the starting index of generation $K + 1$. Hence $V(t + 1) = V(t) + 1$ by assertion 1. If $F(V(t)) = 1$, then $V(t - 1) = V(t) - 1$. But then $M(t + 1) = M(t + 1 - V(t)) + 1 = M(t - (V(t) - 1)) + 1 = M(t - V(t - 1)) + 1 = M(t)$, which contradicts the definition of $t$ as the endpoint of generation $K$. Thus $F(V(t)) > 1$ as required. This completes the proof. \end{proof} Recall from Table~\ref{tab42} that the lengths of successive generations after the first are essentially doubling. Thus it follows that this is also true for the V-sequence values at the start (and therefore end) points respectively of successive generations. The precise result is the following: \begin{proposition}\label{pps44} For fixed $k > 2$ let $a$ and $a'$ be the starting values of the V-sequence at generations k and k + 1 respectively. If $F(a) = 1$ then $a' = 2a + 1$ and if $F(a) = 2$ then $a' = 2a$. \end{proposition} \begin{proof} Suppose $F(a) = 1$. Let s be the unique index such that $V(s) = a$. By Lemma \ref{lem42} and Corollary \ref{col24} $a' = V(s') = V(s) + V(s + 1)$ or $a' = V(s) + V(s + 2)$. But since $F(a) = 1$, by Lemma \ref{lem33} we have that $F(a + 1) > 1$ so $V(s + 1) = V(s + 2) = a + 1$. Thus, in either case $a' = 2a + 1$. If $F(a) = 2$ let $s$ be the smallest positive integer such that $V(s) = a$. Then once again by Lemma \ref{lem42} and Corollary \ref{col24} we have $a' = V(s) + V(s + 1)$ or $a' = V(s) + V(s + 2)$. Thus, either $a' = V(s') = V(s) + V(s + 1) = 2a$ or $a' = V(s') = V(s) + V(s + 2) = 2a + 1$. Now Corollary \ref{col24} also implies that $V(s' - 1) = V(s - 1) + V(s)$ or $V(s' - 1) = V(s - 1) + V(s + 1)$. But since $F(a) = 2$ we have $V(s) = V(s + 1)$ while by Proposition \ref{pps43} we know that $V(s - 1) = a - 1$. Thus, we have $V(s' - 1) = 2a - 1$. Since by Theorem \ref{thm21} we require $V(s') - V(s' - 1) = 1$ it follows that $a' = V(s') = 2a$, as required. \end{proof} We conclude this section with another result that speaks to the intuitive appeal of the maternal generation partition of this $V$-sequence. Notice from Table~\ref{tab42} that starting with generation 2 the respective frequencies of the $V$-sequence values at the start and endpoints of the generations are periodic with period 5.\footnote{Note that because of Proposition \ref{pps43} the maternal generation structure on the $V$-sequence induces a partition of the frequency sequence. The endpoints in this partition are $V(start)$ and $V(end)$ of each generation. In Section \ref{sec3} we suggested a different partition of the frequency sequence, with start points the powers of 2 (see Table~\ref{tab33}). In that case both the start and end points have frequencies that are periodic with period 3.} Indeed, we can show even more, but we must start with generation 3 since the doubling property of the $V$-value at the starting index of successive generations does not begin until generation 4. \begin{proposition}\label{pps45} For any nonnegative integer $h$, assume generation $g = 5h + 3$ starts at $s$ with $V(s) = a$. Then the following holds\\ 1. $F(a) = 2$, $F(a - 1) = 2$, $F(a - 2) = 1$, and $F(a + 1) = 1$\\ 2. the starting V-value of generation $g + 1 = 5h + 4$ is $2a$, and $F(2a) = 2$\\ 3. the starting V-value of generation $g + 2 = 5h + 5$ is $4a$, and $F(4a) = 1$\\ 4. the starting V-value of generation $g + 3 = 5h + 6$ is $8a + 1$, and $F(8a + 1) = 2$\\ 5. the starting V-value of generation $g + 4 = 5h + 7$ is $16a + 2$, and $F(16a + 2) = 1$\\ 6. the starting V-value of generation $g + 5 = 5h + 8$ is $32a + 5$, $F(32a + 3) = 1$, $F(32a + 4) = 2$, $F(32a + 5) = 2$, and $F(32a + 6) = 1$. \end{proposition} \begin{proof} We proceed by induction. For the base case $h = 0$, $g = 3$, $s = 10$ and $a = 6$. All of the six statements above can be verified from Tables~\ref{tab13},~\ref{tab31},~\ref{tab32}. Suppose the proposition holds for $h = H - 1\geq 0$. Assume generation $5h + 3$ begins with $V$-value $b$. By statement 6 of the induction hypothesis generation $5(H - 1) + 8 = 5H + 3$ begins with value $32b + 5 = a$ and $F(a - 2) = 1$, $F(a - 1) = 2$, $F(a) = 2$, $F(a + 1) = 1$. By Proposition \ref{pps44} generation $5H + 4$ begins with value $2a$. Applying the index doubling properties from Table~\ref{tab32} we have $F(2a - 1) = 3$, $F(2a) = 2$, $F(2a + 1) = 1$. Since generation $5H + 4$ begins with value $2a$, which occurs with frequency 2, by Proposition \ref{pps44} generation $5H + 5$ begins with value $4a$. We again apply the index doubling properties of Section \ref{sec3} to obtain following terms of the frequency sequence starting at $4a - 2$: $F(4a - 2) = 3, 2, 1, 2, 2, 2 = F(4a + 3)$. Since generation $5H + 5$ begins with value 4a, which occurs with frequency 1, by Proposition \ref{pps44} generation $5H + 6$ begins with value $8a + 1$. Applying the index doubling properties of Section \ref{sec3} we have following frequency subsequence beginning at $8a - 4$: $F(8a - 4) = 3, 2, 1, 2, 2, 2, 1, 3 = F(8a + 3)$. Since generation $5H + 6$ begins with value $8a + 1$ and $8a + 1$ occurs with frequency 2, by Proposition \ref{pps44} we have that the generation $5H + 7$ begins with value $16a + 2$. By applying the index doubling properties of Section \ref{sec3} we have following frequency subsequence beginning at $16a - 2$: $F(16a - 1) = 3, 2, 2, 1, 2, 2, 2, 3 = F(16a + 6)$. Since generation $5H + 7$ begins with value $16a + 2$, which occurs with frequency 1, the generation $5H + 8$ begins at value $32a + 5$. Applying the index doubling properties of Section \ref{sec3} we have $F(32a + 3) = 1$, $F(32a + 4) = 2$, $F(32a + 5) = 2$ and $F(32a + 6) = 1$. This concludes the proof. \end{proof} The following corollary is immediate from the proof of Proposition \ref{pps45} and Table~\ref{tab32}. \begin{corollary}\label{col46} For any nonnegative integer h, assume generation $g = 5h + 3$ starts at s with $V(s) = a$. Then the following holds\\ 1. the ending V-value of generation $g = 5h + 3$ is $2a - 1$ and $F(2a - 1) = 3$\\ 2. the ending V-value of generation $g + 1 = 5h + 4$ is $4a - 1$ and $F(4a - 1) = 2$\\ 3. the ending V-value of generation $g + 2 = 5h + 5$ is $8a$ and $F(8a) = 2$\\ 4. the ending V-value of generation $g + 3 = 5h + 6$ is $16a + 1$ and $F(16a + 1) = 2$\\ 5. the ending V-value of generation $g + 4 = 5h + 7$ is $32a + 4$ and $F(32a + 4) = 2$. \end{corollary} Using Proposition \ref{pps45} we are able to derive explicit formulas for the starting (and therefore ending) indices and associated $V$-values in Table~\ref{tab42} for each generation. We sketch the approach, leaving the details to the reader. Let $s(k)$, $a(k)$ be the starting index and $V$-value for generation k, respectively, so $V(s(k)) = a(k)$. From Table~\ref{tab42} $s(3) = 10$ and $a(3) = 6$. By Proposition \ref{pps45} we have that if $g = 5h + 3$ then $a(5h + 3) = 32a(5h - 2) + 5$. Together with the initial value $a(3) = 6$ this implies that for $h\geq 0$, we have $a(5h + 3) = 6(32)^h + \displaystyle\frac{5(32)^h - 1)}{31}$. For example when $h = 0, 1$ and $2$ we have $a(3) = 6, a(8) = 197$ and $a(13) = 6309$ respectively, matching the values reported in Table~\ref{tab42}. By Lemma \ref{lem42} and Proposition \ref{pps43} for $k > 2$, $s(k) = s(k + 1) - V(s(k + 1) - 1) = s(k + 1) - (V(s(k)) - 1)$. This is a telescoping sum, from which we conclude that for $k > 3$, we have $s(k) = s(3) + \displaystyle\sum_{i=4}^{k} (V(s(i)-1))$. In fact, since $s(3) = s(2) + V(s(3) - 1)$, this formula can be rewritten as $s(k) = s(2) + \displaystyle\sum_{i=3}^{k} (V(s(i)-1))$. This formula gives the starting indices in terms of the starting values of the $V$-sequence. From Proposition \ref{pps45} we have that for any $h\geq 0$, the sum of the starting values of one complete cycle of five generations $5h + 3$ to $5h + 7$ inclusive is $31(V(s(5h + 3))) + 3$. It follows from this and the preceding formula for $s(k)$ that \begin{eqnarray*} s(5h + 3) &=& s(2) + \displaystyle\sum_{j=0}^{h-1} (31a(5j + 3) + 3 - 5) + a(5h + 3) - 1\\ &=& s(2) + \displaystyle\sum_{j=0}^{h-1} ((31(6(32)^j + \frac{5((32)^j - 1)}{31})) - 2) + 6(32)^h\\ & &{} + \frac{5((32)^h - 1)}{31} - 1\\ &=& s(2) + 6((32)^h - 1) + \frac{5((32)^h - 1)}{31} - 7h + 6(32)^h\\ & &{} + \frac{5((32)^h - 1)}{31} - 1 \\ &=& s(2) + 12(32)^h + \frac{10((32)^h - 1)}{31} - 7h - 7\\ &=& 12(32)^h + \frac{10((32)^h - 1)}{31} - 7h - 2 \end{eqnarray*} We can use the formula for $s(k)$, together with Corollary \ref{col46} and the value of $a(5h + 3)$, to compute $s(5h + 4)$ as follows: \begin{equation*} s(5h + 4) = s(5h + 3) + V(s(5h + 4) - 1) \end{equation*} But $V(s(5h + 4) - 1)$ is the ending $V$-value of generation $5h + 3$, so by Corollary \ref{col46} this is $2a(5h + 3) - 1$. Thus \begin{eqnarray*} s(5h + 4) &=& s(5h + 3) + 2a(5h + 3) - 1\\ &=& 12(32)^h + \frac{10((32)^h - 1)}{31} - 7h - 2 + 12(32)^h \\ & &{}+ \frac{10((32)^h - 1)}{31} - 1\\ &=& 24(32)^h + \frac{20((32)^h - 1)}{31} - 7h - 3 \end{eqnarray*} In an entirely similar manner we derive closed expressions for $s(5h + 5)$, $s(5h + 6)$ and $s(5h + 7)$, thereby determining the formula for a complete cycle of generations. \begin{eqnarray*} s(5h + 5)&=&48(32)^h + \frac{40((32)^h - 1)}{31} - 7h -4\\ s(5h + 6)&=&96(32)^h + \frac{80((32)^h - 1)}{31} - 7h -4\\ s(5h + 7)&=&192(32)^h + \frac{160((32)^h - 1)}{31} - 7h -3 \end{eqnarray*} For example when $h = 0$ we have $s(3) = 10, s(4) = 21, s(5) = 44, s(6) = 92$ and $s(7) = 189$. Once again these match the corresponding values reported in Table~\ref{tab42}. \section{Alternative Initial Conditions}\label{sec5} It is well known that the behavior of meta-Fibonacci recursions is highly sensitive to the assumed initial conditions (see, for example, the discussion in \cite{cct,hts1,hts2,ktv,tsm} for more on this). Virtually anything can happen as the initial conditions are varied: the resulting sequence may not be well defined, or if it is, its behavior may become highly chaotic or extremely simple. In this section we investigate how different initial conditions from the ones we have been using so far, namely $V(1) = V(2) = V(3) = V(4) = 1$, affect the behavior of the sequence generated by recursion \eqref{eq3}. From \eqref{eq3} it is immediately evident that we require both $V(1) < 5$ and $V(4) < 5$ in order that $V(5)$ is defined. Similarly we require $V(2) < 6$ and $V(3) < 7$. We have examined each of the $4\times5\times6\times4 = 480$ possible sets of initial conditions where $V(1) < 5$, $V(2) < 6$, $V(3) < 7$ and $V(4) < 5$. In most cases the new initial conditions result in a sequence that becomes undefined (``dies'') relatively quickly. However, there are some interesting exceptions, which we summarize in Tables~\ref{tab51} and~\ref{tab52}. For clarity in these tables we denote the sequence generated by \eqref{eq3} with new initial conditions by $V'(n)$. By $V(n)$ we continue to mean \eqref{eq3} with initial conditions all 1s. \begin{table}[!ht] \fontsize{8}{8}\selectfont \caption{Recursion \eqref{eq3} with alternative initial conditions that result in a well defined sequence}\label{tab51} \center{ \begin{tabular}{|c|c|} \hline ($V'(1)$, $V'(2)$, $V'(3)$, $V'(4)$)&Comments on the Resulting Sequence $V'(n)$\\ \hline 1, 1, 1, 1&$V'(n) = V(n)$ for all $n$. \\ \hline 1, 1, 1, 2&$V'(n) = V(n + 1)$ for all $n$. \\ \hline 1, 1, 2, 3&$V'(n) = V(n + 2)$ for all $n$. \\ \hline 1, 2, 3, 4&$V'(n) = V(n + 3)$ for all $n$. \\ \hline 2, 1, 1, 1&$V'(n) = V(n)$ for all $n > 1$.\\ \hline 2, 5, 1, 1&$V'(n) = V(n)$ for all $n > 2$.\\ \hline 3, 1, 1, 1&$V'(n) = V(n)$ for all $n > 1$.\\ \hline 3, 1, 6, 1&$V'(n) = V(n)$ for all $n > 3$.\\ \hline \end{tabular} } \end{table} In Table~\ref{tab51} we show the 8 sets of initial conditions, including the original set of all 1s, that result in a well-defined sequence. What is somewhat surprising is that all of these eight sets of initial conditions yield essentially the same sequence! We outline the proof briefly. First it is readily seen that the induction argument in Section \ref{sec2} used to prove that successive terms of $V(n)$ increase by 0 or 1 carries over for each of these sets of initial conditions (note that the key requirement is that a base case can be established, and this follows since the sequences all match the original $V(n)$ sequence after at most the first few terms). It follows that in each case the resulting sequence does not die. To show that each of the sequences eventually matches the original $V(n)$ sequence with some shift, we prove a somewhat more general result. Let $V(n;B)$ denote the $n^{th}$ term of the sequence generated by recursion \eqref{eq3} together with initial conditions $B = (b1, b2, b3, b4)$. Notice that $V(n;B) = V(n - V(n - 1;B);B) + V(n - V(n - 4;B);B)$. Then the following result holds. \begin{proposition}\label{pps51} Let $B1$ and $B2$ be two different sets of four initial conditions. Assume that both the sequences $V(n;B1)$ and $V(n;B2)$ do not die, and that there exists some positive integer N such that $V(N + j;B1) = V(j;B2)$ for $1\leq j \leq 4$. Then for all $n > 0$, we have $V(N + n;B1) = V(n;B2)$. That is, if the sequence $V(n;B2)$ has four initial conditions $B2$ that exactly match a string of four consecutive values starting at the $(N + 1)^{th}$ term in the sequence $V(n;B1)$ then the sequence $V(n;B2)$ is just the sequence $V(n;B1)$ with the first N terms dropped off. \end{proposition} Proposition \ref{pps51} applies directly to a number of the cases in Table~\ref{tab51}. The initial conditions (1, 1, 1, 2) match a string of four consecutive values of the original $V$-sequence beginning at the second term of the sequence. In this case these initial conditions lead to the original $V$-sequence with one term at the beginning dropped off. The initial conditions (1, 2, 3, 4) match a string of four consecutive values of the original $V$-sequence beginning at the fourth term of the sequence. In this case these initial conditions lead to the original V-sequence with three terms at the beginning dropped off. \begin{proof} We proceed by induction. Assume that $V(N + j;B1) = V(j;B2)$ for $j$ up to $k - 1 \geq 4$. Then for $j = k$ we have \begin{equation}\label{eq51} V(N + k;B1) = V(N + k - V(N + k - 1;B1);B1) + V(N + k - V(N + k - 4;B1);B1) \end{equation} and \begin{equation}\label{eq52} V(k;B2) = V(k - V(k - 1;B2);B2) + V(k - V(k - 4;B2);B2). \end{equation} By the induction assumption we have $V(N + k - 1;B1) = V(k - 1;B2)$ and $V(N + k - 4;B1) = V(k - 4;B2)$. Thus we rewrite \eqref{eq51} as \begin{equation}\label{eq53} V(N + k;B1) = V(N + k - V(k - 1;B2);B1) + V(N + k - V(k - 4;B2);B1) \end{equation} Since $V(k;B2)$ is well defined we know that $1 \leq k - V(k - 1;B2)\leq k - 1$ and $1 \leq k - V(k - 4;B2)\leq k - 1$. Applying the induction assumption once again to \eqref{eq53} yields \begin{equation}\label{eq54} V(N + k;B1) = V(k - V(k - 1;B2);B2) + V(k - V(k - 4;B2);B2) = V(k;B2). \end{equation} This completes the induction step and the proof. \end{proof} Proposition \ref{pps51} does not apply directly to all of the cases in Table~\ref{tab51}. However the proof for these cases follows by using it in two steps. For example, notice that for the set of initial conditions (2, 5, 1, 1) the next three terms of the sequence are 2, 3, 4. We already know that this sequence does not die. Hence we can apply Proposition \ref{pps51} with $B1$ = (2, 5, 1, 1) and $B2$ = (1, 2, 3, 4) to conclude that the two sequences are essentially identical. But since we have already shown that the latter sequence is essentially identical to the original $V(n)$ sequence, we are done. This approach can be used for all the remaining cases (2, 1, 1, 1), (3, 1, 1, 1), and (3, 1, 6, 1). \begin{table}[ht] \fontsize{8}{8}\selectfont \caption{Examples of recursion \eqref{eq3} with alternative initial conditions that result in sequences that die after a very long life}\label{tab52} \center{ \begin{tabular}{|c|c|} \hline ($V'(1)$, $V'(2)$, $V'(3)$, $V'(4)$) & Comments on the Resulting Sequence $V'$ \\ \hline 1, 2, 4, 4&Dies at 166567\\ \hline 1, 3, 3, 1&Dies at 166570\\ \hline 2, 1, 2, 4&Dies at 166568\\ \hline 3, 1, 2, 4&Dies at 166568\\ \hline 3, 3, 1, 2&Dies at 166569\\ \hline 3, 1, 4, 4&Dies at 474767\\ \hline \end{tabular} } \end{table} We have already observed that there are only eight sets of initial conditions that together with \eqref{eq3} generate a sequence that does not die. In most cases, if a sequence dies it does so relatively quickly. However, this is not always the case. As we show in Table~\ref{tab52}, some of the sequences that eventually die do so only after a relatively long life. (Note that in Table~\ref{tab52} the first five sets of initial conditions generate essentially the same sequence.) At this time we have no explanation for this unusual behavior. \section{Concluding Remarks}\label{sec6} One possible direction in which these results might be extended would be to introduce ``shift parameters'' $a$ and $b$ as follows: \begin{equation}\label{eq61} V(n) = V(n - a - V(n - 1)) + V(n - b - V(n - 4)) \end{equation} Such parameters have generated some interesting results in the context of other meta-Fibonacci recursions. We have not explored the values of a and b and sets of initial conditions, if any, for which the sequence $V(n)$ defined by \eqref{eq61} does not die. Adding additional terms to recursion \eqref{eq3} or \eqref{eq61} offers another possibility. We have confirmed that adding a third term $V(n - V(n - 7))$, together with the initial conditions $V(1) = V(2) =\cdots= V(6) = V(7) = 1$ produces a sequence that dies quickly. We have not explored this extension with any other sets of initial conditions, nor what happens if four or more such terms appear on the right-hand side of \eqref{eq3}. \section*{Acknowledgements}\label{ack} The authors thank Yuwei Sun for his substantial assistance in the preparation of this manuscript, and Professors Doug Hofstadter and Greg Huber for generously sharing their insights on $V(n)$ and for commenting on earlier versions of this paper. \begin{thebibliography}{9} \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{dbs} B. Dalton and S. M. Tanny, Generational structure of meta-Fibonacci sequences, \emph{unpublished} (2005). \bibitem{gkp} R. L. Graham, D. E. Knuth, and O. Patashnik, \emph{Concrete Mathematics, Second Edition}, Addision-Wesley, Massachusetts, 1994. \bibitem{gk} K. Gutman, Poem titled $V(n) = V(n - V(n - 1)) + V(n - V(n - 4))$, \emph{Math. Intelligencer} \textbf{23} (2001), 50. \bibitem{hts1} J. Higham and S. M. Tanny, A tamely chaotic meta-Fibonacci sequence, \emph{Congressus Numerantium} \textbf{99} (1994), 67--94. \bibitem{hts2} J. Higham and S. M. Tanny, More well-behaved meta-Fibonacci sequences, \emph{Congressus Numerantium} \textbf{98} (1993), 3--17. \bibitem{hds} D. Hofstadter, \emph{ Godel, Escher, Bach. An Eternal Golden Braid}, Basic Books, New York, 1979. \bibitem{hhg} D. Hofstadter and G. Huber, Private communications and seminar at University of Toronto, March 2000. \bibitem{ktv} T. Kubo and R. Vakil, On Conway's recursive sequence, \emph{Discrete Math.} \textbf{152} (1996), 225--252. \bibitem{mcl1} C. L. Mallows, Conway's challenge sequence, \emph{Amer. Math. Monthly} \textbf{98} (1991), 5--20. \bibitem{pks1} K. Pinn, Order and chaos in Hofstadter's Q(n) sequence, \emph{Complexity} \textbf{4} (1999), 41--46. \bibitem{pks2} K. Pinn, A chaotic cousin of Conway's recursive sequence, \emph{Experiment. Math.} \textbf{9} (2000), 55--66. \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 05A15; Secondary 11B37, 11B39. \noindent \emph{Keywords: } meta-Fibonacci recursion, Hofstadter sequence. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A004001} \seqnum{A005185} \seqnum{A063882} and \seqnum{A087777} .) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received April 11 2007; revised version received June 26 2007. Published in {\it Journal of Integer Sequences}, June 27 2007. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}