Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.8

A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions

Nathaniel D. Emerson
Department of Mathematics
California State University, Channel Islands
One University Drive
Camarillo, California 93012-8599
USA

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.

(Concerned with sequences A000045 A000073 A002083 A004001 A005185 A006949 and A092921 .)

Received September 13 2005; revised version received March 17 2006. Published in Journal of Integer Sequences March 17 2006.