Generalizations of Fibonacci numbers
In mathematics, the Fibonacci numbers form a sequence defined recursively by:
That is, after two starting values, each number is the sum of the two preceding numbers.
The Fibonacci sequence has been studied extensively and generalized in many ways, for example, by starting with other numbers than 0 and 1, by adding more than two numbers to generate the next number, or by adding objects other than numbers.
Extension to negative integers
Using, one can extend the Fibonacci numbers to negative integers. So we get:and.
See also Negafibonacci coding.
Extension to all real or complex numbers
There are a number of possible generalizations of the Fibonacci numbers which include the real numbers in their domain. These each involve the golden ratio, and are based on Binet's formulaThe analytic function
has the property that for even integers. Similarly, the analytic function:
satisfies for odd integers.
Finally, putting these together, the analytic function
satisfies for all integers.
Since for all complex numbers, this function also provides an extension of the Fibonacci sequence to the entire complex plane. Hence we can calculate the generalized Fibonacci function of a complex variable, for example,
However, this extension is by no means unique. For example, either
for any odd integer is an extension of the Fibonacci number sequence to the entire complex plane, as is any linear combination of them for which the coefficients sum to 1.
Vector space
The term Fibonacci sequence is also applied more generally to any function from the integers to a field for which. These functions are precisely those of the form, so the Fibonacci sequences form a vector space with the functions and as a basis.More generally, the range of may be taken to be any abelian group. Then the Fibonacci sequences form a 2-dimensional Z-module in the same way.
Similar integer sequences
Fibonacci integer sequences
The 2-dimensional -module of Fibonacci integer sequences consists of all integer sequences satisfying. Expressed in terms of two initial values we have:where is the golden ratio.
The ratio between two consecutive elements converges to the golden ratio, except in the case of the sequence which is constantly zero and the sequences where the ratio of the two first terms is.
The sequence can be written in the form
in which if and only if. In this form the simplest non-trivial example has, which is the sequence of Lucas numbers:
We have and. The properties include:
Every nontrivial Fibonacci integer sequence appears as one of the rows of the Wythoff array. The Fibonacci sequence itself is the first row, and a shift of the Lucas sequence is the second row.
See also Fibonacci integer sequences modulo n.
Lucas sequences
A different generalization of the Fibonacci sequence is the Lucas sequences of the kind defined as follows:where the normal Fibonacci sequence is the special case of and. Another kind of Lucas sequence begins with,. Such sequences have applications in number theory and primality proving.
When, this sequence is called -Fibonacci sequence, for example, Pell sequence is also called 2-Fibonacci sequence.
The 3-Fibonacci sequence is
The 4-Fibonacci sequence is
The 5-Fibonacci sequence is
The 6-Fibonacci sequence is
The -Fibonacci constant is the ratio toward which adjacent -Fibonacci numbers tend; it is also called the th metallic mean, and it is the only positive root of. For example, the case of is, or the golden ratio, and the case of is, or the silver ratio. Generally, the case of is.
Generally, can be called -Fibonacci sequence, and can be called -Lucas sequence.
The -Fibonacci sequence is
The -Fibonacci sequence is
The -Fibonacci sequence is
The -Fibonacci sequence is
Fibonacci numbers of higher order
A Fibonacci sequence of order is an integer sequence in which each sequence element is the sum of the previous elements. The usual Fibonacci numbers are a Fibonacci sequence of order 2. The cases and have been thoroughly investigated. The number of compositions of nonnegative integers into parts that are at most is a Fibonacci sequence of order. The sequence of the number of strings of 0s and 1s of length that contain at most consecutive 0s is also a Fibonacci sequence of order.These sequences, their limiting ratios, and the limit of these limiting ratios, were investigated by Mark Barr in 1913.
Tribonacci numbers
A variation of the Fibonacci number sequence isthe tribonacci number sequence, where each number is the sum of the three preceding
numbers. Starting with the initial values, and, the recurrence
gives this sequence of numbers as
Further terms can be found under sequence number in The On-Line Encyclopedia of Integer Sequences.
The tribonacci sequence has a long and interesting history.
The most notable historical occurrence of the sequence is connected to Charles Darwin and his seminal book On the Origin of Species, where the procreation and population growth of elephants is considered as an illustrative
example.
In 1892, the sequence of numbers appeared in the solution of a recreational problem, concerning
a farmer and the raising of sheep, that was posed by the American mathematician Artemas Martin.
The first mathematical treatment of the tribonacci sequence and an investigation of its properties was done in 1914 and is
due to Agronomof.
The moniker tribonacci appeared much later, not until 1963, and is due to Mark Feinberg, at the time a fourteen-year-old high-school student, who introduced the term in an article in
the Fibonacci Quarterly.
Agronomof's identity.
Agronomof's 1914 note is a small gem that was ignored, made no impact at the time, and gathered dust for over half a century. Although a very brief note, it contains the powerful identity
Note that Agronomof's identity is symmetric in and, and that, for, one recovers the original tribonacci recurrence. Agronomof made his derivation under the assumption that both parameters and are nonnegative integers. However, one can show that the identity is more general and actually holds
for arbitrary integers and by extending the defining recurrence to include tribonacci numbers with negative indices.
Agronomof ends his note by showcasing the following propriétés remarquables of the tribonacci numbers,
These are easily derived from his identity by taking and.
In turn, these two identities can be leveraged to derive a simple expression for the sum of squares of
the tribonacci numbers.
Reflection formula.
As with the Fibonacci numbers, one can run the recurrence for the tribonacci numbers backwards.
From, and, one can determine.
From, and, one can determine, and so on.
Thus, the values for the tribonacci numbers at negative indices are well defined.
Starting with,, and, and reversing the tribonacci recurrence, gives the sequence of negatively indexed tribonacci numbers
as
Further terms can be found under sequence number in The On-Line Encyclopedia of Integer Sequences.
The extension to negative indices means that one can view the tribonacci sequence as a double infinite sequence:
where the value at index zero is given in bold. Traversing the sequence from left to right, one uses recurrence. Traversing the sequence from right to left, one uses the recurrence
The relationship between the negative and positive indexed segments of the tribonacci sequence is given by
This identity holds for all integers, and is known as the reflection formula for the tribonacci numbers. It can be derived using Agronomof's identity.
The tribonacci constant
is the ratio toward which adjacent tribonacci numbers tend. It is the unique real root of the polynomial, approximately , and also satisfies the equation. It is important in the study of the snub cube.
The reciprocal of the tribonacci constant, expressed by the relation, can be written as:
approximately .
The tribonacci numbers are also given by
where denotes the nearest integer function and
Corresponding to the Lucas numbers for the Fibonacci sequence, if one instead starts with,, and and applies the tribonacci recursion then whenever
Tetranacci numbers
The tetranacci numbers start with four predetermined terms, each term afterwards being the sum of the preceding four terms. The first few tetranacci numbers are:Feinberg also coined the term tetranacci.
The tetranacci constant is the ratio toward which adjacent tetranacci numbers tend. It is the unique positive real root of the polynomial, approximately , and also satisfies the equation.
The tetranacci constant can be expressed in terms of radicals by the following expression:
where,
and is the real root of the cubic equation.
Corresponding to the Lucas numbers for the Fibonacci sequence, if one instead starts with,,, and and applies the tetranacci recursion then whenever
Higher orders
Pentanacci, hexanacci, heptanacci, octanacci and enneanacci numbers have been computed.Pentanacci numbers:
The pentanacci constant is the ratio toward which adjacent pentanacci numbers tend.
It is the unique real root of the polynomial, approximately , and also satisfies the equation.
Hexanacci numbers:
The hexanacci constant is the ratio toward which adjacent hexanacci numbers tend.
It is the unique positive real root of the polynomial, approximately , and also satisfies the equation.
Heptanacci numbers:
The heptanacci constant is the ratio toward which adjacent heptanacci numbers tend.
It is the unique real root of the polynomial, approximately , and also satisfies the equation.
Octanacci numbers:
Enneanacci numbers:
An "infinacci" sequence, if one could be described, would, after an infinite number of zeroes, yield the sequence
which are simply the powers of two.
The limit of the ratio of successive terms of an -nacci series tends to a root of the equation .
The limit of the ratio for any is the unique positive root of the characteristic equation
The special case is the traditional Fibonacci series yielding the golden section.
The above formulas for the ratio hold even for -nacci series generated from arbitrary starting numbers. The ratio approaches 2 in the limit that increases to infinity.
The root is in the interval. The negative root of the characteristic equation is in the interval when is even. This root and each complex root of the characteristic equation has modulus.
A series for the positive root for any is
There is no solution of the characteristic equation in terms of radicals when.
The th element of the -nacci sequence is given by
where denotes the nearest integer function and is the -nacci constant, which is the root of nearest to 2.
A coin-tossing problem is related to the -nacci sequence. The probability that no consecutive tails will occur in tosses of an idealized coin is.