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 other objects than numbers.
See also Negafibonacci.
The analytic function
has the property that Fe(n) = Fn for even integers n. Similarly, the analytic function:
satisfies Fo(n) = Fn for odd integers n.
Finally, putting these together, the analytic function
satisfies Fib(n)=Fn for all integers n.
This formula can be used to compute the generalized Fibonacci function of a complex variable. For example,
More generally, the range of g may be taken to be any abelian group (regarded as a Z-module). Then the Fibonacci sequences form a 2-dimensional Z-module in the same way.
Written in the form
a = 0 if and only if b = 0.
Thus the ratio between two consecutive elements converges to the golden ratio, except in the case of the sequence which is constantly zero.
Written in this form the simplest non-trivial example (a = b = 1) is the sequence of Lucas numbers:
We have L(1) = 1 and L(2) = 3. The properties include:
See also Fibonacci integer sequences modulo n.
where the normal Fibonacci sequence is the special case of P = 1 and Q = −1. Another kind of Lucas sequence begins with V(0) = 2, V(1) = P. Such sequences have applications in number theory and primality proving.
A Fibonacci sequence of order n is an integer sequence in which each sequence element is the sum of the previous n elements (with the exception of the first n elements in the sequence). The usual Fibonacci numbers are a Fibonacci sequence of order 2. The cases n=3 and n=4 have been thoroughly investigated.
The tribonacci constant is the ratio toward which adjacent tribonacci numbers tend. It is a root of the polynomial x3 − x2 − x − 1, approximately 1.83929, and also satisfies the equation x + x−3 = 2. It is important in the study of the snub cube.
The tribonacci numbers are also given by
where the outer brackets denote the nearest integer function and
The tetranacci constant is the ratio toward which adjacent tetranacci numbers tend. It is a root of the polynomial x4 − x3 − x2 − x − 1, approximately 1.92756, and also satisfies the equation x + x−4 = 2.
Thus, this has a limit as n increases. A 'polynacci' 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 powers of 2.
And the kth element of the n-nacci sequence is given by
A Coin Tossing Problem is related to the n-nacci sequence. The probability that no n consecutive tails will occur in m tosses of an idealized coin is
In analogy to its numerical counterpart, a Fibonacci string is defined by:
F_n := F(n):=begin{cases} b & mbox{if } n = 0; a & mbox{if } n = 1; F(n-1)+F(n-2) & mbox{if } n > 1. end{cases}
,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 some computer algorithms.
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 structure with unusual spectral properties.
The Padovan sequence is generated by the recurrence P(n) = P(n − 2) + P(n − 3).
A random Fibonacci sequence can be defined by tossing a coin for each position n of the sequence and taking F(n)=F(n−1)+F(n−2) if it lands heads and F(n)=F(n−1)−F(n−2) if it lands tails. Work by Furstenburg and Kesten guarantees that this sequence almost surely 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 is an integer, 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 (4,7,11,18,29,47) 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 :
Since the set of sequences satisfying the relation S(n) = S(n−1) + S(n−2) is closed under termwise addition and under termwise multiplication by a constant, it can be viewed as a vector space. 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 (S(0), S(1)), the Fibonacci sequence F(n) = (0, 1) and the shifted Fibonacci sequence F(n−1) = (1, 0) are seen to form a canonical basis for this space, yielding the identity:
for all such sequences S. For example, if S is the Lucas sequence 2, 1, 3, 4, 7, 11…, then we obtain .
In mathematics, the Fibonacci numbers are a sequence of numbers named after Leonardo of Pisa, known as Fibonacci. Fibonacci's 1202 book Liber Abaci introduced the sequence to Western European mathematics, although the sequence had been previously described in Indian mathematics.
The first number of the sequence is 0, the second number is 1, and each subsequent number is equal to the sum of the previous two numbers of the sequence itself, yielding the sequence 0, 1, 1, 2, 3, 5, 8, etc. In mathematical terms, it is defined by the following recurrence relation:
F_n =begin{cases} 0 & mbox{if } n = 0; 1 & mbox{if } n = 1; F_{n-1}+F_{n-2} & mbox{if } n > 1. end{cases}
That is, after two starting values, each number is the sum of the two preceding numbers. The first Fibonacci numbers , also denoted as Fn, for n = 0, 1, 2, … ,20 are:
| F0 | F1 | F2 | F3 | F4 | F5 | F6 | F7 | F8 | F9 | F10 | F11 | F12 | F13 | F14 | F15 | F16 | F17 | F18 | F19 | F20 |
| 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 | 233 | 377 | 610 | 987 | 1597 | 2584 | 4181 | 6765 |
Every 3rd number of the sequence is even and more generally, every kth number of the sequence is a multiple of Fk.
The sequence extended to negative index n satisfies Fn = Fn−1 + Fn−2 for all integers n, and F−n = (−1)n+1Fn:
.., −8, 5, −3, 2, −1, 1, followed by the sequence above.
Sanskrit vowel sounds can be long (L) or short (S), and Virahanka's analysis, which came to be known as mātrā-vṛtta, wishes to compute how many metres (mātrās) of a given overall length can be composed of these syllables. If the long syllable is twice as long as the short, the solutions are:
A pattern of length n can be formed by adding S to a pattern of length n − 1, or L to a pattern of length n − 2; and the prosodicists showed that the number of patterns of length n is the sum of the two previous numbers in the sequence. Donald Knuth reviews this work in The Art of Computer Programming as equivalent formulations of the bin packing problem for items of lengths 1 and 2.
In the West, the sequence was first studied by Leonardo of Pisa, known as Fibonacci, in his Liber Abaci (1202). He considers the growth of an idealised (biologically unrealistic) rabbit population, assuming that:
The laws of this are that each pair of rabbits has 2 pairs in its lifetime, and dies.
Let the population at month n be F(n). At this time, only rabbits who were alive at month n − 2 are fertile and produce offspring, so F(n − 2) pairs are added to the current population of F(n − 1). Thus the total is F(n) = F(n − 1) + F(n − 2).
The Fibonacci recursion
is similar to the defining equation of the golden ratio in the form
which is also known as the generating polynomial of the recursion.
By definition is a root of the equation, and the other root is . Therefore:
and
Both and are geometric series (for n = 1, 2, 3, ...) that satisfy the Fibonacci recursion. The first series grows exponentially; the second exponentially tends to zero, with alternating signs. Because the Fibonacci recursion is linear, any linear combination of these two series will also satisfy the recursion. These linear combinations form a two-dimensional linear vector space; the original Fibonacci sequence can be found in this space.
Linear combinations of series and , with coefficients a and b, can be defined by
All thus-defined series satisfy the Fibonacci recursion
and
establishing the base cases of the induction, proving that
Therefore, for any two starting values, a combination can be found such that the function is the exact closed formula for the series.
Johannes Kepler observed that the ratio of consecutive Fibonacci numbers converges. He wrote that "as 5 is to 8 so is 8 to 13, practically, and as 8 is to 13, so is 13 to 21 almost”, and concluded that the limit approaches the golden ratio .
Proof:
It follows from the explicit formula that for any real
&= varphiend{align} because and thus
A 2-dimensional system of linear difference equations that describes the Fibonacci sequence is
or
The eigenvalues of the matrix A are and , and the elements of the eigenvectors of A, and , are in the ratios and
This matrix has a determinant of −1, and thus it is a 2×2 unimodular matrix. This property can be understood in terms of the continued fraction representation for the golden ratio:
The matrix representation gives the following closed expression for the Fibonacci numbers:
Taking the determinant of both sides of this equation yields Cassini's identity
Additionally, since for any square matrix , the following identities can be derived:
In particular, with ,
The question may arise whether a positive integer is a Fibonacci number. Since is the closest integer to , the most straightforward, brute-force test is the identity
Alternatively, a positive integer is a Fibonacci number if and only if one of or is a perfect square.
A slightly more sophisticated test uses the fact that the convergents of the continued fraction representation of are ratios of successive Fibonacci numbers, that is the inequality
Most identities involving Fibonacci numbers draw from combinatorial arguments. F(n) can be interpreted as the number of ways summing 1's and 2's to n − 1, with the convention that F(0) = 0, meaning no sum will add up to −1, and that F(1) = 1, meaning the empty sum will "add up" to 0. Here the order of the summands matters. For example, 1 + 2 and 2 + 1 are considered two different sums and are counted twice.
We must establish that the sequence of numbers defined by the combinatorial interpretation above satisfy the same recurrence relation as the Fibonacci numbers (and so are indeed identical to the Fibonacci numbers).
The set of F(n+1) ways of making ordered sums of 1's and 2's that sum to n may be divided into two non-overlapping sets. The first set contains those sums whose first summand is 1; the remainder sums to n−1, so there are F(n) sums in the first set. The second set contains those sums whose first summand is 2; the remainder sums to n−2, so there are F(n−1) sums in the second set. The first summand can only be 1 or 2, so these two sets exhaust the original set. Thus F(n+1) = F(n) + F(n−1).
We count the number of ways summing 1's and 2's to n + 1 such that at least one of the summands is 2.
As before, there are F(n + 2) ways summing 1's and 2's to n + 1 when n ≥ 0. Since there is only one sum of n + 1 that does not use any 2, namely 1 + … + 1 (n + 1 terms), we subtract 1 from F(n + 2).
Equivalently, we can consider the first occurrence of 2 as a summand. If, in a sum, the first summand is 2, then there are F(n) ways to the complete the counting for n − 1. If the second summand is 2 but the first is 1, then there are F(n − 1) ways to complete the counting for n − 2. Proceed in this fashion. Eventually we consider the (n + 1)th summand. If it is 2 but all of the previous n summands are 1's, then there are F(0) ways to complete the counting for 0. If a sum contains 2 as a summand, the first occurrence of such summand must take place in between the first and (n + 1)th position. Thus F(n) + F(n − 1) + … + F(0) gives the desired counting.
This identity has slightly different forms for , depending on whether k is odd or even.
By induction for :
This identity can be established in two stages. First, we count the number of ways summing 1s and 2s to −1, 0, …, or n + 1 such that at least one of the summands is 2.
By our second identity, there are F(n + 2) − 1 ways summing to n + 1; F(n + 1) − 1 ways summing to n; …; and, eventually, F(2) − 1 way summing to 1. As F(1) − 1 = F(0) = 0, we can add up all n + 1 sums and apply the second identity again to obtain
On the other hand, we observe from the second identity that there are
……
Adding up all n + 1 sums, we see that there are
Since the two methods of counting refer to the same number, we have
Finally, we complete the proof by subtracting the above identity from n + 1 times the second identity.
from which other identities for specific values of k, n, and c can be derived below, including
for all integers n and k. Dijkstra points out that doubling identities of this type can be used to calculate Fn using O(log n) long multiplication operations of size n bits; if the fast Schönhage-Strassen multiplication algorithm is used, this is O(n log2 n log log n) bit operations. Notice that, with the definition of Fibonacci numbers with negative n given in the introduction, this formula reduces to the double n formula when k = 0.
Other identities include relationships to the Lucas numbers, which have the same recursive properties but start with L0=2 and L1=1. These properties include F2n=FnLn.
There are also scaling identities, which take you from Fn and Fn+1 to a variety of things of the form Fan+b; for instance
by Cassini's identity.
These can be found experimentally using lattice reduction, and are useful in setting up the special number field sieve to factorize a Fibonacci number. Such relations exist in a very general sense for numbers defined by recurrence relations, see the section on multiplication formulae under Perrin numbers for details.
This series has a simple and interesting closed-form solution for
This solution can be proven by using the Fibonacci recurrence to expand each coefficient in the infinite sum defining :
&= x + x s(x) + x^2 s(x)end{align}
Solving the equation for results in the closed form solution.
In particular, math puzzle-books note the curious value , or more generally
for all integers .
Conversely,
Infinite sums over reciprocal Fibonacci numbers can sometimes be evaluated in terms of theta functions. For example, we can write the sum of every odd-indexed reciprocal Fibonacci number as
and the sum of squared reciprocal Fibonacci numbers as
If we add 1 to each Fibonacci number in the first sum, there is also the closed form
and there is a nice nested sum of squared Fibonacci numbers giving the reciprocal of the golden ratio,
Results such as these make it plausible that a closed formula for the plain sum of reciprocal Fibonacci numbers could be found, but none is yet known. Despite that, the reciprocal Fibonacci constant
has been proved irrational by Richard André-Jeannin.
With the exceptions of 1, 8 and 144 (F0 = F1, F6 and F12) every Fibonacci number has a prime factor that is not a factor of any smaller Fibonacci number (Carmichael's theorem). 0, 1, and 144 are also the only square Fibonacci numbers.
No Fibonacci number greater than F6 = 8 is one greater or one less than a prime number.
Any three consecutive Fibonacci numbers, taken two at a time, are relatively prime: that is,
If n is odd all the odd divisors of Fn are ≡ 1 (mod 4).
This is equivalent to saying that for odd n all the odd prime factors of Fn are ≡ 1 (mod 4).
For example, F1 = 1, F3 = 2, F5 = 5, F7 = 13, F9 = 34 = 2×17, F11 = 89, F13 = 233, F15 = 610 = 2×5×61
There are some interesting formulas connecting the Fibonacci numbers and the Legendre symbol
If p is a prime number then
For example,
Also, if p ≠ 5 is an odd prime number then:
Examples of all the cases:
For example, let n = 1:
F1+F2+...+F10 = 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 = 143 = 11×13
n = 2:
F2+F3+...+F11 = 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 + 89 = 231 = 11×21
n = 3:
F3+F4+...+F12 = 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 + 89 + 144= 374 = 11×34
In fact, the identity is true for all integers n, not just positive ones:
n = 0:
F0+F1+...+F9 = 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 = 88 = 11×8
n = −1:
F−1+F0+...+F8 = 1 + 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 = 55 = 11×5
n = −2:
F−2+F−1+F0+...+F7 = −1 + 1 + 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 = 33 = 11×3
The first triangle in this series has sides of length 5, 4, and 3. Skipping 8, the next triangle has sides of length 13, 12 (5 + 4 + 3), and 5 (8 − 3). Skipping 21, the next triangle has sides of length 34, 30 (13 + 12 + 5), and 16 (21 − 5). This series continues indefinitely. The triangle sides a, b, c can be calculated directly:
These formulas satisfy for all n, but they only represent triangle sides when .
Any four consecutive Fibonacci numbers Fn, Fn+1, Fn+2 and Fn+3 can also be used to generate a Pythagorean triple in a different way:
For every integer d greater than 1 there are either 4 or 5 Fibonacci numbers with d digits in base 10.
The Fibonacci numbers are important in the run-time analysis of Euclid's algorithm to determine the greatest common divisor of two integers: the worst case input for this algorithm is a pair of consecutive Fibonacci numbers.
Yuri Matiyasevich was able to show that the Fibonacci numbers can be defined by a Diophantine equation, which led to his original solution of Hilbert's tenth problem.
The Fibonacci numbers occur in the sums of "shallow" diagonals in Pascal's triangle and Lozanić's triangle (see "Binomial coefficient"). (They occur more obviously in Hosoya's triangle).
Every positive integer can be written in a unique way as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers. This is known as Zeckendorf's theorem, and a sum of Fibonacci numbers that satisfies these conditions is called a Zeckendorf representation.
The Fibonacci numbers and principle is also used in the financial markets. It is used in trading algorithms, applications and strategies. Some typical forms include: the Fibonacci fan, Fibonacci Arc, Fibonacci Retracement and the Fibonacci Time Extension.
Fibonacci numbers are used by some pseudorandom number generators.
Fibonacci numbers are used in a polyphase version of the merge sort algorithm in which an unsorted list is divided into two lists whose lengths correspond to sequential Fibonacci numbers - by dividing the list so that the two parts have lengths in the approximate proportion φ. A tape-drive implementation of the polyphase merge sort was described in The Art of Computer Programming.
Fibonacci numbers arise in the analysis of the Fibonacci heap data structure.
A one-dimensional optimization method, called the Fibonacci search technique, uses Fibonacci numbers.
The Fibonacci number series is used for optional lossy compression in the IFF 8SVX audio file format used on Amiga computers. The number series compands the original audio wave similar to logarithmic methods e.g. µ-law.
In music, Fibonacci numbers are sometimes used to determine tunings, and, as in visual art, to determine the length or size of content or formal elements. It is commonly thought that the first movement of Béla Bartók's Music for Strings, Percussion, and Celesta was structured using Fibonacci numbers.
Since the conversion factor 1.609344 for miles to kilometers is close to the golden ratio (denoted φ), the decomposition of distance in miles into a sum of Fibonacci numbers becomes nearly the kilometer sum when the Fibonacci numbers are replaced by their successors. This method amounts to a radix 2 number register in golden ratio base φ being shifted. To convert from kilometers to miles, shift the register down the Fibonacci sequence instead.
Fibonacci sequences appear in biological settings, in two consecutive Fibonacci numbers, such as branching in trees, arrangement of leaves on a stem, the fruitlets of a pineapple, the flowering of artichoke, an uncurling fern and the arrangement of a pine cone. In addition, numerous poorly substantiated claims of Fibonacci numbers or golden sections in nature are found in popular sources, e.g. relating to the breeding of rabbits, the spirals of shells, and the curve of waves. The Fibonacci numbers are also found in the family tree of honeybees.
Przemyslaw Prusinkiewicz advanced the idea that real instances can be in part understood as the expression of certain algebraic constraints on free groups, specifically as certain Lindenmayer grammars.
A model for the pattern of florets in the head of a sunflower was proposed by H. Vogel in 1979. This has the form
Thus, a male bee will always have one parent, and a female bee will have two.
If one traces the ancestry of any male bee (1 bee), he has 1 female parent (1 bee). This female had 2 parents, a male and a female (2 bees). The female had two parents, a male and a female, and the male had one female (3 bees). Those two females each had two parents, and the male had one (5 bees). This sequence of numbers of parents is the Fibonacci sequence.
This is an idealization that does not describe actual bee ancestries. In reality, some ancestors of a particular bee will always be sisters or brothers, thus breaking the lineage of distinct parents.