## Sequences 1, Tribonacci numbers

In this 3-part series of posts, we’ll discuss well-known sequences with the recurrence,

$aP_{n-3} + bP_{n-2} + cP_{n-1} = P_n$

where {a, b, ccan only be zero or unity.  Aside from the Fibonacci and Lucas numbers which is a = 0, there is the Narayana sequence with b = 0, the Padovan and Perrin with c = 0, and the tribonacci has a = b = c = 1.  All four cases may then share similar properties and one of which, interestingly enough, is that their limiting ratios, a root of the following equations,

\begin{aligned} x^2 &=x+1\\ y^3 &= y^2+1\\ z^3 &= z+1\\ t^3 &= t^2+t+1\end{aligned}

can also be used to express $\zeta(3)$,  or Apery’s constant.

I. Fibonacci and Lucas numbers

Given the two roots of,

$x^2=x+1$

with $x_1 > x_2$, the larger root being the golden ratio, we get the Lucas numbers L(n) and Fibonacci numbers F(n),

\begin{aligned} L_n &= x_1^n+x_2^n = 2,1,3,4,7,11,18,29,\dots\\[2mm] F_n &= \frac{x_1^n-x_2^n}{\sqrt{5}} = 0,1,1,2,\,3,\,5,\,8,\,13,\dots\end{aligned}

(The starting index is n = 0.)  Expanding powers of the golden ratio, then for n > 0,

\begin{aligned} & {x_1}^n = \Big(\frac{1+\sqrt{5}}{2}\Big)^n = \frac{L_n+F_n\sqrt{5}}{2}\end{aligned}

We’ll see this can be generalized to powers of the tribonacci constant.

II. Tribonacci numbers

These are a generalization of the Fibonacci numbers, being,

$t_n = t_{n-1}+t_{n-2}+t_{n-3}$

Pin-Yen Lin has a nice paper involving these numbers.  First, define the following three sequences with this recurrence, but with different initial values,

\begin{aligned}S_n &=0,0,1,1,2,4,7,13,24,\dots\\U_n &=0,3,2,5,10,17,32,49,\dots\\V_n &=3,1,3,7,11,21,39,71,\dots \end{aligned}

(The starting index as usual is n = 0.)  The first and the third are recognized by the OEIS, with the first being the tribonacci numbers.  The limiting ratio for all three is the tribonacci constant, T, the real root of,

$x^3=x^2+x+1$

or,

$T = \frac{1}{3}+\frac{1}{3}(19+3\sqrt{33})^{1/3}+\frac{1}{3}(19-3\sqrt{33})^{1/3}$

I’ve already written about the tribonacci constant before.  But I want to include how Lin found that powers of x can be expressed in terms of those three sequences. Define,

$a =\sqrt[3]{19+3\sqrt{33}}$

$b =\sqrt[3]{19-3\sqrt{33}}$

then, similar to the golden ratio,

$T^n = \frac{1}{9}(a^2+b^2)\,S_n+\frac{1}{9}(a+b)\,U_n+\frac{1}{3}\,V_n$

Hence, starting with = 1,

$T = \frac{0}{9}(a^2+b^2)+\frac{3}{9}(a+b)+\frac{1}{3}$

$T^2 = \frac{1}{9}(a^2+b^2)+\frac{2}{9}(a+b)+\frac{3}{3}$

$T^3 = \frac{1}{9}(a^2+b^2)+\frac{5}{9}(a+b)+\frac{7}{3}$

and so on.  Interesting, isn’t it, that powers of the tribonacci constant can be expressed in this manner.

There is a primality test regarding Lucas numbers: if n is a prime then $L_n-1$ is divisible by n.  For example $L_5 = 11$, minus 1, is divisible by 5.  However there are Lucas pseudoprimes, composite numbers that pass this test, with the smallest being n = 705.
The third tribonacci sequence can be formed analogously to the Lucas numbers.  Given the three roots $x_1, x_2, x_3$ of,
$x^3=x^2+x+1$
$V_n = x_1^n+x_2^n+x_3^n = 3,1,3,7,11,21,39,71,\dots$
I notice that likewise, if n is prime, then $V_n-1$ is divisible by n.  But there are also tribonacci-like pseudoprimes.  The smallest is n = 182.  Steven Stadnicki was nice enough to compute the first 36.  It turns out they are relatively rarer, as there are only 21 less than $10^8$, while there are  852 Lucas pseudoprimes in the same range.