TOPICS

# Fibonacci n-Step Number

An -step Fibonacci sequence is defined by letting for , , and other terms according to the linear recurrence equation

 (1)

for .

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

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

 OEIS name sequence 1 degenerate 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, ... 2 A000045 Fibonacci number 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 3 A000073 tribonacci number 1, 1, 2, 4, 7, 13, 24, 44, 81, ... 4 A000078 tetranacci number 1, 1, 2, 4, 8, 15, 29, 56, 108, ... 5 A001591 pentanacci number 1, 1, 2, 4, 8, 16, 31, 61, 120, ... 6 A001592 hexanacci number 1, 1, 2, 4, 8, 16, 32, 63, 125, ... 7 A066178 heptanacci number 1, 1, 2, 4, 8, 16, 32, 64, 127, ...

The probability that no runs of consecutive tails will occur in coin tosses is given by , where is a Fibonacci -step number.

The limit is called the -anacci constant and given by solving

 (2)

or equivalently

 (3)

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

An exact formula for the th -anacci number can be given by

 (4)

where is a polynomial root.

Another formula is given in terms of the roots of . This has the general form

 (5)

where is a polynomial in the , the first few of which are

 (6) (7) (8) (9)

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

 (10)

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

If , equation (9) reduces to

 (11)
 (12)

giving solutions

 (13)

The ratio is therefore

 (14)

which is the golden ratio, as expected.

The analytic solutions for , 2, ... are given by

 (15) (16) (17) (18) (19)

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 .

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

More things to try:

## References

Fraenkel, A. S. "Systems of Numeration." Amer. Math. Monthly 92, 105-114, 1985.Noe, T. D. and Post, J. V. "Primes in Fibonacci -step and Lucas -Step Sequences." J. Integer Seq. 8, Article 05.4.4, 2005. http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Noe/noe5.html.Sloane, 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. https://mathworld.wolfram.com/Fibonaccin-StepNumber.html