Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Tribonacci Numbers


Date: 11/11/2000 at 22:11:39
From: Anonymous
Subject: Implicit formula for the nth Tribonacci number

Is there an implicit formula to calculate the nth Tribonacci number? 
Also, is there a formula to find the sum of the first n Tribonacci 
numbers? The only thing I know about this sequence is that each term 
starting with the fourth is the sum of the previous three terms:
 
     1, 1, 1, 3, 5, 9, 17, ...

Thank you for your help.


Date: 11/12/2000 at 06:34:17
From: Doctor Mitteldorf
Subject: Re: Implicit formula for the nth Tribonacci number

If you haven't already done so, you can start by working out the 
corresponding problem for ordinary Fibonacci numbers. Read about it 
here:

   Z Transforms and the Fibonacci Sequence
   http://mathforum.org/dr.math/problems/karen4.20.98.html   

The procedure for Tribonacci numbers should be similar, except that 
the generator is cubic instead of quadratic.

I don't have a solution for you, but I have a few thoughts that might 
point in a direction of progress on the problem.

In matrix terms, you can start with the initial triple

     [1]
     [1]
     [1]

and transform it with the matrix:

     [ 0  1  0 ]
     [ 0  0  1 ] = R
     [ 1  1  1 ]

to get the next (overlapping) triple

     [1]
     [1]
     [3]

Thereafter, continuing to multiply by the matrix R gives you 
succeeding terms in the sequence. I'm not sure what to do with this, 
but it is, perhaps, a lead.

There's a relation between this problem and the cubic equation

     r^3 = r^2 + r + 1

If the sequence tends for high n toward a constant ratio from one term 
to the next, then the ratio r must obey this equation. And even at low 
n, the equation can be interpreted as an operator or matrix equation 
that relates each triple of terms to the next triple.  

Based on analogy with the Fibonacci formula, I think you might be able 
to come up with a formula for the nth Tribonacci as a linear 
combination

     a(r1)^n + b(r2)^n + c(r3)^n

where a, b and c are constants that can be determined by trying the 
formula out on three different n values. r1, r2, and r3 are also 
unknowns, but I have a feeling that they are the three roots of the 
cubic equation above.

Once you've found a solution in this form, it is easy to sum the 3 
geometric series to find the sum of the first n Tribonacci numbers. It 
also should be possible to prove by induction that the formula works.

This gives you some leads to try - please write back and let me know 
if you make any further progress.

- Doctor Mitteldorf, The Math Forum
  http://mathforum.org/dr.math/   


Date: 11/13/2000 at 11:00:36
From: Doctor Anthony
Subject: Re: Implicit formula for the nth Tribonacci number

The difference equation is 

     u(n+3) = u(n+2) + u(n+1) + u(n)
     u(n+3) - u(n+2) - u(n+1) - u(n) = 0

The solution depends upon the solution of the auxiliary equation

     x^3 - x^2 - x - 1 = 0

This cubic has one real and two complex roots:

     x = 1.8393
     x = -0.4196 +- 0.60629i

Call these roots a and  b +- i*c.

Then convert the complex roots into r, theta form. Call them R,@. The 
solution of the difference equation is

     u(n) = A*a^n + R^n[B*cos(n@) + C*sin(n@)]

From here you have to use the known values of u(1), u(2), u(3) to find 
the values of A, B and C.

The expression for the nth term will be very complicated indeed. You 
probably know that for the Fibonacci series the nth term is

              1     [1+sqrt(5)]^n      1    [1-sqrt(5)]^n
     u(n) = ------- ------------- - ------- -------------
            sqrt(5)      2^n        sqrt(5)      2^n

so you will understand that few people wish to struggle on for a 
similar expression for the Tribonacci series.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/   


Date: 11/13/2000 at 11:24:55
From: Doctor Rob
Subject: Re: Implicit formula for the nth Tribonacci number

Thanks for writing to Ask Dr. Math.

Yes, there is such a formula. You start by finding the three roots of 
the cubic equation

     x^3 - x^2 - x - 1 = 0

Call them A, B and C. One is a real number and the other two are 
complex conjugates. The real root is

     A = (1+[19-3*33^(1/2)]^[1/3]+[19+3*33^(1/2)]^[1/3])/2

The complex ones involve (-1+-i*3^[1/2])/2, as well as cube roots as 
appearing in the formula for A.

Then, if T(n) is the n-th Tribonacci number:

     T(1) = T(2) = T(3) = 1
     T(n+1) = T(n) + T(n-1) + T(n-2)  for n >= 3

An explicit formula for T(n) has the form

     T(n) = r*A^n + s*B^n + t*C^n

for constants r, s, and t which you can determine from the initial 
conditions:

     T(1) = 1 = r*A + s*B + t*C,
     T(2) = 1 = r*A^2 + s*B^2 + t*C^2,
     T(3) = 1 = r*A^3 + s*B^3 + t*C^3.

This is a set of three linear equations in r, s and t, which you can 
solve to find the values of r, s and t in the above formula. You end 
up with complicated combinations of (19+-3*33^[1/2])^(1/3) and 
(-1+-i*3^[1/2])/2. Massive simplification is possible. In fact, r, s 
and t turn out to be the three roots of the cubic equation

     11*x^3 + 11*x^2 + x - 1 = 0

The real one is

     r = (-11+[847-33*33^(1/2)]^[1/3]+[847+33*33^(1/2)]^[1/3])/33

To find the sum of the first n Tribonacci numbers, you will get a 
similar formula.

     S(n) = T(1) + T(2) + ... + T(n)
     S(0) = 0
     S(1) = 1
     S(2) = 2
     S(3) = 3

You'll have the explicit formula

     S(n) = r*(A^(n+1)-A)/(A-1) + s*(B^(n+1)-B)/(B-1) + 
            t*(C^(n+1)-C)/(C-1)

because of the formula for the sum of a geometric series, applied to 
each of the three terms of the formula for T(n).

It's messier than the Fibonacci case, but all the elements are 
analogous.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
College Number Theory
High School Fibonacci Sequence/Golden Ratio
High School Number Theory
High School Sequences, Series

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/