Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 3 down vote accepted

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

share|improve this 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.)

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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