\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}
\usepackage{enumerate}
\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}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
\vskip 1cm{\LARGE\bf
A Family of Meta-{F}ibonacci Sequences\\
\vskip .05in
Defined by Variable-Order Recursions}
\vskip 1cm
\large
Nathaniel D.~Emerson \\
Department of Mathematics \\
California State University, Channel Islands\\
One University Drive\\
Camarillo, California 93012-8599\\
USA \\
\href{mailto:Nathaniel.Emerson@csuci.edu}{\tt Nathaniel.Emerson@csuci.edu} \\
\end{center}
\vskip .2 in
\begin{abstract}
We define a family of meta-Fibonacci sequences. For each sequence in
the family, the order of the of the defining recursion at the $n^{th}$
stage is a variable $r(n)$, and the $n^{th}$ term is the sum of the
previous $r(n)$ terms. Given a sequence of real numbers that satisfies
some conditions on growth, there is a meta-Fibonacci sequence in the
family that grows at the same rate as the given sequence. In
particular, the growth rate of these sequences can be exponential,
polynomial, or logarithmic. However, the possible asymptotic limits of
such a sequence are restricted to a class of exponential functions. We
give upper and lower bounds for the terms of any such sequence, which
depend only on $r(n)$. The Narayana-Zidek-Capell sequence is a member
of this family. We show that it converges asymptotically.
\end{abstract}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section]
%\documentclass[12pt,reqno]{article}
%\usepackage[english]{babel}
%\usepackage{amsfonts}
%\usepackage{amssymb}
%\usepackage{amsmath}
%\usepackage{amsthm}
%
%\usepackage{fullpage}
%\usepackage{float}
%\usepackage[usenames]{color}
%\definecolor{webgreen}{rgb}{0,.5,0}
%\definecolor{webbrown}{rgb}{.6,0,0}
%\usepackage[colorlinks=true,linkcolor=webgreen, filecolor=webbrown,citecolor=webgreen]{hyperref}
%\usepackage{hyperref}
\theoremstyle{plain}
\newtheorem{mainthm}{Theorem}
\newtheorem{bigthm}{Theorem}
\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{defn}[thm]{Definition}
\newtheorem{defs}[thm]{Definitions}
\newtheorem{example}[thm]{Example}
\theoremstyle{remark}
\newtheorem*{rem}{Remark}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\minus}{\smallsetminus}
\newcommand{\bC}{{\mathbb{C}}}
\newcommand{\bR}{{\mathbb{R}}}
\newcommand{\bN}{{\mathbb{N}}}
\newcommand{\bZ}{{\mathbb{Z}}}
\newcommand{\jr}{jr}
%\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}}}
%\begin{document}
\section{Introduction}
We consider \emph{meta-Fibonacci sequences}, by which we mean a
sequence given by a Fibonacci-type recursion, where the recursion
varies with the index. D. Hofstadter defined the first meta-Fibonacci
sequence \cite[p.\ 137]{Hof79}), which appears
as \seqnum{A005185} in Sloane's {\it Encyclopedia of Integer
Sequences}.
R. Guy posed some questions
about this sequence, which remain open \cite{G86}. J. Conway
\cite{Mal91}, B. Conolly \cite{Cnly89} and S. Tanny \cite{T92} proposed
similar sequences; and good results about these sequences have been
obtained. We define a new family of meta-Fibonacci sequences defined
by variable order recursions. This family is considerably different
from previously described families of meta-Fibonacci sequences
\cite{DGNW, JR05, CCT} both in terms of its definition and behavior.
We define the family of meta-Fibonacci sequences that is the subject of
this paper. The regular Fibonacci numbers are of course constructed by
adding the previous two terms of the sequence: $f_n = f_{n-1} +
f_{n-2}$ (\seqnum{A000045}). Adding the previous three terms yields the
\emph{Tribonacci numbers}: $t_n = t_{n-1} + t_{n-2} + t_{n-3}$
(\seqnum{A000073}). If we add the previous $r$ terms, we obtain the
\emph{$r$-generalized Fibonacci numbers} (``$r$-bonacci numbers''):
$f_{r,n} = f_{r,n-1} + \dots + f_{r,n-r}$ (\seqnum{A092921}). In our
family, we let $r$ vary as a function of $n$. We call the resulting
numbers \emph{variable-$r$ meta-Fibonacci numbers}. Let $\bN$ denote
the non-negative integers and $\bZ^+$ denote the positive integers.
\begin{defn}
\label{defn: vrmFs}
Let $r: \bN \to \bZ^+$ such that $r(0) = 1$, and $ r(n) \leq n$ for all $n \geq 1$.
Define
\[
b(n) = \sum_{k=1}^{r(n)} b(n-k), \quad n \geq 1,
\]
with initial condition $b(0) =1$. We call the sequence $b(n)$ a \emph{variable-$r$
meta-Fibonacci sequence,} and say that $r(n)$ \emph{generates} $b(n)$.
\end{defn}
For brevity, we call such a $b(n)$ an \emph{$r(n)$-bonacci sequence}.
Any such sequence is a non-decreasing sequence of positive integers. It
is easy to show that any $r(n)$-bonacci sequence omits infinitely many
positive integers. Additionally, distinct sequences, $r(n)$, generate
distinct sequences, $b(n)$. Thus, we have defined an uncountable family
of meta-Fibonacci sequences, in one-to-one correspondence with
sublinear sequences of positive integers.
The focus of this paper is the growth of $r(n)$-bonacci sequences,
$b(n)$. We consider
\emph{long-term growth}. That is, the order of $b(n)$ in terms of the
Landau symbols $O$, $\Omega$, and $\Theta$. We also ask about
\emph{short-term growth}. That is, the
value of the ratio of successive terms $b(n)/b(n-1)$. The long-term
growth is characterized by a wide range of possible behaviors. The
short-term growth is highly irregular in general.
In this paper, we denote integer-valued sequences by Roman letters, and
other sequences by Greek letters. Given a sequence of real numbers
$\sigma(n)$ that satisfies some mild conditions on growth, there is an
$r(n)$-bonacci sequence $b(n)$, which in the long term grows at
approximately the same rate as $\sigma(n)$. In particular, $b(n)$ is
$\Theta(\sigma(n))$.
\begin{mainthm}
Let $\sigma(n)$ be a sequence of real numbers such that for all $n$ sufficiently large,
$\sigma(n)$ is non-decreasing, $\sigma(n) \geq 1$, and
\[
\sigma(n+1)/2 \leq \sigma(n) \leq 2^{n-1}.
\]
Then there is a variable-$r$ meta-Fibonacci sequence $b(n)$ such that for all $n$
sufficiently large,
\[
\sigma(n)/2 < b(n) \leq \sigma(n).
\]
\end{mainthm}
The conditions on $\sigma(n)$ are mild enough that it is possible for
$\sigma(n)$ to be exponential, polynomial, or logarithmic (see
Corollary \ref{cor: sigma models}). In contrast, the Fibonacci
sequence (and the $r$-bonacci sequences) grow at an exponential rate.
The growth rate of many previously described meta-Fibonacci sequences
is linear when it is known \cite{CCT, Cnly89, Mal91, T92}.
Consider the growth rate of the ordinary Fibonacci numbers. It is well
known that the short-term growth rate converges to the Golden Section:
$(1 + \sqrt{5})/2$. Hence, the long-term growth rate is exponential.
Simiarly, the short-term growth rate of the $r$-bonacci numbers
converges. Let $\alpha_r$ denote the growth rate of the $r$-bonacci
numbers: $ f_{r,n}/f_{r,n-1} \to \alpha_r $ \cite{Miles}. It is
well-known that $1 < \alpha_r < 2$ for all $r \geq 2$. For technical
reasons, we define $\alpha_1 = 1$. The short-term growth rate of an
$r(n)$-bonacci sequence does not necessarily converge (see Example
\ref{eg: r(n) = 2,3... }). When it does converge, the only possible
limits are 2 or $\alpha_r$ for some $r \geq 1$. Moreover, it converges
to $\alpha_r$ if and only if $r(n) = r$ for all $n$ sufficiently
large. It follows that the class of sequences $\sigma(n)$ such that
$b(n) \sim \sigma(n)$ is restricted.
\begin{mainthm}
Let $\sigma(n)$ be a sequence of real numbers such that $\lim_{n \to \infty } \sigma(n)
/ \sigma(n - 1) $ exists and is non-zero. If
\[
\lim_{n \to \infty } \frac {b(n) }{ \sigma(n)} = L
\]
and $0 < L < \infty$, then
\[
\lim_{n \to \infty } \frac{\sigma(n)}{ \sigma(n - 1)} =2 , \quad \text{ or } \quad
\lim_{n \to \infty } \frac{\sigma(n)}{ \sigma(n - 1)} = \alpha_r
\]
for some $r \geq 1$ and $r(n) = r$ for all $n$ sufficiently large.
\end{mainthm}
Variable-$r$ meta-Fibonacci numbers were originally discovered by the
author while studying dynamical systems \cite{E01}, specifically the
dynamics of complex polynomials. One can consider \emph{closest return
times}, most intuitively, the iterates of a given point under some map
that are closer to the point than any previous iterate. Certain
generalized closest return times of polynomials are \emph{extended}
variable-$r$ meta-Fibonacci numbers (see Section \ref{sect: Generalization})
\cite{E05}. This result generalizes the fact that
there exist complex polynomials whose generalized closest return times
are the ordinary Fibonacci numbers \cite[Ex. 12.4]{BH92}.
We begin with a variety of examples of $r(n)$-bonacci sequences in
Section \ref{sect: Examples}. We then compare and contrast their
behavior to the behavior of other families of meta-Fibonacci
sequences.
We study the asymptotics of $r(n)$-bonacci sequences in Section
\ref{sect: Asymptotics}. The growth rate of any $r(n)$-bonacci
sequence is at most exponential. We give a condition for $b(n)$ to grow
exponentially. We prove Theorems \ref{thm: sigma approx} and \ref{thm:
growth restrictions}.
We derive estimates for $b(n)$ in terms of $r(n)$ in Section \ref{sect:
Estimates}. We give an iterative technique for finding upper and lower
bounds for $b(n)/b(n-1)$. We compute upper and lower bounds for $b(n)$
that do not depend on the previous terms of the sequence. We observe
that the Narayana-Zidek-Capell numbers (\seqnum{A002083}) are
$r(n)$-bonacci numbers. We show that they converge asymptotically to $c
2^{n-3}$ for some positive real number $c$.
In Section \ref{sect: Generalization}, we define a generalization of
the $r(n)$-bonacci numbers by taking $b(n)$ as a sequence defined on
all integers. This generalization has applications in the field of
polynomial dynamics.
\section{Examples} \label{sect: Examples}
Variable-$r$ meta-Fibonacci sequences are considerably different from
any previously described meta-Fibonacci sequence. We give several
examples of several $r(n)$-bonacci sequences. Our goal is that the
reader will develop some intuition for the sequences, particularly for
how $b(n)$ depends on $r(n)$. We might hope to find a closed-form
expression for a general $b(n)$ or an expression that depends only on
$r(1), \dots , r(n)$. The examples of this section show that we can
find a closed form in some cases, but in general it appears to be a
difficult problem.
The main questions we pose in this paper are about the growth rate of
$b(n)$, in both the long term and the short term. The long-term growth
is characterized by a wide range of possible behaviors. The short-term
growth is highly irregular in general. In this section, we give
specific examples of these phenomena. In Section \ref{sect:
Asymptotics}, we give general results. Finally, we recall some other
meta-Fibonacci sequences, most importantly other families of
meta-Fibonacci sequences. We compare and contrast them with
$r(n)$-bonacci sequences.
The proof of any claim made in the examples below has been left as an exercise.
First, we give the most elementary examples. If $r(1)= 1$ and $r(n) =
2$ for all $n \geq 2$, then $b(n) = f_{n+1}$, where $(f_n)$ is the
usual Fibonacci sequence (\seqnum{A000045}). If $r(n)=r \geq 2$ for all
$n$ sufficiently large, then up to re-indexing, the tail of $b(n)$ is
a generalized $r$-bonacci sequence (\seqnum{A092921}) for some initial
conditions.
If $r(n) =1$ for all $n$, then $b(n)=1 $ for all $n$. If $r(n) =1$ for all $n$ large,
then $b(n)$ is eventually constant. While this is a fairly trivial example, it
demonstrates that the lower bound for growth in the $r(n)$-bonacci family is constant.
That is, there are $r(n)$-bonacci sequences that are $\Theta(1)$. Conolly defined a
meta-Fibonacci sequence by
\[
K(n) = K(K(n-1)) + K(K(n-2)), \quad n>2,
\]
$K(1)= K(2) = 1$ \cite[p. 127]{Cnly89}. He
showed that $K(n) = 2$ for all $n > 2$. Thus, there is at least one previously
described meta-Fibonacci sequence that is eventually constant. To the best of the
author's knowledge, this is the only previously described meta-Fibonacci sequence that
does not grow at a polynomial rate. We can also generalize this example by taking $r(n)
= 1$ for many $n$. This makes the short-term growth of $b(n)$ small, and results in slow
long-term growth (see Example \ref{eg: lin growth}).
At the other extreme, in the following example we take $r(n)$ as large as allowed. The
result is that $b(n)$ is maximally large (see Proposition \ref{prop: max growth 2 n-1}).
\begin{example} \label{eg: b(n) max growth}
Let $r(n) = n$ for $n \geq 1$, then $b(n) = 2^{n-1}$ for $n \geq 1$:
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\
\hline
r(n) & 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\
\hline
b(n) & 1 & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & 512\\
\hline
\end{array}
\]
\end{example}
Doubling is a major theme in the behavior of $b(n)$. The following example shows that
$b(n)$ can more than double for infinitely many $n$. Thus, the short-term growth can be
rapid for infinitely many $n$. However, in order to make $b(n)/b(n-1)$ large, we must
take $r(n-1)$ small. Therefore, the long-term growth is much slower than in the previous
example.
\begin{example} \label{eg: short growth = 3}
For $n \geq 1$, let $r(n) = n$ if $n$ is even, and $r(n) =1$ if $n$ is odd:
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 &10\\
\hline
r(n) & 1 & 1 & 2 & 1 & 4 & 1 & 6 & 1 & 8 & 1 & 10\\
\hline
b(n) & 1 & 1 & 2 & 2 & 6 & 6 & 18 & 18 & 54 & 54 & 162\\
\hline
\end{array}
\]
It is straightforward to show that $b(n) = 3b(n-1)$ for $n \geq 4$ and even.
\end{example}
The following example shows that $ b(n)/{ b(n-1)} \to 2$ occurs for non-constant
sequences.
\begin{example}
For $n \geq 2$, let
$r(n) = n$ for $n$ even, and $r(n) = n-1$ for $n$ odd:
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}\hline
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
\hline
r(n) & 1 & 1 & 2 & 2 & 4 & 4 & 6 & 6 & 8 & 8 \\
\hline
b(n) & 1 & 1 & 2 & 3 & 7 & 13 & 27 & 53 & 107 & 213 \\
\hline
\end{array}
\]
For $n > 2$, $b(n) = 2 b(n-1) +1$ for $n$ even, and $b(n) = 2 b(n-1) - 1$ for $n$ odd.
Hence, $ \lim_{n \to \infty} b(n)/{ b(n-1)} = 2$.
\end{example}
The following example shows that the short-term growth, the sequence $(b(n)/ b(n-1))$,
need not converge.
\begin{example}\label{eg: r(n) = 2,3... }
For $n \geq 2$, let $r(n) = 2$ for $n$ even, and $r(n) = 3$ for $n$ odd:
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}\hline
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
\hline
r(n) & 1 & 1 & 2 & 3 & 2 & 3 & 2 & 3 & 2 & 3 \\
\hline
b(n) & 1 & 1 & 2 & 4 & 6 & 12 & 18 & 36 & 54 & 108 \\
\hline
\end{array}
\]
It follows that $b(n)/ b(n-1) = 2$ for $n
> 2$ and odd, and $b(n)/ b(n-1) = 3/2$ for $n>2$ and even.
\end{example}
The following example shows how irregularly $b(n)$ can grow in the short-term. We take
a very irregular function for $r(n)$, and generate a $b(n)$ that grows irregularly.
\begin{example}
Let $r(0)= 1$, and $r(n) = \varphi(n)$ for $n >0$, where $
\varphi(n)$ is the Euler totient function (\seqnum{A000010}):
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 &10 & 11 & 12 & 13 &14 &15&16&17\\
\hline
r(n) & 1 & 1 & 2 & 2 & 4 & 2 & 6 & 4 & 6 & 4 & 10 & 4 & 12 &6 & 8& 8& 16\\
\hline
b(n) & 1 & 1 & 2 & 3 & 7 & 10 & 24 & 44 & 90 & 168 & 350 & 652 & 1352 &2656 &5336&10628&21304\\
\hline
\end{array}
\]
\end{example}
From the above examples, we can see that a closed form for $b(n)$ can be found in some
cases. However, finding a closed form in general appears to be a difficult problem.
Even the more modest goal of finding an expression for $b(n)$ that depends only on
$r(n)$ seems difficult. Although, we can find upper and lower bounds for $b(n)$ that
depend only on $r(n)$ (see Theorem \ref{thm: upper/lower bounds}).
The next three sequences are examples of the long-term behavior of $b(n)$. They show
that through careful choice of $r(n)$, we can make $b(n)$ grow at a predetermined rate
(see Theorem \ref{thm: sigma approx}).
\begin{example}\label{eg: exp growth}
Choose $r(n)$ so that $\sqrt{3}^{\, n} / 2 < b(n) \leq \sqrt{3}^{\, n}$ for all $n \geq
0$:
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 &10 & 11 & 12 & 13\\
\hline
r(n) & 1 & 1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 & 5\\
\hline
b(n) & 1 & 1 & 2 & 4 & 8 & 8 & 16 & 32 & 64 & 64 & 128 & 256 & 512 & 1024\\
\hline
\end{array}
\]
So $b(n)$ is $\Theta(\sqrt{3}^n)$.
\end{example}
By taking $r(n) =1 $ frequently, we can have linear growth for $b(n)$.
\begin{example} \label{eg: lin growth}
For $n \geq 2$, let $r(n) = 2$ if $n = 2^k$ for some $k
\in \bN$, and $r(n) = 1$ otherwise:
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}\hline
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
\hline
r(n) & 1 & 1 & 2 & 1 & 2 & 1 & 1 & 1 & 2 & 1 \\
\hline
b(n) & 1 & 1 & 2 & 2 & 4 & 4 & 4 & 4 & 8 & 8 \\
\hline
\end{array}
\]
It is easy to show that $n/2 < b(n) \leq n$ for $n \geq 1$. That is, $b(n)$ is
$\Theta(n)$.
\end{example}
We can construct $b(n)$ that grows logarithmically. No previously published
meta-Fibonacci sequence grows logarithmically.
\begin{example}\label{eg: log growth}
For $n \geq 2$, let
$r(n) = 2$ if $n = 2^{2^k}$ for some $k \in \bN$, and $r(n) = 1$ otherwise:
\[
\begin{array}{|c|c|c|c|c|c|c|}\hline
n & 0 & 1 & 2 & 4 & 16 & 256 \\
\hline
r(n) & 1 & 1 & 2 & 2 & 2 & 2 \\
\hline
b(n) & 1 & 1 & 2 & 4 & 8 & 16 \\
\hline
\end{array}
\]
We have $\log_2 n < b(n) \leq 2 \log_2 n$ for $n
>1$. Hence, $b(n)$ is $\Theta(\log_2 n)$.
\end{example}
Similarly, we can construct examples that are $\Theta(\log_2 \log_2 n)$, etc. Thus,
$b(n)$ can grow extremely slowly, even when it is not eventually constant.
We now recall some previously defined meta-Fibonacci
sequences. We take Hofstadter's $Q$-sequence (\seqnum{A005185}, \cite[p. 137]{Hof79})
as a typical example. Let $Q(1) = Q(2) = 1$ and
\[
Q(n) = Q(n-Q(n-1)) + Q(n-Q(n-2)), \quad n > 2.
\]
The first few terms are given below:
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20\\
\hline
Q(n) & 1& 1& 2& 3& 3& 4& 5& 5& 6& 6 & 6& 8& 8& 8& 10& \textbf{9}& 10& 11& 11& 12\\
\hline
\end{array}
\]
The recursion for $Q(n)$ is ``self-referential.'' The order of the recursion is fixed.
The terms we add to obtain $Q(n)$ are not necessarily the immediately previous terms. It
may happen that for some $n$, we add terms that are early in the sequence and thus
small, so $Q(n)$ will be small. In contrast for an $r(n)$-bonacci sequence $b(n)$, an
``external variable,'' $r(n)$, controls the recursion. The order of the recursion is not
generally fixed. We always add the immediately previous $r(n)$ terms, so $b(n)$ is
always the sum of the greatest of the preceding terms. These differences result in
$Q(n)$ having much more complicated short-term behavior than $b(n)$. The short-term
behavior of $Q(n)$ has been described as ``chaotic'' \cite{Hof79} (for instance $Q(16) <
Q(15)$). In contrast, $b(n)$ is non-decreasing.
Although the Hofstadter sequence is the oldest meta-Fibonacci sequence, some fundamental
questions about it remain open. For example, is it well defined? Observe that it is
well-defined if and only if $Q(n) \leq n$ for all $n > 2$. From this observation, we
see that the fundamental question about $Q(n)$ is really a question about its growth
rate; if it is well defined, then its maximum possible growth rate is linear. In fact,
it appears from numerical evidence that $ Q(n)/n \to 1/2$ \cite{G86}. Therefore, it
seems that the long-term behavior of $Q(n)$ is tame.
This observation illustrates a general property of self-referential sequences, including
all previously published meta-Fibonacci sequences. We can compute an upper bound for the
growth of any self-referential sequence from its recursion. For example, let $s(n)$ be a
sequence satisfying some self-referential recursion of the form
\[
s(n) = s(n + c - s(n-d)) + (\text{other terms}),
\]
for some $c, d \in \bZ$ with initial condition(s) $s(0), \dots$. It follows that
\[
s(n) \leq n+ c + d .
\]
In particular, $s(n)$ must be $O(n)$.
In light of this property, it should not be surprising that most previously described
meta-Fibonacci sequences grow linearly. For instance, the Tanny sequence
(\seqnum{A006949}, \cite{T92}):
\[
T(n) = T(n - 1 -T(n-1)) + T(n - 2 - T(n-2)), \quad n > 2,
\]
$T(0) = T(1) = T(2)$. Our estimate gives $T(n) \leq n $. In fact, it is known that $
T(n)/n \to 1/2$ \cite[Prop. 2.7]{T92}.
For an $r(n)$-bonacci sequence $b(n)$, this argument is not useful. It implies we must
have $n- r(n) \geq 0$, which is built in to the definition of $r(n)$. Therefore, we must
use other methods to estimate the growth rate of $b(n)$.
Since the $r(n)$-bonacci sequences are a family, we compare and contrast the family to
known meta-Fibonacci families. The $r$-bonacci sequences
can be regarded as a family of meta-Fibonacci sequences parameterized
by $r \geq 2$ (since $r=1$ gives a constant sequence). It is a proper subfamily of the
$r(n)$-bonacci family. This family is quite well understood. Every sequence in the
family grows exponentially, and a closed form its terms is known \cite{Miles}.
J. Callaghan, J. Chew and S. Tanny studied a family of meta-Fibonacci sequences
parameterized by $a > 0$, $ k
>1$ \cite{CCT}:
\[
T_{a,k}(n) = \sum_{i=0}^{k-1} T_{a,k}(n - i - a
-T_{a,k}(n-i-1)), \quad n > a+k, \ k \geq 2
\]
with $ T_{a,k}(n) = 1 $ for $1 \leq n \leq a+k$. This family generalizes the Tanny
sequence (\seqnum{A006949}, \cite{T92}). Sub-families of this family have also been
considered \cite{HT93b, JR05}. For all $a$ and all odd $k$, the growth rate of sequences
in this family is linear \cite[Cor. 5.14]{CCT}:
\[
\lim_{n \to \infty } \frac{ T_{a,k}(n)}{n} = \frac{k-1}{k}.
\]
In previously described meta-Fibonacci sequences, three orders of growth have been
found: exponential, linear, and constant. Moreover, all of the sequences in each of the
above meta-Fibonacci families have the same order of growth. We have given examples of
all of these orders of growth and more in the $r(n)$-bonacci family. Part of the
explanation for this difference is that both of the above families contain only
countably many sequences. In contrast, there are uncountably many $r(n)$-bonacci
sequences. When we define an $r(n)$-bonacci sequence, we get to make countably many
choices for $r(n)$. Each choice can be made in $n (\geq 2)$ ways. These choices can be
made recursively, so $b(n)$ can be defined recursively to satisfy specified behavior on
its growth. It follows that we can construct a wide variety of growth in the family (see
Theorem \ref{thm: sigma approx}).
R.~Dawson, G.~Gabor, R.~Nowakowski and D.~Wiens defined a family of meta-Fibonacci
sequences by a random process \cite{DGNW}. A $(p,q)$-\emph{sequence} $(F_n)$ is defined
as follows: Fix positive integers $p$ and $q$ and choose real numbers $a_1,\cdots,a_p$.
Set $F_n=a_n$ with probability one for $n\leq p$. Let $F_{n+1}=\sum^q_{k=1}F_{j_k}$ for
$n\geq p$, where the $j_k$ are randomly chosen (with replacement) from $(1,2,\cdots,n)$
with the uniform distribution. Note that $(p,q)$-sequences are extremely general; any
sequence defined by an order $q$ linear recursion with positive integer coefficients can
occur as a $(p,q)$-{sequence}. This includes all previously published meta-Fibonacci
sequences. The authors did not address the question of the possible values of $(F_n)$,
instead they asked about its average value. The expected value of $F_n$ is a polynomial
in $n$ of degree $q-1$ \cite[Thm. 1]{DGNW}. We propose the following interpretation of
this result: a ``typical'' meta-Fibonacci sequence defined by a recursion of fixed order
grows at a polynomial rate. Under this interpretation, there are $r(n)$-bonacci
sequences that grow at the rate of a typical meta-Fibonacci sequence, but there are also
$r(n)$-bonacci sequences that grow faster or slower.
In many ways, the family of $(p,q)$-sequences is the meta-Fibonacci family which is most
similar to the $r(n)$-bonacci family: both families are uncountable; they properly
contain the $r$-bonacci numbers; there are sequences in both families that grow at
different rates (the Fibonacci sequence, the Tanny sequence, and an eventually constant
sequence can all occur as $(p,2)$-sequences). However, it is not always possible to make
meaningful comparisons between the two families because $(p,q)$-sequences are random and
$r(n)$-bonacci sequences are deterministic.
\section{Asymptotic Growth} \label{sect: Asymptotics}
In this section, we examine the asymptotic growth of $b(n)$. We show more precisely the
variety of different growth rates that $b(n)$ can have. Here, the $r(n)$-bonacci family
is characterized by flexibility in its short-term growth. This flexibility leads to
short-term oscillation, and the possible asymptotic limits are quite restricted. On the
other hand, a wide range of possible long-term growth rates are possible.
After some preliminaries, we consider the short-term growth of $b(n)$. The key question
is about doubling: how does $b(n)/b(n-1)$ compare to 2? We give an answer based on
$r(n)$, which is the foundation of the rest of our results. We show that in the long
term, no $b(n)$ can more than double. We give a condition for $b(n)$ to grow
exponentially.
Given a sequence $\sigma(n)$ that satisfies some mild conditions on growth, there is an
$r(n)$-bonacci sequence that grows at the same rate as $\sigma(n)$. This shows some of
the broad range of possible growth rates that occur in the $r(n)$-bonacci family. In
contrast, the asymptotic limits of $b(n)$ are restricted. If $b(n) \sim \sigma(n) $,
then $\sigma(n)$ grows like an $r$-bonacci sequence or $2^n$.
In this section, let $b(n)$ be a variable-$r$ meta-Fibonacci sequence generated by
$r(n)$. We state elementary conclusions about the limiting behavior of $b(n)$.
\begin{lem}
We have $\limsup_{n \to \infty} r(n) = 1$ if and only if $b(n)$ is eventually constant.
\end{lem}
\begin{lem}
We have $\limsup_{n \to \infty} r(n) > 1$ if and only if $\lim_{n \to \infty} b(n) =
\infty$.
\end{lem}
Thus, an $r(n)$-bonacci sequence converges if and only if it is eventually constant. We
consider sequences that are not eventually constant.
We examine the short-term growth of $b(n)$. For any given $n$, the larger $r(n)$ is, the
larger $b(n)$ will be. However, it is $\Delta r(n) = r(n) - r(n-1)$ that has the
greatest influence on the growth rate. The following lemma is our basic estimate; we
give a condition for $b(n)$ to double.
\begin{lem} \label{lem: Delta r(n) = 1 -> growth =2}
If $\Delta r(n) = 1$ for some $n \geq 1$, then $b(n)/b(n-1) =2$.
\begin{proof}
We have $r(n) = r(n-1) + 1$. Hence,
\begin{align*}
b(n) &= \sum_{k=1}^{r(n)} b(n-k)\\
&= b(n-1) + \sum_{k=2}^{r(n-1)+1} b(n-k)\\
&= b(n-1) + \sum_{j=1}^{r(n-1)} b({n-1 - j})\\
&= 2b(n-1).
\end{align*}
\end{proof}
\end{lem}
We give a universal upper bound for $b(n)$---one which does not depend on $r(n)$.
\begin{prop} \label{prop: max growth 2 n-1}
If $b(n)$ is an $r(n)$-bonacci sequence, then $b(n) \leq 2^{n-1}$ for all $n \geq 1$.
\begin{proof}
Let $\hat{r}(n) = n$ for all $n \geq 1$, and let
$\hat{b}(n)$ be the $r(n)$-bonacci sequence generated by $\hat{r}(n)$. By Lemma
\ref{lem: Delta r(n) = 1 -> growth =2}, $\hat{b}(n) = 2^{n-1}$ for all $n \geq 1$. Note
that $b(0) = \hat{b}(0) = 1$. Inductively, we have
\[
b(n) = \sum_{k=1}^{r(n)} b(n-k) \leq \sum_{k=1}^{n} b(n-k) \leq
\sum_{k=1}^{\hat{r}(n)} \hat{b}({n-k}) = \hat{b}(n) = 2^{n-1}.
\]
\end{proof}
\end{prop}
This bound shows that all $r(n)$-bonacci sequences are $O(2^{n})$. Hence, their order is
at most exponential. We compare the growth rate of $b(n)$ to the growth rate of the
$r$-bonacci numbers.
\begin{prop} \label{prop: exp growth}
Let $b(n)$ be an $r(n)$-bonacci sequence. If $ r\leq \liminf_{n \to \infty} r(n)$ for
some $r\in \bZ^+$, then $b(n)$ is $\Omega(\alpha_r^n)$.
\begin{proof}
Fix $N$ so that $r(n) \geq r$ for all $n > N$. Let $\hat{r}(n) = r(n)$ for $n =0,
\dots, N$, and $\hat{r}(n) = r$ for $n >N$. Let $\hat{b}(n)$ be the $r(n)$-bonacci
sequence generated by $\hat{r}(n)$. For $n$ large, $\hat{b}(n)$ satisfies the
$r$-bonacci recursion, so its tail is a generalized $r$-bonacci sequence with initial
conditions $\hat{b}(N+1), \dots, \hat{b}(N+r)$. Hence, $\hat{b}(n)$ is $
\Theta(\alpha_r^n)$. It is clear that $\hat{b}(n) \leq b(n)$ for all $n$. Therefore,
${b}(n)$ is $\Omega(\alpha_r^n)$.
\end{proof}
\end{prop}
We give a condition for $b(n)$ to grow exponentially.
\begin{cor}
If $\liminf_{n \to \infty} r(n) \geq 2$, then $b(n)$ grows exponentially.
\begin{proof}
By Proposition \ref{prop: exp growth}, $b(n)$ is $\Omega(\alpha_r^n)$ for some $r\geq
2$. It is known that $\alpha_r
> 1$ for $r \geq 2$ \cite{Miles}.
\end{proof}
\end{cor}
We extend Lemma \ref{lem: Delta r(n) = 1 -> growth =2} to cover all cases of $\Delta
r(n)$. This yields information about the relative magnitude of $b(n)/b(n-1)$ and 2. The
following is the main lemma in this paper:
\begin{lem}\label{lem: b(n) growth}
For all $n \geq 1$ the following hold:
\begin{enumerate}[\indent a.]
\item $b(n) / b(n-1) = 1 $ if and only if $\Delta r(n) =
1-r(n-1)$; \label{thm: growth, case r(n) = 1}
\item $1 < b(n) / b(n-1) < 2 $ if and only if $1-r(n-1) < \Delta r(n) <
1$;\label{thm: growth, case Delta < 1}
\item $b(n) / b(n-1) = 2 $ if and only if $\Delta r(n) = 1$;\label{thm: growth, case Delta = 1}
\item $ b(n) / b(n-1) > 2 $ if and only if $\Delta r(n) > 1$.\label{thm: growth, case Delta > 1}
\end{enumerate}
\begin{proof}
We will prove the ``if'' part of each case. Case {\ref{thm: growth, case r(n) = 1}} is
equivalent to $r(n) =1$, so it is clear. Case {\ref{thm: growth, case Delta = 1}} is
Lemma \ref{lem: Delta r(n) = 1 -> growth =2}. In case {\ref{thm: growth, case Delta <
1}}, we have $r(n) < r(n-1) + 1$. Thus,
\[
b(n) = \sum_{k=1}^{r(n)} b(n-k) < \sum_{k=1}^{r(n-1)+1}
b(n-k)= 2 b(n-1),
\]
where the last equality follows from Lemma \ref{lem: Delta r(n) = 1 -> growth =2}. Case
{\ref{thm: growth, case Delta > 1}} is similar. The ``only if'' directions follow by
considering the above cases.
\end{proof}
\end{lem}
We use this result on the short-term growth of $b(n)$ to study the long-term growth of
$b(n)$.
\begin{cor} \label{cor: lim sup growth < 2 -> r(n) const}
If $\displaystyle \limsup_{n \to \infty} \frac{b(n)}{b(n-1)} < 2$, then $r(n)$ is
eventually constant.
\begin{proof}
By Lemma \ref{lem: b(n) growth}.{\ref{thm: growth, case Delta < 1}} for all $n$
sufficiently large, $r(n) - 1 < r(n-1) $. It follows that for $n$ large, $r(n)$ is a
non-increasing sequence of positive integers, so it is eventually constant.
\end{proof}
\end{cor}
\begin{lem} \label{lem: lim inf growth <= 2}
For any $r(n)$-bonacci sequence $b(n)$, we have
\[
\liminf_{n \to \infty} \frac{b(n)}{b(n-1)} \leq 2.
\]
\begin{proof}
Towards a contradiction, suppose not. By Lemma \ref{lem: b(n) growth}.{\ref{thm: growth,
case Delta > 1}}, for all $n$ sufficiently large, $\Delta r(n) > 1$. It follows that
$n -r(n) < (n-1) -r(n-1)$ for $n$ large. Thus, $(n -r(n))$ is a strictly decreasing
sequence of integers for $n$ large. Therefore, $N- r(N) < 0$ for some $N$, contrary to
$r(n) \leq n$ by Definition \ref{defn: vrmFs}.
\end{proof}
\end{lem}
We now demonstrate the wide range of asymptotic growth rates that are found in the
$r(n)$-bonacci family. For a sequence of real numbers $\sigma(n)$ that satisfies the
following conditions on growth, we can construct an $r(n)$-bonacci sequence $b(n)$ that
grows at the same rate as $\sigma(n)$ in some sense. In particular, $b(n)$ is
$\Theta(\sigma(n))$.
\begin{bigthm} \label{thm: sigma approx}
Let $\sigma(n)$ be a sequence of real numbers such that the following hold for all $n$
sufficiently large:
\begin{enumerate}
\item $\sigma(n)$ is non-decreasing;
\item $\sigma(n) \geq 1$;
\item $\sigma(n) \leq 2^{n-1}$;
\item $\sigma(n) \geq \sigma(n+1)/2$.
\end{enumerate}
Then there is an $r(n)$-bonacci sequence $b(n)$ such that for all $n$ sufficiently
large,
\[
\sigma(n)/2 < b(n) \leq \sigma(n).
\]
\begin{proof}
We construct $b(n)$ by using Lemma \ref{lem: b(n) growth} to choose $r(n)$
appropriately. Take $N$ large enough so that $ \sigma(n)$ satisfies all 4 of the above
conditions for all $n \geq N$. We have $1\leq \sigma(N) \leq 2^{N-1}$ by Conditions 2
and 3, so $ \sigma(N)/2 < 2^m \leq \sigma(N)$ for some $m < N$. Let $r(n) = n$ for $n =
1, \dots, m$, and $r(n) = 1$ for $n = m+1, \dots , N$. Lemma \ref{lem: b(n) growth}
implies that $b(N) = b(m) = 2^m$, so $b(N)$ satisfies the desired bounds.
Suppose now that for some $n> N$ we have defined the sequence up to $b(n-1)$, so that $
\sigma(n-1)/2 < b(n-1) \leq \sigma(n-1)$. We will choose $r(n)$ so that $b(n)$ also
satisfies the desired bounds.
If $b(n-1) > \sigma(n)/2$, let $r(n) =1$, so $b(n) = b(n-1)$ and the lower bound is
obviously satisfied. For the upper bound, $b(n) = b(n-1) \leq \sigma(n-1) \leq
\sigma(n)$ by Condition 1.
Otherwise, we have $b(n-1) \leq \sigma(n)/2$. Let $r(n) = r(n-1)+1$. By Lemma \ref{lem:
Delta r(n) = 1 -> growth =2}, $b(n) = 2b(n-1) \leq \sigma(n)$. Also, $b(n) = 2 b(n-1) >
\sigma(n-1) \geq \sigma(n)/2$ by Condition 4.
\end{proof}
\end{bigthm}
Examples \ref{eg: exp growth}, \ref{eg: lin growth} and \ref{eg: log growth} show the
$b(n)$ given by the above construction for $\sigma(n) = \sqrt{3}^{\, n}, \ \sigma(n)
=n,$ and $\sigma(n) = 2 \log_2 n$ respectively. The conditions on $\sigma(n)$ are mild.
The first two conditions reflect basic properties of the growth of $b(n)$. The last two
say that $\sigma(n)$ does not more than double in either the long term or the short term
respectively. Conditions 1--3 are necessary (by Definition \ref{defn: vrmFs} and
Proposition \ref{prop: max growth 2 n-1}). Condition 4 is only sufficient and could be
weakened. We note three common classes of sequences that can be $\sigma(n)$.
\begin{cor}\label{cor: sigma models}
Let $\gamma \in \bR$. The following sequences satisfy the hypotheses of Theorem
\ref{thm: sigma approx}:
\begin{enumerate}
\item $\sigma(n) = \gamma^n \ (1 \leq \gamma < 2)$;
\item $\sigma(n) = n^{\gamma} \ (\gamma \geq 0)$;
\item $\sigma(n) = \log_{\gamma} n \ (\gamma > 1)$.
\end{enumerate}
\end{cor}
Suppose $\sigma(n)$ satisfies the conditions of Theorem \ref{thm: sigma approx} and
$\sigma(n) \to \infty$. If we allow greater oscillation from $b(n)$, we can construct
uncountably many $r(n)$-bonacci sequences that grow at the same rate as $\sigma(n)$.
\begin{cor}
If $\sigma(n)$ is a sequence that satisfies the hypotheses of Theorem \ref{thm: sigma
approx} and $\lim_{n \to \infty} \sigma(n) = \infty$, then there are uncountably many
$r(n)$-bonacci sequences $b(n)$ such that for all $n$ sufficiently large,
\[
\sigma(n)/4 < b(n) \leq \sigma(n).
\]
\begin{proof}
The details of the proof are essentially the same as in Theorem \ref{thm: sigma approx}.
Suppose that we have defined the sequence up to $b(n-1)$. If $b(n-1) > \sigma(n)/2$,
let $r(n) = 1$. If $b(n-1) \leq \sigma(n)/4$, let $r(n) = r(n-1)+1$. The interesting
case is when $\sigma(n)/4 < b(n-1) \leq \sigma(n)/2$. Either of the choices $r(n) = 1$
or $r(n) = r(n-1) + 1$ will result in a $b(n)$ that satisfies the desired bounds. Since
$\sigma(n) \to \infty$, there will be countably many $n$ where we have to make a choice.
\end{proof}
\end{cor}
We now turn to the question of asymptotic limits of $b(n)$. The possible limits for the
short-term growth of $b(n)$, that is the sequence $(b(n)/ b(n-1))$, are restricted. One
possible limit is $\alpha_r$, the growth rate of the $r$-bonacci numbers.
\begin{lem}\label{lem: r(n) econst => r-bon}
If $\lim_{n \to \infty} r(n) = r$, then
\[
\lim_{n \to \infty} \frac{b(n)}{ b(n-1)} = \alpha_r.
\]
\begin{proof}
For $n$ sufficiently large, $b(n)$ satisfies the $r$-boncacci recursion or is eventually
constant.
\end{proof}
\end{lem}
If $r(n)$ is not eventually constant, the only possible limit for the short-term growth
is 2.
\begin{lem}\label{lem: b(n)/b(n-1) = 2}
If the sequence $(b(n)/ b(n-1))$ converges and $r(n)$ is not eventually constant, then
\[
\lim_{n \to \infty} b(n)/{ b(n-1)} = 2.
\]
\begin{proof}
Suppose $ \limsup_{n \to \infty} {b(n)}/{b(n-1)} < 2$. By Corollary \ref{cor: lim sup
growth < 2 -> r(n) const}, $\lim_{n \to \infty} r(n) = r$ for some $ r \in \bZ^+$,
contrary to assumption. Thus, $ \limsup_{n \to \infty} {b(n)}/{b(n-1)} \geq 2$. By Lemma
\ref{lem: lim inf growth <= 2}, $ \liminf_{n \to \infty} {b(n)}/{b(n-1)} \leq 2.$
Therefore, the only possible limit for $(b(n)/ b(n-1))$ is 2.
\end{proof}
\end{lem}
It is known that $ \alpha_r \to 2$ \cite{S74}. Hence, if the short-term growth rate of
$b(n)$ converges, it converges to some $\alpha_r$, or the limiting value of the
$\alpha_r$. This restriction on short-term growth leads to a restriction on long-term
growth. Particularly, $b(n)$ can converge asymptotically to a restricted class of
sequences. Although $b(n)$ can grow at the same rate as a wide variety of sequences,
$b(n)$ is a good approximation of a limited class of sequences. While $b(n)$ may grow at
the same rate overall as some $\sigma(n)$, in general $b(n)$ oscillates a great deal.
For instance, the sequences constructed by Theorem \ref{thm: sigma approx} oscillate
between $\sigma(n)/2$ and $\sigma(n)$. This oscillation severely restricts the possible
asymptotic limits of $b(n)$.
\begin{bigthm}\label{thm: growth restrictions}
Let $\sigma(n)$ be a sequence of real numbers such that $\lim_{n \to \infty } \sigma(n)
/ \sigma(n - 1) $ exists and is non-zero. If
\[
\lim_{n \to \infty } \frac {b(n) }{ \sigma(n)} = L
\]
with $0 < L < \infty$, then
\[
\lim_{n \to \infty } \frac{\sigma(n)}{ \sigma(n - 1)} =2 , \quad \text{ or } \quad
\lim_{n \to \infty } \frac{\sigma(n)}{ \sigma(n - 1)} = \alpha_r
\]
for some $r \geq 1$ and $r(n) = r$ for all $n$ sufficiently large.
\begin{proof}
A simple computation gives
\[
\frac {b(n) }{ \sigma(n)} =
\frac {b(n)}{ b(n-1)} \, \frac {b(n-1) }{\sigma(n-1)} \, \frac{\sigma(n-1)}{\sigma(n)}.
\]
{Taking limits we find that}
\begin{align*}
L = \left( \lim_{n \to \infty} \frac {b(n)}{ b(n-1)} \right)
&(L)
\left(\lim_{n \to \infty}\frac{\sigma(n-1)}{\sigma(n)} \right) \\
\lim_{n \to \infty}\frac{\sigma(n)}{\sigma(n-1)} &= \lim_{n \to \infty} \frac {b(n)}{
b(n-1)}.
\end{align*}
The Theorem follows from Lemmas \ref{lem: r(n) econst => r-bon} and \ref{lem:
b(n)/b(n-1) = 2}.
\end{proof}
\end{bigthm}
\section{Estimates on Growth} \label{sect: Estimates}
In this section, we derive estimates for $b(n)$ in terms of $r(n)$. We gvie a technique
to iteratively compute estimates. We recall how one determines the growth rate of
$r$-bonacci sequences. We generalize this technique to cover $r(n)$-bonacci sequences.
We find upper and lower bounds for the short-term growth of $r(n)$-bonacci numbers. We
use these bounds to study long-term growth. We give upper and lower bounds for $b(n)$
that depend only on $r(1), \dots, r(n)$, and not the previous $b(k)$. As an application
of our estimates, we show that the Narayana-Zidek-Capell numbers converge
asymptotically. Throughout this section, let $b(n)$ be a variable-$r$ meta-Fibonacci
sequence generated by $r(n)$.
We begin by outlining how one shows that the short-term growth rate of the Fibonacci
numbers converges to $\alpha_2$. Let $\alpha_2(n) = f_n/f_{n-1}$. By the defining
recursion of $f_n$,
\[
\frac{f_n}{f_{n-1}} = 1 + \frac{f_{n-2}}{f_{n-1}}.
\]
We can rewrite this equation in terms of $\alpha_2(n)$:
\[
\alpha_2(n) = 1 + \frac{1}{\alpha_2(n-1)}.
\]
Let $n \to \infty$. It follows that $\alpha_2(n) \to (1 + \sqrt{5})/{2} = \alpha_2$. A
similar argument works for the $r$-bonacci numbers. However, to show convergence we use
that the order of the recursion is constant.
Now consider an $r(n)$-bonacci sequence $b(n)$. Fix $n$ such that $r(n)
> 1$. We can start in the same manner:
\begin{equation}\label{eq: b(n)/b(n-1)}
\frac{b(n)}{b(n-1)} = 1 + \sum_{k=2}^{r(n)} \frac{b(n -k)}{b(n-1)}.
\end{equation}
In general, the ratios do not converge, but we can use \eqref{eq: b(n)/b(n-1)} to
estimate the growth of $b(n)$. It is useful to write the terms on the right-hand side
as telescoping products:
\begin{equation}
\frac{b(n)}{b(n-1)} = 1 + \sum_{k=2}^{r(n)}
\prod_{j=1}^{k-1} \frac{b(n -j - 1)}{b(n-j)}.
\end{equation}
Notice that we have expressed the ratio $b(n)/b(n-1)$ in terms of the reciprocal of the
ratio of the previous $b(n-j)/b(n-j - 1)$. F. Dubeau used a similar fact in his study of
the growth rate of the $r$-bonacci numbers $(\alpha_r)$ \cite{Du89}. Generalizing
Dubeau's argument, we can use this equation to obtain upper bounds from lower bounds and
vice versa.
\begin{lem} \label{lem: swap bounds}
If for some $n >1$, we have $r(n) > 1$ and
\[
\lambda(i) \leq \frac{b(i)}{b(i-1)} \leq \upsilon(i) ,
\]
for $i = n - r(n), \dots, n-1,$ then
\[
1 + \sum_{k=2}^{r(n)} \prod_{j=1}^{k-1}
\frac{1}{\upsilon(n-j)}
\leq \frac{b(n)}{b(n-1)} \leq
1 + \sum_{k=2}^{r(n)} \prod_{j=1}^{k-1} \frac{1}{\lambda(n-j)} .
\]
\end{lem}
Our objective now is to find explicit upper and lower bounds for $b(n)/b(n-1)$. The
following lemma is the basis for many of our other estimates. We relate the short-term
growth of $b(n)$ to $r(n)$.
\begin{lem} \label{lem: b(n) <= r(n)}
For all $n \geq 1 $,
\[
\frac{b(n)}{b(n-1)} \leq r(n).
\]
\begin{proof}
By definition,
\begin{align*}
b(n) &= \sum_{k=1}^{r(n)} b(n-k) \\
&\leq \sum_{k=1}^{r(n)} b(n-1) \qquad \text{since the $b(n)$ are
non-increasing,}\\
&= r(n) \, b(n-1).
\end{align*}
\end{proof}
\end{lem}
The above estimate is sharp. We can let $r(1) = \cdots = r(n-1) = 1$ and $r(n) = n$ for
any $n > 1$. Then $b(1) = \cdots = b(n-1) = 1$, and $b(n) = n $, so $b(n)/b(n-1) = n =
r(n)$. From the above Lemma, it follows that $b(n) \leq \prod_{k=1}^{n} r(k)$. Which
implies $b(n) \leq n!$. Although, from Lemma \ref{prop: max growth 2 n-1} we know in
fact that $b(n) \leq 2^{n-1}$. Therefore, while Lemma \ref{lem: b(n) <= r(n)} gives a
sharp estimate of the short-term growth of $b(n)$, in the long term it is highly
inaccurate. However, it is good enough for our purposes. We give a lower bound for
$b(n)/b(n-1)$, which depends only on $r(n-1)$.
\begin{lem} \label{lem: b(n)/b(n-1) geq 1 + 1/r(n-1)}
If $r(n) >1$, then
\[
\frac{b(n)}{b(n-1)} \geq 1 + \frac{ 1}{r(n-1)}.
\]
\begin{proof} \label{lem: b(n)/b(n-1) > 1 +1/r(n-1)}
Since $r(n) > 1$, we can combine Lemmas \ref{lem: swap bounds} and \ref{lem: b(n) <=
r(n)} to get
\[
\frac{b(n)}{b(n-1)} \geq
1 + \sum_{k=2}^{r(n)} \prod_{j=1}^{k-1} \frac{1}{r(n-j)} \geq
1 + \frac{1}{r(n-1)}.
\]
\end{proof}
\end{lem}
We use Lemma \ref{lem: b(n)/b(n-1) geq 1 + 1/r(n-1)} to obtain a new upper bound for
growth.
\begin{lem}
If $r(k) > 1$ for $k = n-r(n), \dots, n$, then
\[
\frac{b(n)}{b(n-1)} \leq
1 + \sum_{k=2}^{r(n)} \prod_{j=1}^{k-1}
\frac{r(n-j)}{1+ r(n-j)} < r(n).
\]
\begin{proof}
Combine Lemmas \ref{lem: b(n)/b(n-1) geq 1 + 1/r(n-1)} and \ref{lem: swap bounds}.
\end{proof}
\end{lem}
Note that we have obtained a better estimate than we started with. One could certainly
find even better estimates. One method is to continue to use Lemma \ref{lem: swap
bounds} to iterate the bounds. Dubeau used a similar technique to good effect in his
study of the $\alpha_r$ \cite{Du89}.
\begin{defn}
For $n \geq 1$, define
\[
\rho(n) = 1 + \frac{1}{r(n-1)} \quad \text{if } r(n) > 1,
\]
and $\rho(n)= 1$ otherwise.
\end{defn}
We give an estimate for $b(n)$ that depends only on $\rho(k)$ ($k \leq n$), that is
$r(1), \dots, r(n)$.
\begin{thm}\label{thm: upper/lower bounds}
For all $n \geq 1$,
\[
\prod_{k=1}^{n} \rho(k) \leq b(n)
\leq 1 + \sum_{k=2}^{r(n)} \prod_{j=1}^{k-1}
\frac{1}{\rho(k)}.
\]
\begin{proof}
Since $b(0) =1$, $b(n) = b(n)/b(0)$. So we can write $b(n)$ as a telescoping product:
\[
b(n) = \prod_{k=1}^{n} \frac{b(k)}{b(k-1)} .
\]
It follows from Lemma \ref{lem: b(n)/b(n-1) geq 1 + 1/r(n-1)} that $\rho(k) \leq
{b(k)}/{b(k-1)}$ for all $k$. Applying Lemma \ref{lem: swap bounds} gives the upper
bound.
\end{proof}
\end{thm}
In the late 1960s, T. V. Narayana, J. Zidek and P. Capell studied the combinatorics of
knock-out tournaments. The Narayana-Zidek-Capell sequence (\seqnum{A002083}) gives the
number of knock-out tournaments with $n$ players \cite{CN70}. According to G. Kreweras,
this sequence was originally discovered by M. A. Stern in 1838 \cite{K83}. This sequence
is an $r(n)$-bonacci sequence. As an application of the above techniques, we solve an
open problem. We show that the Narayana-Zidek-Capell sequence converges asymptotically.
We start with a fairly weak upper bound; the ratios of successive terms of the sequence
are bounded above by 2. We obtain a lower bound that is sufficiently strong to show
asymptotic convergence.
\begin{example}[The Narayana-Zidek-Capell sequence]
Let $r(0) = r(1) =1$, and $r(n) = \lfloor n /2 \rfloor, \ n >1$:
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11\\
\hline
r(n) & 1 & 1 & 1 & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 5 & 5\\
\hline
a(n) & 1 & 1 & 1 & 1 & 2 & 3 & 6 & 11 & 22 & 42 & 84 & 165 \\
\hline
\end{array}
\]
\emph{Remark.} It is unconventional to define $a(0)$.
\end{example}
The sequence satisfies the recursion relation:
\begin{equation}\label{eq: NZC recursion}
a(2n)=2 \, a(2n-1),\quad a(2n+1)=2 \, a(2n)-a(n), \quad n > 1.
\end{equation}
Narayana and Capell found upper and lower bounds for $a(n)$ \cite[p. 108]{CN70}:
\begin{equation}\label{eq: NZC est}
0.625 <
\frac{a(n)}{2^{n-3}} <
0.64453125,
\quad n \geq 11.
\end{equation}
G. McGarvey conjectured that $ \liminf_{n \to \infty}
a(n)/2^{n-3} \approx 0.633368$ (\seqnum{A002083}):
\[
%\label{eq: NZC a(n)/2 n-3}
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
n & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13\\
\hline
a(n)/2^{n-3} & 2 & 1 & 1 & .75& .75& .6875 & .6875 & .65625 & .65625 & .64453 & .64453& .63867\\
\hline
\end{array}
\]
We show that $ a(n) \sim c 2^{n-3}$ for some $c
>0$. We give an explicit estimate for convergence, so the rate of convergence is
computable. First, we prove a lower bound for the short-term growth when the index is
odd.
\begin{lem} \label{lem: lower bound for NZC ratio}
For all $n \geq 2$,
\[
\frac{a(2n+1)}{a(2n)} \geq 2 -
\frac{1}{2^{ n -1}}.
\]
\begin{proof}
From the recursion relation \eqref{eq: NZC recursion}, it is immediate that ${a(k)}/
{a(k-1)} \leq 2$ for all $k \geq 1$. We apply Lemma \ref{lem: swap bounds} to obtain
\[
\frac{a(2n+1)}{a(2n)} \geq
1 + \sum_{k=2}^{n} \prod_{j=1}^{k-1} \frac{1}{2}
= \sum_{i=0}^{n-1} \frac{1}{2^i}
= 2 - \frac{1}{2^{n-1}}.
\]
\end{proof}
\end{lem}
\begin{thm}
The Narayana-Zidek-Capell sequence converges asymptotically to $c 2^{n-3} $ for some
positive real number $c$.
\begin{proof}
It suffices to show that $a(n)/{2^{n}}$ converges to a non-zero limit. Write $a(n)/2^n$
as a telescoping product:
\[
\frac{a(n)}{2^n} = \prod_{k=1}^{n} \frac{1}{2}
\frac{a(k)}{a(k-1)}.
\]
We use the comparison test to show that the product converges. From the recursion, it is clear that $a(n)/2^n \leq 1$ for all
$n$. So, we need only consider lower bounds. If $k$ is even, then $a(k)/a(k-1) = 2$.
Thus, only the terms with odd indices affect the product. We can write
\[
\frac{a(n)}{2^n} = \prod_{k= 2}^{\lfloor n/2 \rfloor} \frac{1}{2}
\frac{a(2k+1)}{a(2k)},
\]
since $a(3)/a(2) = a(1)/a(0) = 1 $. Hence, $a(2n )/2^{2n} = a(2n+1)/2^{2n+1}$, and it
suffices to consider only the odd terms of the product:
\[
\frac{a(2n+1)}{2^{2n+1}} = \prod_{k=2}^{ n} \frac{1}{2}
\frac{a(2k+1)}{a(2k)}.
\]
By Lemma \ref{lem: lower bound for NZC ratio},
\[
\frac{a(2n+1)}{2^{2n+1}} \geq \prod_{k=2}^{ n}
\frac{1}{2} \left( 2 - \frac{1}{2^{k-1}} \right)
= \prod_{k=2}^{n}
\left( 1 - \frac{1}{2^{k}} \right).
\]
The product on the right-hand side (\seqnum{A048651}) converges as $n \to \infty$.
\end{proof}
\end{thm}
\section{A Generalization} \label{sect: Generalization}
We define a generalization of $b(n)$, which is a double sequence. This generalization
allows us to remove the restriction that $r(n) \leq n$. It also allows us to pick
different initial conditions for our sequence. This generalization has applications to
polynomial dynamics.
\begin{defn}\label{defn: ex vrmFs}
We call a double sequence $\beta(n), \ n \in \bZ$, an \emph{extended variable-$r$
meta-Fibonacci sequence} if there exists $r: \bZ \to \bZ^+$ such that for all $n \in
\bZ$,
\[
\beta(n) = \sum_{k=1}^{r(n)} \beta(n-k).
\]
\end{defn}
The author originally discovered $r(n)$-bonacci numbers while studying the dynamics of
complex polynomials \cite{E01, E05}. The generalized return times of polynomials are
extended $r(n)$-bonacci numbers, with $r(n) = 1$ and $\beta(n) = 1$ for $n \leq 0$. Note
that such a $\beta(n)$ is a non-decreasing sequence of positive integers. We give an
example of this type of $\beta(n)$. For fun, we take $r(n)$ as the Fibonacci numbers for
$n > 0$.
\begin{example}\label{eg: dyn seq}
Let $\beta(n) =1 $ and $r(n) = 1$ for $n \leq 0$. Let $r(n) =f_{n+1}$ for $n> 0$:
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
n &-2&-1& 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
\hline
r(n) & 1 & 1 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 \\
\hline
\beta(n) & 1& 1 & 1 & 1 & 2 & 4 & 9 & 20 & 44 & 95 & 202 & 424 \\
\hline
\end{array}
\]
It is left as an exercise to show that $\beta(n) = 2 \beta (n-1) + f_{n-1} - 1$ for $n
>0$.
\end{example}
\begin{rem}
Certain results in this paper, especially Lemma \ref{lem: swap bounds}, used only the
form of the recursion---these results apply immediately to all $\beta(n)$. Provided that
$\beta(n) > 0$ for all $n \in \bZ$, many results in this paper apply to $\beta(n)$,
particularly Lemma \ref{lem: b(n) growth}. We used the fact that $b(n)$ is
non-decreasing in the proof of Lemma \ref{lem: b(n) <= r(n)}. So, all results that
depend on this lemma, require that $\beta(n)$ be non-decreasing. In particular, all
results in Section \ref{sect: Estimates} apply if $\beta(n)$ non-decreasing and
positive. One important difference is that the long-term growth rate of an extended
$r(n)$-bonacci sequence can exceed 2. Therefore, Proposition \ref{prop: max growth 2
n-1}, Lemma \ref{lem: b(n)/b(n-1) = 2} and Theorem \ref{thm: growth restrictions} do not
necessarily apply to extended sequences when we have $r(n)
> n$.
\end{rem}
We can generalize Lemma \ref{lem: lim inf growth <= 2}.
\begin{lem}
Let $\beta(n)$ be an extended variable-$r$ meta-Fibonacci sequence generated by $r(n)$.
If $\liminf_{n \to \infty} \beta(n)/\beta(n-1) > 2$, then $\Delta r(n) \geq 2$ for all
$n$ sufficiently large.
\end{lem}
It is not clear which double sequences $r(n)$ can generate an extended $r(n)$-bonacci
sequence. We do not attempt to give a complete answer to this question. Instead, we
give a class $r(n)$ that work; we require that $r(n)$ be constant for non-positive $n$.
Recall for the Fibonacci numbers, we use $f_{n-2} = f_{n} - f_{n-1}$ to define $f_n$ for
$n \leq 0$. We can define $\beta(n)$ for $n \leq 0$ in an analogous manner. In this
case, a closed form of $\beta(n)$ for $n \leq 0$ can be easily found using standard
techniques.
\begin{prop}\label{prp: ex vrmFs , r(n)=R n < 1}
Fix $R >0$. Let $r: \bZ \to \bZ^+$ such that $r(n) = R$ for all $n \leq 0$. Choose
initial conditions $\beta(0) , \beta(-1), \dots, \beta(1-R) \in \bR$. First, for $n = 0,
-1, -2, \dots$ define
\begin{equation}\label{eq: beta(n) for n < 0}
\beta(n - R) = \beta(n) - \sum_{k=1}^{R-1} \beta(n-k).
\end{equation}
Next, for $n \geq 0$ let
\[
\beta(n) = \sum_{k=1}^{r(n)} \beta(n-k).
\]
Then $\beta(n)$ is an extended variable-$r$ meta-Fibonacci sequence generated by $r(n)$.
\begin{proof}
We need to check that $\beta(n)$ is well defined and satisfies the $r(n)$-bonacci
recursion for all $n \in\bZ$. For $n \leq 0$, note that $\beta(n)$ depends only on
$\beta(n+1), \dots, \beta(n+R)$, which have been previously defined, and \eqref{eq:
beta(n) for n < 0} can be rewritten as the $r(n)$-bonacci recursion. For $n >0$, the
only concern is that we may have $n-r(n) <0$ for some $n$, but then $\beta(n-r(n))$ was
defined in the first step.
\end{proof}
\end{prop}
We give two examples of the above construction.
\begin{example}
Let $r(n) = 2$ for $n \leq 0$ and $r(n) = 2n $ for $n >0$. Choose $\beta(0) = \pi $ and
$\beta(-1) = 1$. Now, we use \eqref{eq: beta(n) for n < 0} to compute $\beta(-2) = \beta
(0) - \beta(-1) = \pi-1 $. Next, compute $\beta(n)$ for $n < -2$. Finally, compute
$\beta(n)$ for $n$ positive.
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
n & - 5& -4&-3 &-2&-1& 0 & 1 & 2 & 3 & 4 \\
\hline
r(n) & 2 & 2& 2& 2 & 2 & 2 & 2 & 4 & 6 & 8 \\
\hline
\beta(n) & -3 \pi +5 & 2 \pi -3 &-\pi+2 & \pi -1 & 1 & \pi & \pi + 1 & 3\pi + 1 & 5\pi +4 & 12\pi + 5 \\
\hline
\end{array}
\]
\end{example}
In the above example, even though the initial conditions are both positive, for $n \leq
-2$, $\beta(n)$ alternates between positive and negative values.
\begin{example}
Let $r(n) = 3$ for $n \leq 0$, and $r(n) = 2n $ for $n >0$. Choose $\beta(0) = 3$,
$\beta(-1) = 2$ and $\beta(-2) = 1$:
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
n & -7 & - 6& -5&-4&-3 &-2&-1& 0 & 1 & 2 & 3 & 4 & 5 & 6 \\
\hline
r(n) & 3 &3 & 3& 3& 3& 3 & 3 & 3 & 2 & 4 & 6 & 8 & 10& 12 \\
\hline
\beta(n) & 2 & -1& 0 &1 &0 & 1& 2 & 3 & 5 & 11 & 22 & 45 & 90 & 179 \\
\hline
\end{array}
\]
\end{example}
Lemma \ref{lem: b(n) growth} does not apply to the above sequence, because not all of
the terms are positive. Note that $\Delta r(3) = 2$, but $\beta(3)/\beta(2) = 2$. Even
worse, $\Delta r(6) = 2$, but $\beta(6)/\beta(5) < 2$.
\section{Acknowledgements}
Jeffrey Shallit was kind enough to point out that the
Narayana-Zidek-Capell sequence (\seqnum{A002083}) can be obtained as an
$r(n)$-bonacci sequence.
I would like to thank the anonymous referee for his useful comments.
\providecommand{\href}[2]{#2}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{\href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}}
\begin{thebibliography}{10}
\bibitem{BH92}
Bodil Branner and John Hubbard, {Iteration of cubic polynomials, part {I}{I}:
Patterns and parapatterns}, {\it Acta Math.} \textbf{169} (1992), 229--325.
\MRhref{MR1194004}{MR 1194004}
\bibitem{CCT}
Joseph Callaghan, John~J. Chew~III, and Stephen~M. Tanny,
On the behavior of a
family of meta-{F}ibonacci sequences, {\it SIAM J. Discrete Math.}
\textbf{18} (2004),
794--824. \MRhref{MR2157827}{MR 2157827}
\bibitem{CN70}
P. Capell and T. V. Narayana,
On knock-out tournaments, {\it Canad. Math. Bull.},
\textbf{13} (1970), 105--109. \MRhref{MR0264997}{MR 0264997}
\bibitem{Cnly89}
{B}.~{W}. Conolly, Meta-{F}ibonacci sequences, ch.~XII of \emph{Fibonacci \&
{L}ucas {N}umbers and the {G}olden {S}ection}, by S. Vajda, pp.~127--138,
{E}llis {H}orwood, 1989. {\MRhref{MR1015938}{MR~1015938}}
\bibitem{DGNW}
R.~Dawson, G.~Gabor, R.~Nowakowski, and D.~Wiens, Random {F}ibonacci-type
sequences, {\it Fibonacci Quart.} \textbf{23} (1985), 169--176. \MRhref{MR797140}{MR 797140}
\bibitem{Du89}
Dubeau, Fran{\c{c}}ois, On {$r$}-generalized {F}ibonacci numbers, {\it Fibonacci
Quart.}, \textbf{27} (1989), 221--229. \MRhref{MR1002065}{MR 1002065}
\bibitem{E01}
Nathaniel~D. Emerson, \emph{Dynamics of polynomials whose {J}ulia set is an area zero
{C}antor set}, Ph. {D}. thesis, University of California Los Angeles, 2001.
\bibitem{E05}
Nathaniel~D. Emerson, Return times of polynomials as meta-{F}ibonacci numbers,
Preprint, August 2005.
\bibitem{G86}
Richard~K. Guy, Some suspiciously simple sequences, {\it Amer. Math. Monthly}
\textbf{93} (1986), 186--190. \MRhref{MR1540817}{MR~1540817}
\bibitem{Hof79}
Douglas~R. Hofstader,
\emph{G{\"o}del, {E}scher, {B}ach: An {E}ternal {G}olden {B}raid},
Basic Books, 1979.
\bibitem{HT93b}
J.~Higham and S.~Tanny,
More well-behaved meta-{F}ibonacci sequences, {\it Congr.
Numer.} \textbf{98} (1993), 3--17. \MRhref{MR1267335}{MR 1267335}
\bibitem{JR05}
Brad Jackson and Frank Ruskey,
Meta-{F}ibonacci sequences, binary trees, and
extremal compact codes, preprint, April 2005.
\bibitem{K83}
G. Kreweras,
Sur quelques probl\`emes relatifs au vote pond\'er\'e, {\it Math. Sci.
Humaines} \textbf{84} (1983), {45--63}. \MRhref{MR0734845}{MR 0734845}
\bibitem{Mal91}
Colin~L. Mallows, Conway's challenge sequence,
{\it Amer. Math. Monthly} \textbf{98}
(1991), 5--20. \MRhref{MR1083608}{MR 1083608}
\bibitem{Miles}
E.~P. {Miles, Jr.}, Generalized {F}ibonacci numbers and associated matrices,
{\it Amer. Math. Monthly}
\textbf{67} (1960), 745--752. \MRhref{MR0123521}{MR 0123521}
\bibitem{S74}
Lawrence Somer, Problem H-197 (and Solution), {\it Fibonacci Quart.}
\textbf{12} (1974), 110--111.
\bibitem{T92}
Stephen M. Tanny, A well-behaved cousin of the Hofstadter sequence,
{\it Discr. Math.}
\textbf{105} (1992), 227--239. \MRhref{MR1180206}{MR 1180206}
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}: Primary 11B37;
Secondary 11B39, 11B99.
\noindent \emph{Keywords:}
Meta-Fibonacci, Hofstadter sequence, Narayana-Zidek-Capell
sequence.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences \seqnum{A000045}, \seqnum{A000073},
\seqnum{A002083}, \seqnum{A004001}, \seqnum{A005185}, \seqnum{A006949} and
\seqnum{A092921}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received September 13 2005;
revised version received March 17 2006.
Published in {\it Journal of Integer Sequences}, March 17 2006.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}