Fibonacci, tribonacci and other similar sequences 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.
 A: 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. 
A: 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.
