6
$\begingroup$

I know the sequence called the Fibonacci sequence; it's defined like:

$\begin{align*} F_0&=0\\ F_1&=1\\ F_2&=F_0+F_1\\ &\vdots\\ Fn&=F_{n-1} + F_{n-2}\end{align*}$

And we know that there's Binet formula for computing $n$-th element in the sequence.

However, I'm trying to find something totally different.

We know that $K=2$ for the Fibonacci sequence; let's call $K$ the number of previous elements to get the $n$-th element. For example,

$\begin{align*} K=2&\Rightarrow F_n= F_{n-1} + F_{n-2},\\ K=3&\Rightarrow F_n= F_{n-1} + F_{n-2} + F_{n-3},\\ \end{align*}$

and so on.

How to compute the $n$-th element for given $K$? I couldn't find any formula for $K > 2$.

Thanks for any help.

  • 2
    Whoever invented "tribonacci" must have deliberately ignored the etymology of Fibonacci's name - which was bestowed on him quite a bit after his death. [Leonardo da Pisa's](http://en.wikipedia.org/wiki/Fibonacci) grandfather had the name Bonaccio (the benevolent), which was also used by his father. The name "filius bonacii" or "figlio di Bonaccio" (son of Bonaccio) was contracted to give Fibonacci. By the way: the Fibonacci sequence was baptized like this by [Édouard Lucas](http://en.wikipedia.org/wiki/Edouard_Lucas).2011-05-27

2 Answers 2

10

In addition to André's notes, another means of calculating solutions to these recurrence relations is to rephrase them using linear algebra as a single matrix multiply and then apply the standard algorithms for computing large powers of numbers (i.e., via binary representation of the exponent) to computing powers of the matrix; this allows for the $n$th member of the sequence to be computed with $O(\log(n))$ multiplies (of potentially exponentially-large numbers, but the multiplication can also be sped up through more complicated means).

In the Fibonacci case, this comes by forming the vector $\mathfrak{F}_n = {F_n\choose F_{n-1}}$ and recognizing that the recurrence relation can be expressed by multiplying this vector with a suitably-chosen matrix: $\mathfrak{F}_{n+1} = \begin{pmatrix}F_{n+1} \\\\ F_n \end{pmatrix} = \begin{pmatrix}F_n + F_{n-1} \\\\ F_n \end{pmatrix} = \begin{pmatrix} 1&1 \\\\ 1&0 \end{pmatrix} \begin{pmatrix} F_n \\\\ F_{n-1} \end{pmatrix} = M_F\mathfrak{F}_n $

where $M_F$ is the $2\times2$ matrix $\begin{pmatrix} 1&1 \\\\ 1&0 \end{pmatrix}$. This lets us find $F_n$ by finding $M_F^n\mathfrak{F}_0$, and as I noted above the matrix power is easily computed by finding $M_F^2, M_F^4=(M_F^2)^2, \ldots$ (note that this also gives an easy way of proving the formulas for $F_{2n}$ in terms of $F_n$ and $F_{n-1}$, which are just the matrix multiplication written out explicitly; similarly, the Binet formula itself can be derived by finding the eigenvalues of the matrix $M_F$ and diagonalizing it).

Similarly, for the Tribonacci numbers the same concept applies, except that the matrix is 3x3: $\mathfrak{T}_{n+1} = \begin{pmatrix} T_{n+1} \\\\ T_n \\\\ T_{n-1} \end{pmatrix} = \begin{pmatrix} T_n+T_{n-1}+T_{n-2} \\\\ T_n \\\\ T_{n-1} \end{pmatrix} = \begin{pmatrix} 1&1&1 \\\\ 1&0&0 \\\\ 0&1&0 \end{pmatrix} \begin{pmatrix} T_n \\\\ T_{n-1} \\\\ T_{n-2} \end{pmatrix} = M_T\mathfrak{T}_n$ with $M_T$ the $3\times3$ matrix that appears there; this is (probably) the most efficient all-integer means of finding $T_n$ for large values of $n$, and again it provides a convenient way of proving various properties of these numbers.

  • 1
    @StevenStadnicki: You are right. Please next time you criticize me, rub it into my face in the comment, so I don't embarass myself multiple times ;-)2013-01-24
6

This is halfway between a comment and an answer. The Binet Formula (misattributed of course, it was known long before Binet) can only in a limited way be thought of as a formula "for computing" the $n$-th term of the Fibonacci sequence. Certainly it works nicely for small $n$. However, for even medium-sized $n$, it demands high-accuracy computation of $\sqrt{5}$. Ironically, such high accuracy computations of $\sqrt{5}$ involve close relatives of the Fibonacci sequence!

You can find a discussion of algorithms for computing the Fibonacci sequence at http://www.ics.uci.edu/~eppstein/161/960109.html.

A Binet-like expression for the "Tribonacci" numbers can be found at http://mathworld.wolfram.com/TribonacciNumber.html

However, the recurrence for the Tribonacci numbers, suitably speeded up, is a better computing method than the formula.

  • 0
    As far as your note of necessity of using value $\sqrt{5}$ with high accuracy; I can imagine an algorithm to compute $F_n$ from Binet formula that would work in $\mathbb{Q}[\sqrt{5}]$. (Of course, this algorithm would not have much practical value, just a side-note to the comments on high precision.)2011-05-29