Tribonacci NumbersDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/