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 .