Tribonacci numbers

This article needs more work.

Please help by expanding it!

The tribonacci numbers are a homogeneous linear recurrence with constant coefficients of order 3 with signature (0, 0, 1), inspired from the Fibonacci numbers (which are of order 2 with signature (0, 1)), i.e.

     

a 0  =  0; a 1  =  0; a 2  =  1; a n  =  a n  − 1 + a n  − 2 + a n  − 3, n ≥ 3.

A000073 Tribonacci numbers:

a (n) = a (n  −  1) + a (n  −  2) + a (n  −  3)

with

a (0) = a (1) = 0, a (2) = 1

.

{0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744, 755476, 1389537, 2555757, 4700770, 8646064, ...}

Generating function

The generating function of the tribonacci numbers is

G{an , n  ≥  0}(x)  =  x 2 1 − x − x 2 − x 3  =    ∞ ∑   n  = 0    a n x n.

Rewriting the generating function as (which shows the form of the recurrence in the denominator)

G{an , n  ≥  0}(x)  =  (x  − 1) 1 (x  − 1) 3 − (x  − 1) 2 − (x  − 1) 1 − (x  − 1) 0   ,

and setting

x  − 1

to

10 k

, we get the form

(10 k ) 1 (10 k ) 3 − (10 k ) 2 − (10 k ) 1 − (10 k ) 0  =  10 k 10 3k − 10 2k − 10 k − 1  =    ∞ ∑   n  = 0    a n (10 k ) n   , k ≥ 1.

For example, for the first few values of

k

, we have (note that overlapping occurs when tribonacci numbers have more than

k

digits)

k = 1: 10 / 889 = 0.011248593925759280089988751406...

k = 2: 100 / 989899 = 0.00010102040713244482517913443694...

k = 3: 1000 / 998998999 = 0.0000010010020040070130240440811492...

k = 4: 10000 / 999899989999 = 0.000000010001000200040007001300240044...

A variant of the above is

1 (10 k ) 3 − (10 k ) 2 − (10 k ) 1 − (10 k ) 0  =  1 10 3k − 10 2k − 10 k − 1  =    ∞ ∑   n  = 0    a n (10 k ) n  + 1   , k ≥ 1.

For example, for the first few values of

k

, we have (note that overlapping occurs when tribonacci numbers have more than

k

digits)

k = 1: 1 / 889 = 0.0011248593925759280089988751406... (A021893)

k = 2: 1 / 989899 = 0.0000010102040713244482517913443694...

k = 3: 1 / 998998999 = 0.0000000010010020040070130240440811492...

k = 4: 1 / 999899989999 = 0.0000000000010001000200040007001300240044...

Tribonacci triangle

Recurrence relation:

     

T  (n, 0)  =  1; T  (n, n)  =  1, n ≥ 0; T  (n, k )  =  T  (n − 1, k − 1) + T  (n − 1, k) + T  (n − 2, k − 1), n ≥ 2, 0 ≤ k ≤ n.

Tribonacci triangle
(The sums of terms on rising diagonals with slope 1/2 give the tribonacci numbers A000073 (n), n   ≥   2.)

n																												A000129 (n), n   ≥   1.
0														1														1
1													1		1													2
2												1		3		1												5
3											1		5		5		1											12
4										1		7		13		7		1										29
5									1		9		25		25		9		1									70
6								1		11		41		63		41		11		1								169
7							1		13		61		129		129		61		13		1							408
8						1		15		85		231		321		231		85		15		1						985
9					1		17		113		377		681		681		377		113		17		1					2378
10				1		19		145		575		1289		1683		1289		575		145		19		1				5741
11			1		21		181		833		2241		3653		3653		2241		833		181		21		1			13860
			k = 0		1		2		3		4		5		6		7		8		9		10		11

A008288 Square array of Delannoy numbers

D (i, j) (i   ≥   0,  j   ≥   0)

read by antidiagonals. (Concatenated rows of tribonacci triangle.)

{1, 1, 1, 1, 3, 1, 1, 5, 5, 1, 1, 7, 13, 7, 1, 1, 9, 25, 25, 9, 1, 1, 11, 41, 63, 41, 11, 1, 1, 13, 61, 129, 129, 61, 13, 1, 1, 15, 85, 231, 321, 231, 85, 15, 1, 1, 17, 113, 377, 681, 681, 377, 113, 17, 1, 1, 19, 145, 575, 1289, 1683, 1289, 575, 145, 19, 1, 1, 21, 181, 833, 2241, 3653, 3653, ...}

A000129 Pell numbers:

a (0) = 0, a (1) = 1

; for

n > 1, a (n) = 2 a (n  −  1) + a (n  −  2)

.

{0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, 33461, 80782, 195025, 470832, 1136689, 2744210, 6625109, 15994428, 38613965, 93222358, 225058681, 543339720, ...}

Tribonacci numbers with various signatures

Signature (0, 0, 1): A000073 Tribonacci numbers:

a (n) = a (n  −  1) + a (n  −  2) + a (n  −  3)

with

a (0) = a (1) = 0, a (2) = 1

.

{0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744, 755476, 1389537, 2555757, 4700770, 8646064, ...}

Signature (0, 1, 0): A001590 Tribonacci numbers:

a (n) = a (n  −  1) + a (n  −  2) + a (n  −  3)

with

a (0) = 0, a (1) = 1, a (2) = 0

.

{0, 1, 0, 1, 2, 3, 6, 11, 20, 37, 68, 125, 230, 423, 778, 1431, 2632, 4841, 8904, 16377, 30122, 55403, 101902, 187427, 344732, 634061, 1166220, 2145013, 3945294, 7256527, ...}

Signature (1, 1, 0): A081172 Tribonacci numbers:

a (n) = a (n  −  1) + a (n  −  2) + a (n  −  3)

with

a (0) = 1, a (1) = 1, a (2) = 0

.

{1, 1, 0, 2, 3, 5, 10, 18, 33, 61, 112, 206, 379, 697, 1282, 2358, 4337, 7977, 14672, 26986, 49635, 91293, 167914, 308842, 568049, 1044805, 1921696, 3534550, 6501051, ...}

Signature (1, 1, 1): A000213 Tribonacci numbers:

a (n) = a (n  −  1) + a (n  −  2) + a (n  −  3)

with

a (0) = a (1) = a (2) = 1

.

{1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201, 2209, 4063, 7473, 13745, 25281, 46499, 85525, 157305, 289329, 532159, 978793, 1800281, 3311233, 6090307, 11201821, ...}