1

I have been thinking about finding an explicit formula for the tribonacci numbers, where, namely:

$$a_n = a_{n-1}+a_{n-2}+a_{n-3}$$

and $a_1 = 0, a_1 = 1, a_2 = 1.$ Obviously, these beginning terms can be shifted, but we'll leave them as such for now.

This has proven difficult, and I'm still not sure how it's done, but what about the general sequence:

$$a_n = xa_{n-1}+ya_{n-2}+za_{n-3}$$

With arbitrary $a_1, a_2,$ and $a_3.$ How is a tribonacci explicit formula calculated?

Cheers.

2 Answers2

3

The real root of $x^3 - x^2 - x - 1$ is As in comments, the formula is $$ A \alpha^n + B \beta^n + \bar{B} \bar{\beta}^n $$

with

$$ \alpha = \frac{ 1 + \sqrt[3]{19 + \sqrt{297}}+ \sqrt[3]{19 - \sqrt{297}} }{3} \approx 1.83928675521416113255 $$ \approx -0.4196433776070805662759262823 + 0.6062907292071993692593421970 i the complex conjugate roots are of magnitude smaller than one and their powers shrink

Using $$ \omega = -\frac{1}{2} + i \frac{\sqrt 3}{2} $$ and $$ \bar{\omega} = -\frac{1}{2} - i \frac{\sqrt 3}{2} $$

the conjugate roots are $$ \beta = \frac{ 1 + \omega\sqrt[3]{19 + \sqrt{297}}+ \bar{\omega}\sqrt[3]{19 - \sqrt{297}} }{3} \approx -0.4196433776070805662759262823 + 0.6062907292071993692593421970 i $$

$$ \bar{\beta} = \frac{ 1 + \bar{\omega}\sqrt[3]{19 + \sqrt{297}}+ \omega\sqrt[3]{19 - \sqrt{297}} }{3}\approx -0.4196433776070805662759262823 - 0.6062907292071993692593421970 i $$

Will Jagy
  • 139,541
  • 1
    It would be worth including in your answer how it relates to the question, even if it is obvious to you. – Eddy Oct 22 '20 at 23:17
2

Please see https://www.fq.math.ca/Scanned/36-2/wolfram.pdf in The Fibonacci Quarterly, sub-section 6.2.2. That approach also considers having initial functions instead of any given initial values.

Changing the constant coefficients to $x$, $y$ and $z$ from 1 can be solved similarly.

Specifically, we are seeking a solution for $f$ where $f: \Re \rightarrow \Im$ which has the property \begin{equation} \label{rec-eq} f(x) = \sum_{1 \leq l \leq 3}~f(x - l) \end{equation} where $f(0)$, $f(1)$ and $f(2)$ are given initial values.

The real root of the associated characteristic equation $x^3 - x^2 - x - 1 = 0$ is $r_1 = \frac{1 + (19 - 3\sqrt{33})^{\frac{1}{3}} + (19 + 3\sqrt{33})^{\frac{1}{3}}}{3}$. The approximate values of the complex roots are $-0.419643377607081 \pm 0.606290729207199 i$.

A general solution is $f(x) = K_1 r_1^x + K_2 r_1^{\frac{-x}{2}}\cos (\theta x) + r_1^{\frac{-x}{2}} \left( \frac{K_2\left(\frac{1 -r_1}{2}\right) + K_3}{\sqrt{\frac{1}{r_1} - \left(\frac{r_1 - 1}{2}\right)^2}} \right) \sin (\theta x)$ where $\theta =\arccos \left(\frac{1 - r_1}{2} \sqrt{r_1}\right)$ and $K_1$, $K_2$ and $K_3$ are solutions to the system $\left[ \begin{array}{ccc} 1 & 1 & 0\\ r_1 -1 & -r_1 & 1\\ \frac{1}{r_1} & 0 & -r_1 \end{array}\right] \left[\begin{array}{c} K_1\\ K_2\\ K_3 \end{array}\right] = \left[\begin{array}{c} f(0)\\ f(1) - f(0)\\ f(2) - f(1) - f(0) \end{array}\right]. $

DavidW
  • 572