Interesting properties of Fibonacci-like sequences?

Question

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?

Answer 1

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.)

Answer 2

Most of these are not worth learning about, except for the fact they exist and are easily calculated. It is worth reviewing Lucas numbers, but there is no need to learn all the properties.

Your time would be better spent looking at recurrence relations and generating functions in greater generality.

If you want a particular similar sequence to study, I would suggest Pell numbers which start $0, 1, 2, 5, 12, 29, 70, 169, 408, 985, \ldots$, satisfy $P_n = 2P_{n-1}+P_{n-2}$ and are related to $1+\sqrt{2}$, the so-called silver ratio. They pop up in a variety of circumstances, for example finding numbers which are both square and triangular: $(P_n(P_n+P_{n-1}))^2$.

Answer 3

Define sequences $$F(n) = [0],1,1,2,3,5,8,13,21,34\ldots \hspace{.5in} \mbox{ for } n=0,1,2,3\ldots$$ and $$L(n) = [2],1,3,4,7,11,18,29,47,89\ldots\hspace{.5in} \mbox{ for } n=0,1,2,3\ldots$$

Then we have $L(n) =F(n+1)+F(n-1)$. The ratio $L(n)/F(n)$ tends to $\sqrt{5}$ as $n\to \infty$.

Now, define the sequences $$S_1\!(n) =[0] ,1 ,2 ,5 ,12 ,29 ,70\ldots\hspace{.5in} \mbox{ for } n=0,1,2,3\ldots$$ and $$S_2\!(n) = [-1] ,1 ,3 ,7 ,17 ,41 ,99 \ldots\hspace{.5in} \mbox{ for } n=0,1,2,3\ldots$$ Note that $S_1\!(n)=2S_1\!(n-1)+S_1\!(n-2)$ and $S_2\!(n)=2S_2\!(n-1)+S_2\!(n-2)$. For these two sequences, the ratio $S_2\!(n)/S_1\!(n)$ tends to $\sqrt{2}$ as $n\to \infty$.

These ratios are used to calculate $\sqrt{2}$ and $\sqrt{5}$. Using $F(n)/L(n)$, $\sqrt{2}$ has been computed to a trillion digits. These exercises are done to test the speed, accuracy and ruggedness of computer hardware and software.

An example: \begin{align} 17^2-2*12^2&=1\\ 2*12^2&=17^2-1\\ 2&=\frac{17^2-1}{12^2}\\ \sqrt{2}&=\frac{17}{12}\sqrt{1-\frac{1}{289}} \end{align}

Now $\sqrt{1-1/289}$ can be written as an infinite series for computation.

Answer 4

I can think of at least eight interesting things about the tribonacci numbers and its limiting ratio, the tribonacci constant. Whereas for the Fibonacci numbers the discriminant $\sqrt{5}$ plays a role, for the tribonacci it is $\sqrt{11}$.

I. Sequences

Given three sequences with recurrence $s_n = s_{n-1}+s_{n-2}+s_{n-3}$ but different initial values as,

$$\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline \text{Name} & \text{Formula} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & OEIS\\ \hline R_n & x_1^n+x_2^n+x_3^n &3 &1 &3 &7 &11 &21 &39 & 71 & A001644 \\ \hline S_n &\frac{x_1^n}{y_1}+\frac{x_2^n}{y_2}+\frac{x_3^n}{y_3}&3 &2 &5 &10 &17 &32 &59 &108 &(none)\\ \hline T_n &\frac{x_1^n}{z_1}+\frac{x_2^n}{z_2}+\frac{x_3^n}{z_3}&0 &1 &1 &2 &4 &7 &13 &24& A000073 \\ \hline \end{array}$$

$$y_i =\tfrac{1}{19}(x_i^2-7x_i+22)$$ $$z_i =-x_i^2+4x_i-1$$

and the $x_i$ are the roots of $x^3-x^2-x-1=0$, with $T_n$ as the tribonacci numbers and the real root $T = x_1 \approx 1.83929$ the tribonacci constant.

II. Powers

Let $a=\tfrac{1}{3}(19+3\sqrt{33})^{1/3},\; b=\tfrac{1}{3}(19-3\sqrt{33})^{1/3}$, then powers of the tribonacci constant $T$ can be expressed in terms of those three sequences as,

$$3T^n = R_{n}+(a+b)S_{n-1}+3(a^2+b^2)T_{n-1}$$

III. q-Continued fraction

Let $q = -1/(e^{\pi\sqrt{11}})$, then,

$$\frac{(e^{\pi\sqrt{11}})^{1/24}}{\frac{1}{T}+1} = 1 + \cfrac{q}{1-q + \cfrac{q^3-q^2}{1 + \cfrac{q^5-q^3}{1 + \cfrac{q^7-q^4}{1 + \ddots }}}}$$

IV. Snub cube

The Cartesian coordinates for the vertices of a snub cube are all the even permutations of $v=1/T$,

$\hskip2.8in$

V. Pi Formula

Let $v = 1/T$, then,

$$\small\sum_{n=0}^\infty \frac{(2n)!^3}{n!^6}\frac{2(4v+1)(2v+1)n+(4v^2+2v-1)}{(v+1)^{24n}} =\frac{4}{\pi}$$

VI. Infinite Nested Radical

$$\frac{1}{T-1} = \sqrt[3]{\frac{1}{2}+ \sqrt[3]{\frac{1}{2}+ \sqrt[3]{\frac{1}{2}+ \sqrt[3]{\frac{1}{2}+\dots}}}}$$

VII. Complete elliptic integral of the first kind $K(k_{11})$

Alternatively, its exact value is,

$$K(k_{11}) = \frac{1}{11^{1/4}(4\pi)^2} \bigl(\tfrac{T+1}{T}\bigr)^2\; \Gamma\bigl(\tfrac{1}{11}\bigr) \Gamma\bigl(\tfrac{3}{11}\bigr) \Gamma\bigl(\tfrac{4}{11}\bigr) \Gamma\bigl(\tfrac{5}{11}\bigr) \Gamma\bigl(\tfrac{9}{11}\bigr) = 1.570983\dots$$

VIII. Cubic Pell-Type Equation

The diophantine cubic Pell-type equation,

$$a^3 - 2 a^2 b + 2 b^3 - a^2 c - 2 a b c + 2 b^2 c + a c^2 + 2 b c^2 + c^3=1$$

has an infinite number of integer solutions,

$$a,\;b,\;c = T_{n-1},\;T_{n-2},\;T_{n-3}$$

Conclusion: Surely the tribonacci numbers are interesting enough?

P.S. See also this post.