Everyone is familiar with the Fibonacci Sequence, [0] 1 1 2 3 5 8 ... and many of it's interesting properties. For example, as the sequence continues, the ratio of $\frac{F_n}{F_{n-1}}$ converges to $\tau=\frac{1+\sqrt{5}}{2}$, a ratio which can be used to describe a number of numerical relationships in nature.
From some quick Wikipedia browsing, we can find a number of Generalizations of Fibonacci numbers. For one abstract generalization, we can define Fibonacci-like sequences as follows:
An $n$-order Fibonacci-like sequence is generated by $F_n=\sum_{i=1}^{n}F_{n-i}$ with $n$ initial terms.
Thus, the Fibonacci sequence is such a sequence with $n=2$ and $F_0=0$ and $F_1=1$
Using this basic generalization, we have Lucas Numbers, where $n=2$ and $F_0=2$ and $F_1=1$, whose consecutive-number ratio also converges to the golden ratio. There are also Tribonacci, Tetranacci, and n-nacci numbers, which follow this generalization for 3, 4, and n numbers, and pad the initializing values with 0s, e.g. $F_0=0$ … $F_{n-2}=0$, $F_{n-1}=1$.
So, my question is, are there any important properties of these sequences that are worth learning? Do these sequences have real-world applications or reflections like the original Fibonacci sequence does? What can be learned from these?
Best Answer
In any general recurrence of the form:
$$x_n = \sum_{i=1}^k {a_i x_{n-i}}$$
you can determine an explicit formula in terms of the roots of the polynomial of degree k:
$$z^k - a_1{z^{k-1}} - a_2{z^{k-2}} - a_{k-1}z - a_k$$
If the polynomial has no repeated roots, then the form of the explicit formula will be:
$$x_n = b_1 r_1^n + b_2 r_2^n + ... + b_k r_k^n$$
Where the $b_i$ can be any numbers, and the $r_i$ are the distinct roots of the polynomial.
This means that "most of the time," $\lim\limits_{n\to \infty}{x_{n+1}/x_n}$ will be equal to the root $r_i$ with the largest absolute value such that $b_i\neq 0$. If two $r_i$ have the same largest absolute value, the convergent behavior might be odd - it possibly might never converge.
There is a lot of linear algebra involved in this - the $r_i$s are eigenvalues of a matrix which sends $(x_i,x_{i+1},...,x_{i+k-1})$ to $(x_{i+1},...,x_{i+k})$
In the case of what you call the k-nacci numbers, your polynomial is:
$$x^k-x^{k-1}-x^{k-2}-..-1 = x^k -\frac{x^k-1}{x-1}$$
I'm not sure what you can say about the roots of this polynomial when $k>2$. It's easy to show it has no repeated roots (a polynomial has no repeated roots of it is relatively prime to its derivative.)