Fibonacci n-Step Number

An n-step Fibonacci sequence {F_k^((n))}_(k=1)^infty is defined by letting F_k^((n))=0 for k<=0, F_1^((n))=F_2^((n))=1, and other terms according to the linear recurrence equation


for k>2.

Using Brown's criterion, it can be shown that the n-step Fibonacci numbers are complete; that is, every positive number can be written as the sum of distinct n-step Fibonacci numbers. As discussed by Fraenkel (1985), every positive number has a unique Zeckendorf-like expansion as the sum of distinct n-step Fibonacci numbers and that sum does not contain n consecutive n-step Fibonacci numbers. The Zeckendorf-like expansion can be computed using a greedy algorithm.

The first few sequences of n-step Fibonacci numbers are summarized in the table below.

1degenerate1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, ...
2A000045Fibonacci number1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
3A000073tribonacci number1, 1, 2, 4, 7, 13, 24, 44, 81, ...
4A000078tetranacci number1, 1, 2, 4, 8, 15, 29, 56, 108, ...
5A001591pentanacci number1, 1, 2, 4, 8, 16, 31, 61, 120, ...
6A001592hexanacci number1, 1, 2, 4, 8, 16, 32, 63, 125, ...
7A066178heptanacci number1, 1, 2, 4, 8, 16, 32, 64, 127, ...

The probability that no runs of k consecutive tails will occur in n coin tosses is given by F_(n+2)^((k))/2^n, where F_l^((k)) is a Fibonacci k-step number.

The limit lim_(k->infty)F_k^((n))/F_(k-1)^((n)) is called the n-anacci constant and given by solving


or equivalently


for x and then taking the real root x>1. For even n, there are exactly two real roots, one greater than 1 and one less than 1, and for odd n, there is exactly one real root, which is always >=1.

An exact formula for the kth n-anacci number F_k^((n)) can be given by


where r=(x^(-n)+x-2)_([5+(-1)^n]/2) is a polynomial root.

Another formula is given in terms of the n roots x_i of P(x). This has the general form


where Q_n(x) is a polynomial in the x_i, the first few of which are


When arranged as a number triangle corresponding to smallest coefficients first, this gives


(OEIS A118745) for n=2 to 7 with the pattern easily discernible for higher n.

If n=2, equation (9) reduces to


giving solutions


The ratio is therefore


which is the golden ratio, as expected.


The analytic solutions for n=1, 2, ... are given by


and numerically by 1, 1.61803 (OEIS A001622), 1.83929 (OEIS A058265; the tribonacci constant), 1.92756 (OEIS A086088; the tetranacci constant), 1.96595, ..., which approaches 2 as n->infty.

See also

Fibonacci Number, Heptanacci Number, Hexanacci Number, Lucas n-Step Number, Pentanacci Number, Tetranacci Constant, Tetranacci Number, Tribonacci Constant, Tribonacci Number, Zeckendorf Representation

Portions of this entry contributed by Tony Noe

Portions of this entry contributed by Tito Piezas III

Explore with Wolfram|Alpha


Fraenkel, A. S. "Systems of Numeration." Amer. Math. Monthly 92, 105-114, 1985.Noe, T. D. and Post, J. V. "Primes in Fibonacci n-step and Lucas n-Step Sequences." J. Integer Seq. 8, Article 05.4.4, 2005., N. J. A. Sequences A000045/M0692, A000073/M1074, A000078/M1108, A001591, A001622, A046698, A058265, A086088, and A118745 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Fibonacci n-Step Number

Cite this as:

Noe, Tony; Piezas, Tito III; and Weisstein, Eric W. "Fibonacci n-Step Number." From MathWorld--A Wolfram Web Resource.

Subject classifications