Fibonacci n-Step Number

An $n$-step Fibonacci sequence is given by defining $F_k=0$ for $k\leq 0$, $F_1=F_2=1$, $F_3=2$, and

$$F_k=\sum_{i=1}^k F_{n-i}$$ (1)

for $k>3$. The case $n=1$ corresponds to the degenerate 1, 1, 2, 2, 2, 2 ..., $n=2$ to the usual Fibonacci Numbers 1, 1, 2, 3, 5, 8, ... (Sloane's A000045), $n=3$ to the Tribonacci Numbers 1, 1, 2, 4, 7, 13, 24, 44, 81, ... (Sloane's A000073), $n=4$ to the Tetranacci Numbers 1, 1, 2, 4, 8, 15, 29, 56, 108, ... (Sloane's A000078), etc.

The limit $\lim_{k\to\infty} F_k/F_{k-1}$ is given by solving

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

for $x$ and taking the Real Root $x>1$. If $n=2$, the equation reduces to

$$x^2(2-x)=1$$ (3)

$$x^3-2x^2+1=(x-1)(x^2-x-1)=0,$$ (4)

giving solutions

$$x = 1, {\textstyle{1\over 2}}(1\pm\sqrt{5}\,).$$ (5)

The ratio is therefore

$$x={\textstyle{1\over 2}}(1+\sqrt{5}\,)=\phi=1.618\ldots,$$ (6)

which is the Golden Ratio, as expected. Solutions for $n=1$, 2, ... are given numerically by 1, 1.61803, 1.83929, 1.92756, 1.96595, ..., approaching 2 as $n\to\infty$.

See also Fibonacci Number, Tribonacci Number

References

Sloane, N. J. A. Sequences A000045/M0692, A000073/M1074, and A000078/M1108 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.