TOPICS
Search

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

 F_k^((n))=sum_(i=1)^nF_(k-i)^((n))
(1)

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.

nOEISnamesequence
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

 x^n(2-x)=1,
(2)

or equivalently

 P(x)=x^n-x^(n-1)-x^(n-2)-...-x-1=0,
(3)

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

 F_k^((n))=nint((r^(k-1)(r-1))/((n+1)r-2n)),
(4)

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

 F_k^((n))=sum_(i=1)^n(x_i^k)/(Q_n(x_i)),
(5)

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

Q_2(x)=2x-1
(6)
Q_3(x)=-x^2+4x-1
(7)
Q_4(x)=-x^3+6x-1
(8)
Q_5(x)=-x^4+x^2+8x-1.
(9)

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

 -1,2 
-1,4,-1 
-1,6,0,-1 
-1,8,1,0,-1 
-1,10,2,1,0,-1 
-1,12,3,2,1,0,-1
(10)

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

If n=2, equation (9) reduces to

 x^2(2-x)=1
(11)
 x^3-2x^2+1=(x-1)(x^2-x-1)=0,
(12)

giving solutions

 x=1,1/2(1+/-sqrt(5)).
(13)

The ratio is therefore

 x=1/2(1+sqrt(5))=phi=1.618...,
(14)

which is the golden ratio, as expected.

FibonacciNStepLimits

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

x_1=1
(15)
x_2=1/2(1+sqrt(5))
(16)
x_3=1/3[1+(19-3sqrt(33))^(1/3)+(19+3sqrt(33))^(1/3)]
(17)
=(x^3-x^2-x-1)_1
(18)
x_4=(x^4-x^3-x^2-x-1)_2
(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 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

References

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. 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

Subject classifications