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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/Recurrence_relation $\endgroup$ – joriki May 27 '11 at 15:34
  • 2
    $\begingroup$ This isn't a totally different thing. There's a generalization of Binet's formula that works for any sequence of this type. $\endgroup$ – Qiaochu Yuan May 27 '11 at 15:34
  • $\begingroup$ possible duplicate of Interesting properties of Fibonacci-like sequences? $\endgroup$ – Aryabhata May 27 '11 at 15:46
  • 2
    $\begingroup$ 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 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. $\endgroup$ – t.b. May 27 '11 at 16:14
10
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ So having for example K=100 we'll have matrix 100x100 ? $\endgroup$ – Krzysztof Lewko May 27 '11 at 19:16
  • 1
    $\begingroup$ That's right - this method becomes a lot more complicated for recurrence sequences with higher values of $K$. In the long run it's still more efficient for calculation than using the defining recurrence relation, even using 'naive' versions of matrix multiplication (that take $O(K^3)$ time to multiply $K\times K$ matrices); ignoring the size of the coefficients, you'll be doing $O(K^3\log n)$ operations to find the $n$th term, rather than $O(Kn)$ operations using the basic recurrence relation, so you need $n$ to be at least on the order of $K^2$ for it to help. $\endgroup$ – Steven Stadnicki May 27 '11 at 20:32
  • $\begingroup$ Also, similar to the the way that the values of Fibonacci numbers hew close to powers of the golden ratio, all of these sequences grow as $\alpha_K^n$ for some constant $\alpha_K$, and it's possible to show that $\alpha_K\rightarrow 2$ as $K\rightarrow\infty$. $\endgroup$ – Steven Stadnicki May 27 '11 at 20:39
  • $\begingroup$ Note that representing the recursions for $n$-nacci numbers as matrix powers ends up with one taking the powers of an appropriate Frobenius companion matrix, whose characteristic polynomials are (relatively) trivial to derive (and explains why $n$-nacci numbers are expressible as combinations of powers of polynomial roots). $\endgroup$ – J. M. is a poor mathematician Jun 2 '11 at 4:49
  • 1
    $\begingroup$ @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 ;-) $\endgroup$ – vonbrand Jan 24 '13 at 0:29
6
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ From your mathworld link you can get to mathworld.wolfram.com/Fibonaccin-StepNumber.html where similar formula for n-step Fibonacci sequence is mentioned. $\endgroup$ – Martin Sleziak May 27 '11 at 16:36
  • $\begingroup$ The $k$'th "$n$-step Fibonacci" number can be written as $\sum_r \frac{1}{r^k P'(r)}$ where $P(z) = -1 + \sum_{k=1}^n z^n$ and the sum is over the roots of $P(z)$. $\endgroup$ – Robert Israel May 27 '11 at 18:29
  • $\begingroup$ 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.) $\endgroup$ – Martin Sleziak May 29 '11 at 9:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.