Posts Tagged ‘tribonacci’

Sequences 2, Padovan and Perrin numbers

III. Padovan sequence

Just like the golden ratio and tribonacci constant, powers of the plastic constant P can also be expressed in terms of sequences associated with it. P is a root of the equation,

P^3=P+1

or,

P = \frac{1}{3}\left(\frac{27+3\sqrt{69}}{2}\right)^{1/3}+\frac{1}{3}\left(\frac{27-3\sqrt{69}}{2}\right)^{1/3}

Define,

\begin{aligned}    a & = \left(\tfrac{27+3\sqrt{69}}{2}\right)^{1/3}\\b&=\left(\tfrac{27-3\sqrt{69}}{2}\right)^{1/3}\end{aligned}

then powers of P  are,

P^{n} = \frac{1}{9}(a^2+b^2)U_{n+1}+\frac{1}{3}(a+b)U_{n+2}+\frac{1}{3}V_n

where U and V are the Padovan and Perrin sequences, respectively,

\begin{aligned} U_n &= 1,0,0,1,0,1,1,1,2,2,3,4,5,7,9,12,16\dots\\    V_n &=3,0,2,3,2,5,5,7,10,12,17,22,29,\dots\end{aligned}

which start with index n = 0.  Hence,

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

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

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

and so on.  These sequences obey,

W_n = W_{n-2} + W_{n-3}

and their limiting ratio, of course, is P.  While the Fibonacci sequence has a nice representation as a square spiral, the Padovan is a spiral of equilateral triangles,

The Perrin sequence also has a notable feature regarding primality testing.  Let x_1, x_2, x_3 be the roots of,

P^3=P+1

then, starting with n = 0,

V_n=x_1^n+x_2^n+x_3^n = 3,0,2,3,2,5,5,7,10,12,17,22,29,\dots

Indexed in this manner, if n is prime, then n divides V_n.  For example V_{11} = 22.  However, there are Perrin pseudoprimes, composite numbers that pass this test, with the smallest being n = 521^2.

Lastly, like all the four limiting ratios of this family of recurrences, the plastic constant P  can be expressed in terms of the Dedekind eta function as,

\begin{aligned} P &=\frac{e^{\pi i/24}\,\eta(\tau) }{\sqrt{2}\,\eta(2\tau)}\end{aligned}

where,

\tau=\frac{1+\sqrt{-23}}{2}

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.

Addendum:

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

then, starting with n = 0,

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.

The Tremendous Tribonacci constant

The tribonacci constant is the real root of the cubic equation,

T^3-T^2-T-1 = 0

and is the limiting ratio of the tribonacci numbers = {0, 1, 1, 2, 4, 7, 13, 24, …} where each term is the sum of the previous three, analogous to the Fibonacci numbers.  Let d = 11, then,

T = \frac{1}{3} +\frac{1}{3}\big(19+3\sqrt{3d}\big)^{1/3} + \frac{1}{3}\big(19-3\sqrt{3d}\big)^{1/3} = 1.839286\dots

We’ll see that the tribonacci constant is connected to the complete elliptic integral of the first kind K(k_{11}).  But first, given the golden ratio’s infinite radical representation,

\phi = \sqrt{1+\sqrt{1+\sqrt{1+\sqrt{1+\dots}}}}

then T also has the beautiful infinite radical,

\frac{1}{T-1} = \sqrt[3]{\frac{1}{2}+\sqrt[3]{\frac{1}{2}+\sqrt[3]{\frac{1}{2}+\sqrt[3]{\frac{1}{2}+\dots}}}} = 1.191487\dots

as well as a continued fraction,

\big(\frac{T}{T+1}\big) \big(e^{\frac{\pi\sqrt{11}}{24}}\big) = 1 + \cfrac{q}{1-q + \cfrac{q^3-q^2}{1+\cfrac{q^5-q^3}{1+\cfrac{q^7-q^4}{1+\ddots}}}} = 0.9999701\dots

where q is the negative real number,

q = \frac{-1}{e^{\pi \sqrt{11}}}

Recall that at elliptic singular values, the complete elliptic integral of the first kind K(k) satisfies the equation,

\frac{K'(k_d)}{K(k_d)} = \sqrt{d}

or, in the syntax of Mathematica,

\frac{EllipticK[1-ModularLambda[\sqrt{-d}]]}{EllipticK[ModularLamda[\sqrt{-d}]]} = \sqrt{d}

Interestingly, we can express both k_{11} = 0.000477\dots and K(k_{11}) = 1.57098\dots in terms of the tribonacci constant as,

k_{11} = \frac{1}{4}\left(2-\sqrt{\frac{2v+7}{2v-7}}\,\right) = 0.000477\dots

where,

v = T+4

and,

K(k_{11}) = \left(\frac{T+1}{T}\right)^2\, \frac{1}{11^{1/4}\, (4\pi)^{2}} \, \Gamma(\tfrac{1}{11}) \Gamma(\tfrac{3}{11}) \Gamma(\tfrac{4}{11}) \Gamma(\tfrac{5}{11}) \Gamma(\tfrac{9}{11})

where \Gamma(n) is the gamma function, as well as the infinite series,

K(k_{11}) = \left(\frac{T+1}{T}\right)^2 \frac{\pi}{32^{1/4}} \sqrt{\frac{1}{4} \sum_{n=0}^\infty \frac{(6n)!}{(3n)!n!^3} \,\frac{1}{(-32)^{3n}} }

With a slight tweak of the formula, we instead get,

\frac{1}{4\pi} = \frac{1}{32^{3/2}} \sum_{n=0}^\infty \frac{(6n)!}{(3n)!n!^3}\, \frac{154n+15}{(-32)^{3n}}

Finally, saving the best for last, given the snub cube, an Archimedean solid,

then the Cartesian coordinates for its vertices are all the even and odd permutations of,

{± 1,  ± 1/T,  ±}

with an even and odd number of plus signs, respectively, similar to how, for the vertices of the dodecahedron — a Platonic solid —  one can use the golden ratio.

For more about the tribonacci constant, and the equally fascinating plastic constant,  kindly refer to “A Tale of Four Constants “.