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 .