Tribonacci Number

The tribonacci numbers are a generalization of the Fibonacci Numbers defined by $T_1=1$, $T_2=1$, $T_3=2$, and the Recurrence Relation

$$T_n=T_{n-1}+T_{n-2}+T_{n-3}$$ (1)

for $n\geq 4$. The represent the $n=3$ case of the Fibonacci n-Step Number. The first few terms are 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, ... (Sloane's A000073). The ratio of adjacent terms tends to 1.83929, which is the Real Root of $x^4-2x^3+1=0$. The Tribonacci numbers can also be computed using the Generating Function

${1\over 1-z-z^2-z^3}=1+z+2z^2+4z^3+7z^4$
$+13z^5+24z^6+44z^7+81z^8+149z^9+\ldots.\quad$	(2)

An explicit Formula for $T_n$ is also given by

$$\left[{3{\{{\textstyle{1\over 3}}(19\!+\!3\sqrt{33})^{1/3}\!... ...(586+102\sqrt{33})^{2/3}+4-2(586+102\sqrt{33})^{1/3}}}\right],$$ (3)

where $[x]$ denotes the Nint function (Plouffe). The first part of a Numerator is related to the Real root of $x^3-x^2-x-1$, but determination of the Denominator requires an application of the LLL Algorithm. The numbers increase asymptotically to

$$T_n\sim c^n,$$ (4)

where

$$c = ({\textstyle{19\over 27}}+{\textstyle{1\over 9}}\sqrt{33}\,)^{1/3... ...e{19\over 27}}+{\textstyle{1\over 9}}\sqrt{33}\,)^{-1/3}+{\textstyle{1\over 3}}$$

$$= 1.83928675521\ldots$$ (5)

(Plouffe).

See also Fibonacci n-Step Number, Fibonacci Number, Tetranacci Number

References

Plouffe, S. ``Tribonacci Constant.'' http://www.lacim.uqam.ca/piDATA/tribo.txt.

Sloane, N. J. A. Sequence A000073/M1074 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.