In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the
Fibonacci number
In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
s form a
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
defined
recursively
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
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:
:... −8, 5, −3, 2, −1, 1, 0, 1, 1, 2, 3, 5, 8, ...
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 mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
(and sometimes the
complex numbers
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form a ...
) in their domain. These each involve the
golden ratio
In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities. Expressed algebraically, for quantities a and b with a > b > 0,
where the Greek letter phi ( ...
, and are based on Binet's formula
:
The analytic function
:
has the property that
for
even
Even may refer to:
General
* Even (given name), a Norwegian male personal name
* Even (surname)
* Even (people), an ethnic group from Siberia and Russian Far East
** Even language, a language spoken by the Evens
* Odd and Even, a solitaire game w ...
integers
. Similarly, the analytic function:
:
satisfies
for
odd
Odd means unpaired, occasional, strange or unusual, or a person who is viewed as eccentric.
Odd may also refer to:
Acronym
* ODD (Text Encoding Initiative) ("One Document Does it all"), an abstracted literate-programming format for describing X ...
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,
:
Vector space
The term ''Fibonacci sequence'' is also applied more generally to any
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
from the integers to a field for which
. These functions are precisely those of the form
, so the Fibonacci sequences form a
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
with the functions
and
as a basis.
More generally, the range of
may be taken to be any
abelian group
In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is commut ...
(regarded as a
-module). Then the Fibonacci sequences form a 2-dimensional
-module in the same way.
Similar integer sequences
Fibonacci integer sequences
The 2-dimensional
-module of Fibonacci
integer sequence
In mathematics, an integer sequence is a sequence (i.e., an ordered list) of integers.
An integer sequence may be specified ''explicitly'' by giving a formula for its ''n''th term, or ''implicitly'' by giving a relationship between its terms. For ...
s 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 number
The Lucas numbers or Lucas series are an integer sequence named after the mathematician François Édouard Anatole Lucas (1842–1891), who studied both that sequence and the closely related Fibonacci numbers. Lucas numbers and Fibonacci nu ...
s:
:
We have
and
. The properties include:
:
Every nontrivial Fibonacci integer sequence appears (possibly after a shift by a finite number of positions) as one of the rows of the
Wythoff array
In mathematics, the Wythoff array is an infinite matrix of integers derived from the Fibonacci sequence and named after Dutch mathematician Willem Abraham Wythoff. Every positive integer occurs exactly once in the array, and every integer sequence ...
. 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 .
Lucas sequences
A different generalization of the Fibonacci sequence is the
Lucas sequence
In mathematics, the Lucas sequences U_n(P,Q) and V_n(P, Q) are certain constant-recursive integer sequences that satisfy the recurrence relation
: x_n = P \cdot x_ - Q \cdot x_
where P and Q are fixed integers. Any sequence satisfying this recu ...
s 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
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
proving.
When
, this sequence is called -Fibonacci sequence, for example,
Pell sequence
In mathematics, the Pell numbers are an infinite sequence of integers, known since ancient times, that comprise the denominators of the closest rational approximations to the square root of 2. This sequence of approximations begins , , , , and ...
is also called 2-Fibonacci sequence.
The 3-Fibonacci sequence is
:0, 1, 3, 10, 33, 109, 360, 1189, 3927, 12970, 42837, 141481, 467280, 1543321, 5097243, 16835050, 55602393, 183642229, 606529080, ...
The 4-Fibonacci sequence is
:0, 1, 4, 17, 72, 305, 1292, 5473, 23184, 98209, 416020, 1762289, 7465176, 31622993, 133957148, 567451585, 2403763488, ...
The 5-Fibonacci sequence is
:0, 1, 5, 26, 135, 701, 3640, 18901, 98145, 509626, 2646275, 13741001, 71351280, 370497401, 1923838285, 9989688826, ...
The 6-Fibonacci sequence is
:0, 1, 6, 37, 228, 1405, 8658, 53353, 328776, 2026009, 12484830, 76934989, 474094764, 2921503573, 18003116202, ...
The -Fibonacci constant is the ratio toward which adjacent
-Fibonacci numbers tend; it is also called the th
metallic mean
The metallic means (also ratios or constants) of the successive natural numbers are the continued fractions:
n + \cfrac
= ;n,n,n,n,\dots= \frac.
The golden ratio (1.618...) is the metallic mean between 1 and 2, while the silver ratio (2.414 ...
, and it is the only positive
root
In vascular plants, the roots are the organs of a plant that are modified to provide anchorage for the plant and take in water and nutrients into the plant body, which allows plants to grow taller and faster. They are most often below the sur ...
of
. For example, the case of
is
, or the
golden ratio
In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities. Expressed algebraically, for quantities a and b with a > b > 0,
where the Greek letter phi ( ...
, and the case of
is
, or the
silver ratio
In mathematics, two quantities are in the silver ratio (or silver mean) if the ratio of the smaller of those two quantities to the larger quantity is the same as the ratio of the larger quantity to the sum of the smaller quantity and twice t ...
. Generally, the case of
is
.
Generally,
can be called -Fibonacci sequence, and can be called -Lucas sequence.
The (1,2)-Fibonacci sequence is
:0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691, 87381, 174763, 349525, 699051, 1398101, 2796203, 5592405, 11184811, 22369621, 44739243, 89478485, ...
The (1,3)-Fibonacci sequence is
:1, 1, 4, 7, 19, 40, 97, 217, 508, 1159, 2683, 6160, 14209, 32689, 75316, 173383, 399331, 919480, 2117473, 4875913, 11228332, 25856071, 59541067, ...
The (2,2)-Fibonacci sequence is
:0, 1, 2, 6, 16, 44, 120, 328, 896, 2448, 6688, 18272, 49920, 136384, 372608, 1017984, 2781184, 7598336, 20759040, 56714752, ...
The (3,3)-Fibonacci sequence is
:0, 1, 3, 12, 45, 171, 648, 2457, 9315, 35316, 133893, 507627, 1924560, 7296561, 27663363, 104879772, 397629405, 1507527531, 5715470808, ...
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 (with the exception of the first
elements in the sequence). The usual Fibonacci numbers are a Fibonacci sequence of order 2. The cases
and
have been thoroughly investigated. The number of
compositions
Composition or Compositions may refer to:
Arts and literature
* Composition (dance), practice and teaching of choreography
*Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include ...
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
James Mark McGinnis BarrFull name as listed in (May 18, 1871December 15, 1950) was an electrical engineer, physicist, inventor, and polymath known for proposing the standard notation for the golden ratio. Born in America, but with English citi ...
in 1913.
Tribonacci numbers
The tribonacci numbers are like the Fibonacci numbers, but instead of starting with two predetermined terms, the sequence starts with three predetermined terms and each term afterwards is the sum of the preceding three terms. The first few tribonacci numbers are:
:
0,
0,
1,
1,
2,
4,
7,
13,
24,
44,
81,
149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, …
The series was first described formally by Agronomof in 1914,
but its first unintentional use is in the ''
Origin of Species
''On the Origin of Species'' (or, more completely, ''On the Origin of Species by Means of Natural Selection, or the Preservation of Favoured Races in the Struggle for Life''),The book's full original title was ''On the Origin of Species by Me ...
'' by
Charles R. Darwin. In the example of illustrating the growth of elephant population, he relied on the calculations made by his son,
George H. Darwin
Sir George Howard Darwin, (9 July 1845 – 7 December 1912) was an English barrister and astronomer, the second son and fifth child of Charles Darwin and Emma Darwin.
Biography
George H. Darwin was born at Down House, Kent, the fifth chil ...
.
The term tribonacci was suggested by Feinberg in 1963.
The tribonacci constant
:
is the ratio toward which adjacent tribonacci numbers tend. It is a root of the polynomial
, and also satisfies the equation
. It is important in the study of the
snub cube
In geometry, the snub cube, or snub cuboctahedron, is an Archimedean solid with 38 faces: 6 square (geometry), squares and 32 equilateral triangles. It has 60 edge (geometry), edges and 24 vertex (geometry), vertices.
It is a chiral polytope, ...
.
![TRIBONACCI](https://upload.wikimedia.org/wikipedia/commons/9/93/TRIBONACCI.jpg)
The reciprocal of the tribonacci constant, expressed by the relation
, can be written as:
:
The tribonacci numbers are also given by
:
where
denotes the
nearest integer function
Rounding means replacing a number with an approximate value that has a shorter, simpler, or more explicit representation. For example, replacing $ with $, the fraction 312/937 with 1/3, or the expression with .
Rounding is often done to ob ...
and
:
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:
:0, 0, 0, 1, 1, 2, 4, 8,
15,
29,
56,
108 108 may refer to:
* 108 (number)
* AD 108, a year
* 108 BC, a year
* 108 (artist) (born 1978), Italian street artist
* 108 (band), an American hardcore band
* 108 (emergency telephone number), an emergency telephone number in several states in Ind ...
, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312, 283953, 547337, …
The tetranacci constant is the ratio toward which adjacent tetranacci numbers tend. It is a root of the polynomial
, approximately 1.927561975482925 , 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
Higher orders
Pentanacci, hexanacci, heptanacci, octanacci and enneanacci numbers have been computed. The pentanacci numbers are:
:0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, …
Hexanacci numbers:
:0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, …
Heptanacci numbers:
:0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, …
Octanacci numbers:
:0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080, 16128, ...
Enneanacci numbers:
:0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144, 16272, ...
The limit of the ratio of successive terms of an
-nacci series tends to a root of the equation
(, , ).
An alternate recursive formula for the limit of ratio
of two consecutive
-nacci numbers can be expressed as
:
.
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 numbers. The limit of this ratio is 2 as
increases. An "infinacci" sequence, if one could be described, would after an infinite number of zeroes yield the sequence
:
.., 0, 0, 1,1, 2, 4, 8, 16, 32, …
which are simply the
powers of two
A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer as the exponent.
In a context where only integers are considered, is restricted to non-negative ...
.
The limit of the ratio for any
is the positive root
of the characteristic equation
:
The root
is in the
interval . The negative root of the characteristic equation is in the interval (−1, 0) 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
.
Fibonacci word
In analogy to its numerical counterpart, the
Fibonacci word
A Fibonacci word is a specific sequence of binary digits (or symbols from any two-letter alphabet). The Fibonacci word is formed by repeated concatenation in the same way that the Fibonacci numbers are formed by repeated addition.
It is a parad ...
is defined by:
:
where
denotes the concatenation of two strings. The sequence of Fibonacci strings starts:
: …
The length of each Fibonacci string is a Fibonacci number, and similarly there exists a corresponding Fibonacci string for each Fibonacci number.
Fibonacci strings appear as inputs for the
worst case
In computer science, best, worst, and average cases of a given algorithm express what the resource usage is ''at least'', ''at most'' and ''on average'', respectively. Usually the resource being considered is running time, i.e. time complexity, b ...
in some
computer algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ca ...
s.
If "a" and "b" represent two different materials or atomic bond lengths, the structure corresponding to a Fibonacci string is a
Fibonacci quasicrystal, an aperiodic
quasicrystal
A quasiperiodic crystal, or quasicrystal, is a structure that is ordered but not periodic. A quasicrystalline pattern can continuously fill all available space, but it lacks translational symmetry. While crystals, according to the classical cr ...
structure with unusual
spectral
''Spectral'' is a 2016 3D military science fiction, supernatural horror fantasy and action-adventure thriller war film directed by Nic Mathieu. Written by himself, Ian Fried, and George Nolfi from a story by Fried and Mathieu. The film stars ...
properties.
Convolved Fibonacci sequences
A convolved Fibonacci sequence is obtained applying a
convolution
In mathematics (in particular, functional analysis), convolution is a operation (mathematics), mathematical operation on two function (mathematics), functions ( and ) that produces a third function (f*g) that expresses how the shape of one is ...
operation to the Fibonacci sequence one or more times. Specifically, define
:
and
:
The first few sequences are
:
: 0, 0, 1, 2, 5, 10, 20, 38, 71, … .
:
: 0, 0, 0, 1, 3, 9, 22, 51, 111, … .
:
: 0, 0, 0, 0, 1, 4, 14, 40, 105, … .
The sequences can be calculated using the recurrence
:
The
generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary seri ...
of the
th convolution is
:
The sequences are related to the sequence of
Fibonacci polynomials In mathematics, the Fibonacci polynomials are a polynomial sequence which can be considered as a generalization of the Fibonacci numbers. The polynomials generated in a similar way from the Lucas numbers are called Lucas polynomials.
Definition
The ...
by the relation
:
where
is the
th derivative of
. Equivalently,
is the coefficient of
when
is expanded in powers of
.
The first convolution,
can be written in terms of the Fibonacci and Lucas numbers as
:
and follows the recurrence
:
Similar expressions can be found for
with increasing complexity as
increases. The numbers
are the row sums of
Hosoya's triangle.
As with Fibonacci numbers, there are several combinatorial interpretations of these sequences. For example
is the number of ways
can be written as an ordered sum involving only 0, 1, and 2 with 0 used exactly once. In particular
and 2 can be written , , , , .
Other generalizations
The
Fibonacci polynomials In mathematics, the Fibonacci polynomials are a polynomial sequence which can be considered as a generalization of the Fibonacci numbers. The polynomials generated in a similar way from the Lucas numbers are called Lucas polynomials.
Definition
The ...
are another generalization of Fibonacci numbers.
The
Padovan sequence
In number theory, the Padovan sequence is the sequence of integers ''P''(''n'') defined. by the initial values
:P(0)=P(1)=P(2)=1,
and the recurrence relation
:P(n)=P(n-2)+P(n-3).
The first few values of ''P''(''n'') are
:1, 1, 1, 2, 2, 3, 4, 5 ...
is generated by the recurrence
.
The
Narayana's cows
Nārāyaṇa Paṇḍita ( sa, नारायण पण्डित) (1340–1400) was an Indian mathematician. Plofker writes that his texts were the most significant Sanskrit mathematics treatises after those of Bhaskara II, other than the K ...
sequence is generated by the recurrence
.
A random Fibonacci sequence can be defined by tossing a coin for each position
of the sequence and taking
if it lands heads and
if it lands tails. Work by Furstenberg and Kesten guarantees that this sequence
almost surely
In probability theory, an event is said to happen almost surely (sometimes abbreviated as a.s.) if it happens with probability 1 (or Lebesgue measure 1). In other words, the set of possible exceptions may be non-empty, but it has probability 0. ...
grows exponentially at a constant rate: the constant is independent of the coin tosses and was computed in 1999 by
Divakar Viswanath. It is now known as
Viswanath's constant.
A repfigit, or
Keith number
In number theory, a Keith number or repfigit number (short for repetitive Fibonacci-like digit) is a natural number n in a given number base b with k digits such that when a sequence is created such that the first k terms are the k digits of n and ...
, is an integer such that, when its digits start a Fibonacci sequence with that number of digits, the original number is eventually reached. An example is 47, because the Fibonacci sequence starting with 4 and 7 reaches 47. A repfigit can be a tribonacci sequence if there are 3 digits in the number, a tetranacci number if the number has four digits, etc. The first few repfigits are:
:14, 19, 28, 47, 61, 75, 197, 742, 1104, 1537, 2208, 2580, 3684, 4788, 7385, 7647, 7909, …
Since the set of sequences satisfying the relation
is closed under termwise addition and under termwise multiplication by a constant, it can be viewed as a
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
. Any such sequence is uniquely determined by a choice of two elements, so the vector space is two-dimensional. If we abbreviate such a sequence as
, the Fibonacci sequence
and the shifted Fibonacci sequence
are seen to form a canonical basis for this space, yielding the identity:
:
for all such sequences . For example, if is the Lucas sequence , then we obtain
:
.
-generated Fibonacci sequence
We can define the -generated Fibonacci sequence (where is a positive rational number): if
:
where is the th prime, then we define
:
If
, then
, and if
, then
.
:
Semi-Fibonacci sequence
The semi-Fibonacci sequence is defined via the same recursion for odd-indexed terms
and
, but for even indices
,
. The bissection of odd-indexed terms
therefore verifies
and is strictly increasing. It yields the set of the ''semi-Fibonacci numbers''
: 1, 2, 3, 5, 6, 9, 11, 16, 17, 23, 26, 35, 37, 48, 53, 69, 70, 87, 93, 116, 119, 145, 154, ...
which occur as
.
References
External links
*
{{Fibonacci
Fibonacci numbers