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 defined by
The sequence begins
The closed-form formula for the Fibonacci sequence involved the roots of the polynomial It is reasonable to expect that the analogous formula for the tribonacci sequence involves the polynomial and this is indeed the case. This polynomial has one real root
called the tribonacci constant. The other two roots are complex conjugates.
Let be the complex roots of Then
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 so the hard part of the proof is verifying that the right side is for 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:
The proof is similar as well:
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
This is because the other two roots and of are complex numbers whose absolute value is so their powers go to as .
The tribonacci sequence counts many combinatorial objects that are similar to the ones that the Fibonacci sequence counts.
Let and be the number of compositions of with no part larger than Here a composition of a positive integer is a sum of positive integers equal to where "order matters."
For instance, because
It is enough to show that for since and agree for But this is immediate: there are compositions ending in compositions ending in and compositions ending in because subtracting the last number from a composition of leaves a composition of or respectively.