info prev up next book cdrom email home

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

\begin{displaymath}
F_k=\sum_{i=1}^k F_{n-i}
\end{displaymath} (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

\begin{displaymath}
x^n(2-x)=1
\end{displaymath} (2)

for $x$ and taking the Real Root $x>1$. If $n=2$, the equation reduces to
\begin{displaymath}
x^2(2-x)=1
\end{displaymath} (3)


\begin{displaymath}
x^3-2x^2+1=(x-1)(x^2-x-1)=0,
\end{displaymath} (4)

giving solutions
\begin{displaymath}
x = 1, {\textstyle{1\over 2}}(1\pm\sqrt{5}\,).
\end{displaymath} (5)

The ratio is therefore
\begin{displaymath}
x={\textstyle{1\over 2}}(1+\sqrt{5}\,)=\phi=1.618\ldots,
\end{displaymath} (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.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-26