Tribonacci Sequence

The tribonacci sequence is a generalization of the Fibonacci sequence where each term is the sum of the three preceding terms.

The tribonacci sequence is a sequence of integers $T_n$ defined by

$\begin{array}{c}&T_0 = 0,&T_1=T_2=1, &T_n = T_{n-1} + T_{n-2}+ T_{n-3} \, \, (n \ge 3). \end{array}$

The sequence begins $0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, \dots .$

The closed-form formula for the Fibonacci sequence involved the roots of the polynomial $x^2-x-1.$ It is reasonable to expect that the analogous formula for the tribonacci sequence involves the polynomial $x^3-x^2-x-1,$ and this is indeed the case. This polynomial has one real root

$t = \frac13\left(1+\sqrt[3]{19+3\sqrt{33}} + \sqrt[3]{19-3\sqrt{33}} \right) \approx 1.83929,$

called the tribonacci constant. The other two roots are complex conjugates.

Let $\alpha,\beta,\gamma$ be the complex roots of $x^3-x^2-x-1.$ Then

$T_n = \frac{\alpha^n}{-\alpha^2+4\alpha-1} + \frac{\beta^n}{-\beta^2+4\beta-1} + \frac{\gamma^n}{-\gamma^2+4\gamma-1}.$

As with the Fibonacci numbers, the formula is more difficult to produce than to prove. It can be derived from general results on linear recurrence relations, but it can be proved from first principles using induction. It is immediately clear from the form of the formula that the right side satisfies the same recurrence as $T_n,$ so the hard part of the proof is verifying that the right side is $0,1,1$ for $n=0,1,2,$ respectively. This can be accomplished via a tedious computation with symmetric polynomials.

The generating function for the tribonacci numbers is quite similar to the generating function for the Fibonacci numbers:

$\displaystyle\sum _{ n=0 }^{ \infty }{ { T }_{ n } } { x }^{ n }=\frac { x }{ 1-x-x^2-x^3}.$

The proof is similar as well:

$\begin{aligned} \big(1-x-x^2-x^3\big)\left(\sum_{n=0}^\infty T_n x^n\right) &= T_0 + \big(T_1-T_0\big) x +\big(T_2-T_1-T_0\big)x^2 + \sum_{n=3}^\infty \big(T_n-T_{n-1}-T_{n-2}-T_{n-3}\big) x^n \\ &= x.\ _\square \end{aligned}$

Just as the ratios of consecutive terms of the Fibonacci sequence approach the golden ratio, the ratios of consecutive terms of the tribonacci sequence approach the tribonacci constant

$t = \frac { 1 }{ 3 } \left( 1+\sqrt [ 3 ]{ 19+3\sqrt { 33 } } +\sqrt [ 3 ]{ 19-3\sqrt { 33 } } \right).$

This is because the other two roots $\beta$ and $\gamma$ of $x^3-x^2-x-1$ are complex numbers whose absolute value is $\frac1{\sqrt{t}} < 1,$ so their $n^\text{th}$ powers go to $0$ as $n\to\infty$.

That is,

$\lim _{ n\rightarrow \infty }{ \frac { { T }_{ n+1 } }{ { T }_{ n } } } = t = \frac { 1 }{ 3 } \left( 1+\sqrt [ 3 ]{ 19+3\sqrt { 33 } } +\sqrt [ 3 ]{ 19-3\sqrt { 33 } } \right).$

The tribonacci sequence counts many combinatorial objects that are similar to the ones that the Fibonacci sequence counts.

Let $C_0 = 0, C_1 = 1,$ and $C_n$ $(n\ge 2)$ be the number of compositions of $n-1$ with no part larger than $3.$ Here a composition of a positive integer $k$ is a sum of positive integers equal to $k,$ where "order matters."

For instance, $C_5 = 7$ because

$4 = 1+1+1+1=1+1+2=1+2+1=2+1+1=2+2=1+3=3+1.$

Show that $C_n = T_n.$

---

It is enough to show that $C_n = C_{n-1}+C_{n-2}+C_{n-3}$ for $n \ge 3,$ since $C_n$ and $T_n$ agree for $n = 0,1,2.$ But this is immediate: there are $C_{n-1}$ compositions ending in $1,$ $C_{n-2}$ compositions ending in $2,$ and $C_{n-3}$ compositions ending in $3,$ because subtracting the last number from a composition of $n-1$ leaves a composition of $n-2,n-3,$ or $n-4,$ respectively. $_\square$