Fibonacci n-Step Number

A Fibonacci -step number, for a positive integer , is a term of the sequence defined by letting for , , and defining the remaining terms by the linear recurrence equation

for .

For and , the partial sum is

This identity follows by subtracting consecutive weighted sums and applying the recurrence equation.

For , Brown's criterion shows that the -step Fibonacci numbers are complete; every positive integer can be written as a sum of distinct -step Fibonacci numbers. As discussed by Fraenkel (1985), every positive integer has a unique Zeckendorf-like expansion using the terms , , ... and containing no consecutive terms. 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.

For integers and , the probability that no runs of consecutive tails occur in independent fair coin tosses is , where is a Fibonacci -step number.

For , the limit is called the -anacci constant and is given by solving

or equivalently

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 .

For , the -anacci constant also has a geometric interpretation generalizing the golden ratio (Mustonen 2005). Divide a line segment of length 1 into parts of lengths , , ..., so that

Then and

Multiplying by gives the same polynomial equation for as the limiting ratio of adjacent terms. For , this is the usual golden ratio division, while and 4 give the tribonacci constant and tetranacci constant, respectively.

For and , an exact formula for the th -anacci number is

where is the unique real root greater than 1 of , and is the nearest integer function (Dresden and Du 2014, p. 3).

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

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

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

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

If , equation (3) reduces to

giving solutions

The ratio is therefore

which is the golden ratio, as expected.

The analytic solutions for , 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 .