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
starting with the fourth is the sum of the previous three terms:

1, 1, 1, 3, 5, 9, 17, ...

```

```
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
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

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.

[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/
```

```Date: 11/13/2016 at 13:03:22
From: David
Subject: Nth Tribonacci number

I believe this formula of Doctor Rob's, above, is incorrect:

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

The last number should be a 3, not a 2; so the correct formula for the
Tribonacci number is:

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

The next line says "The complex [roots] involve (-1 +- i*3^[1/2])/2, as
well as cube roots as appearing in the formula for A." I think his
response there may also have a typo, since there is no 2 in the
denominator of the exact forms of the complex solutions provided by
Wolfram|Alpha:

http://www.wolframalpha.com/input/?i=x%5E3+-+x%5E2+-+x+-+1+%3D+0

https://en.wikipedia.org/wiki/Generalizations_of_   Fibonacci_numbers#Tribonacci_numbers

```

```Date: 11/14/2016 at 23:22:37
From: Doctor Peterson
Subject: Re: Nth Tribonacci number

Hi, David.

Checking as you did on Wolfram|Alpha, I think you are right.

Let's see if I can reconstruct Doctor Rob's result and correct it.

He says,

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.

There are several ways to carry out the solution of a cubic, and I can't
be sure which he used. As a quick route to a solution, I'll try the
formula as found here:

http://www.math.vanderbilt.edu/~schectex/courses/cubic/

The solution of ax^3 + bx^2 + cx + d = 0 is

x = {q + [q^2 + (r-p^2)^3]^(1/2)}^(1/3) +
{q - [q^2 + (r-p^2)^3]^(1/2)}^(1/3) + p

where

p = -b/(3a), q = p^3 + (bc - 3ad)/(6a^2), r = c/(3a)

We have a = 1, b = -1, c = -1, d = -1, so we get

p = 1/3, q = 1/27 + 4/6 = 19/27, r = -1/3

x = {(19/27) + [(19/27)^2 + (-1/3-(1/3)^2)^3]^(1/2)}^(1/3) +
{(19/27) - [(19/27)^2 + (-1/3-(1/3)^2)^3]^(1/2)}^(1/3) + (1/3)
= {(19/27) + [361/729 + (-4/9)^3]^(1/2)}^(1/3) +
{(19/27) - [361/729 + (-4/9)^3]^(1/2)}^(1/3) + (1/3)
= {(19/27) + [361/729 + (-64/729)]^(1/2)}^(1/3) +
{(19/27) - [361/729 + (-64/729)]^(1/2)}^(1/3) + (1/3)
= {(19/27) + [297/729]^(1/2)}^(1/3) +
{(19/27) - [297/729]^(1/2)}^(1/3) + (1/3)
= {(19/27) + [33/81]^(1/2)}^(1/3) +
{(19/27) - [33/81]^(1/2)}^(1/3) + (1/3)
= {(19/27) + (1/9) sqrt(33)}^(1/3) +
{(10/27) - (1/9) sqrt(33)}^(1/3) + (1/3)
= {(19/27) + (3/27) sqrt(33)}^(1/3) +
{(10/27) - (3/27) sqrt(33)}^(1/3) + (1/3)
= (1/3){19 + 3 sqrt(33)}^(1/3) +
(1/3){19 - 3 sqrt(33)}^(1/3) + (1/3)
= [{19 + 3 sqrt(33)}^(1/3) + {19 - 3 sqrt(33)}^(1/3) + 1]/3

This is Doctor Rob's value with your correction! And, yes, now I see that

Thank you for these corrections, David. We appreciate your feedback.

- Doctor Peterson, The Math Forum at NCTM

```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search