FACTOID # 7: The top five best educated states are all in the Northeast.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > Fibonacci number
A tiling with squares whose sides are successive Fibonacci numbers in length

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.[1][2] Image File history File links FibonacciBlocks. ... Image File history File links FibonacciBlocks. ... For other meanings of mathematics or uses of math and maths, see Mathematics (disambiguation) and Math (disambiguation). ... For other senses of this word, see sequence (disambiguation). ... Drawing of Leonardo Pisano Leonardo of Pisa or Leonardo Pisano (Pisa, c. ... Liber Abaci (1202) is an historic book on arithmetic by Leonardo of Pisa, known later by his nickname Fibonacci. ... This article is under construction. ...

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. In mathematical terms, it is defined by the following recurrence relation: In mathematics, a recurrence relation, also known as a difference equation, is an equation which defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms. ...

$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 (sequence A000045 in OEIS), also denoted as Fn, for n = 0, 1, 2, … ,20 are:[3][4] The On-Line Encyclopedia of Integer Sequences (OEIS) is an extensive searchable database of integer sequences, freely available on the Web. ...

 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
A Fibonacci spiral created by drawing arcs connecting the opposite corners of squares in the Fibonacci tiling; this one uses squares of sizes 1, 1, 2, 3, 5, 8, 13, 21, and 34; see Golden spiral
A plot of the Fibonacci sequence from 0 to 1597

Every 3rd number of the sequence is even and more generally, every kth number of the sequence is a multiple of Fk. Approximate and true Golden Spirals. ...

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.

The Fibonacci numbers first appeared, under the name mātrāmeru (mountain of cadence), in the work of the Sanskrit grammarian Pingala (Chandah-shāstra, the Art of Prosody, 450 or 200 BC). Prosody was important in ancient Indian ritual because of an emphasis on the purity of utterance. The Indian mathematician Virahanka (6th century AD) showed how the Fibonacci sequence arose in the analysis of metres with long and short syllables. Subsequently, the Jain philosopher Hemachandra (c.1150) composed a well-known text on these. A commentary on Virahanka's work by Gopāla in the 12th century also revisits the problem in some detail. Look up Cadence, cadence in Wiktionary, the free dictionary. ... Sanskrit grammatical tradition (, one of the six Vedanga disciplines) begins in late Vedic India, and culminates in the Aá¹£á¹­ÄdhyÄyÄ« of PÄá¹‡ini (ca. ... Pingala (à¤ªà¤¿à¤™à¥à¤—à¤² ) is the supposed author of the Chandas shastra (, also Chandas sutra ), a Sanskrit treatise on prosody considered one of the Vedanga. ... Centuries: 6th century BC - 5th century BC - 4th century BC Decades: 500s BC 490s BC 480s BC 470s BC 460s BC - 450s BC - 440s BC 430s BC 420s BC 410s BC 400s BC Years: 455 BC 454 BC 453 BC 452 BC 451 BC - 450 BC - 449 BC 448 BC... The eastern hemisphere in 200 BC. Antiochus IIIs forces continue their invasion of Coele Syria, defeating the Egyptian general Scopas at Panion near the source of the Jordan River, and thus gaining control of Palestine. ... In linguistics, prosody refers to intonation, rhythm, and vocal stress in speech. ... Here is a chronology of the main Indian mathematicians: BC Yajnavalkya, 1800 BC, the author of the altar mathematics of the Shatapatha Brahmana. ... Virahanka (à¤µà¤¿à¤°à¤¹à¤¾à¤™à¥à¤•) was an Indian prosodicist who is also known for his work on mathematics. ... The verses of the Vedas have a variety of different meters. ... JAIN is an activity within the Java Community Process, developing APIs for the creation of telephony (voice and data) services. ... Hemachandra SurÄ« ({{lang-sa|à¤¹à¥‡à¤®à¤šà¤¨à¥à¤¦à¥à¤° à¤¸à¥‚à¤°à¥€) (1089â€“1172) was an Indian Jaina scholar, poet, and polymath who wrote on grammar, philosophy, prosody, and contemporary history. ... Events Åhus, Sweden gains city privileges City of Airdrie, Scotland founded King Sverker I of Sweden is deposed and succeeded by Eric IX of Sweden. ... Gopala was an Indian mathematician, who studied the Fibonacci numbers in 1135, more than half a century before Fibonacci popularized these numbers in Europe. ...

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:

1 mora: S (1 pattern)
2 morae: SS; L (2)
3 morae: SSS, SL; LS (3)
4 morae: SSSS, SSL, SLS; LSS, LL (5)
5 morae: SSSSS, SSSL, SSLS, SLSS, SLL; LSSS, LSL, LLS (8)
6 morae: SSSSSS, SSSSL, SSSLS, SSLSS, SLSSS, LSSSS, SSLL, SLSL, SLLS, LSSL, LSLS, LLSS, LLL (13)
7 morae: SSSSSSS, SSSSSL, SSSSLS, SSSLSS, SSLSSS, SLSSSS, LSSSSS, SSSLL, SSLSL, SLSSL, LSSSL, SSLLS, SLSLS, LSSLS, SLLSS, LSLSS, LLSSS, SLLL, LSLL, LLSL, LLLS (21)

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. Mora (plural moras or morae) is a unit of sound used in phonology that determines syllable weight (which in turn determines stress or timing) in some languages. ... Donald Ervin Knuth ( or Ka-NOOTH[1], Chinese: [2]) (b. ... Cover of books The Art of Computer Programming[1] is a comprehensive monograph written by Donald Knuth which covers many kinds of programming algorithms and their analysis. ... In computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. ...

In the West, the sequence was first studied by Leonardo of Pisa, known as Fibonacci, in his Liber Abaci (1202)[5]. He considers the growth of an idealised (biologically unrealistic) rabbit population, assuming that: For the number sequence, see Fibonacci number. ... Liber Abaci (1202) is an historic book on arithmetic by Leonardo of Pisa, known later by his nickname Fibonacci. ... // Events August 1 - Arthur of Brittany captured in Mirebeau, north of Poitiers Beginning of the Fourth Crusade. ...

• In the "zeroth" month, there is one pair of rabbits (additional pairs of rabbits = 0)
• In the first month, the first pair begets another pair (additional pairs of rabbits = 1)
• In the second month, both pairs of rabbits have another pair, and the first pair dies (additional pairs of rabbits = 1)
• In the third month, the second pair and the new two pairs have a total of three new pairs, and the older second pair dies. (additional pairs of rabbits = 2)

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).[6]

## Relation to the Golden Ratio

Not to be confused with Golden mean (philosophy), the felicitous middle between two extremes, Golden numbers, an indicator of years in astronomy and calendar studies, or the Golden Rule. ...

### Closed form expression

Like every sequence defined by linear recurrence, the Fibonacci numbers have a closed-form solution. It has become known as Binet's formula, even though it was already known by Abraham de Moivre: In mathematics, a recurrence relation, also known as a difference equation, is an equation which defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms. ... In mathematics, an equation or system of equations is said to have a closed-form solution if, and only if, at least one solution can be expressed analytically in terms of a bounded number of well-known operations. ... Jacques Philippe Marie Binet was a catholic mathematician. ... Abraham de Moivre. ...

$Fleft(nright) = {{varphi^n-(1-varphi)^n} over {sqrt 5}}={{varphi^n-(-varphi)^{-n}} over {sqrt 5}}, ,$ where $varphi$ is the golden ratio (note, that $1-varphi=-1/varphi$, as can be seen from the defining equation below).

The Fibonacci recursion Not to be confused with Golden mean (philosophy), the felicitous middle between two extremes, Golden numbers, an indicator of years in astronomy and calendar studies, or the Golden Rule. ...

$F(n+2)-F(n+1)-F(n)=0,$

is similar to the defining equation of the golden ratio in the form

$x^2-x-1=0,,$

which is also known as the generating polynomial of the recursion.

#### Proof by induction

Any root of the equation above satisfies $begin{matrix}x^2=x+1,end{matrix},$ and multiplying by $x^{n-1},$ shows: Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. ...

$x^{n+1} = x^n + x^{n-1},$

By definition $varphi$ is a root of the equation, and the other root is $1-varphi=-1/varphi, .$. Therefore:

$varphi^{n+1} = varphi^n + varphi^{n-1},$

and

$(1-varphi)^{n+1} = (1-varphi)^n + (1-varphi)^{n-1}, .$

Both $varphi^{n}$ and $(1-varphi)^{n}=(-1/varphi)^{n}$ 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. In mathematics, a geometric progression is a sequence of numbers such that the quotient of any two successive members of the sequence is a constant called the common ratio of the sequence. ... In mathematics, linear combinations are a concept central to linear algebra and related fields of mathematics. ...

Linear combinations of series $varphi^{n}$ and $(1-varphi)^{n}$, with coefficients a and b, can be defined by

$F_{a,b}(n) = avarphi^n+b(1-varphi)^n$ for any real $a,b, .$

All thus-defined series satisfy the Fibonacci recursion

begin{align} F_{a,b}(n+1) &= avarphi^{n+1}+b(1-varphi)^{n+1} &=a(varphi^{n}+varphi^{n-1})+b((1-varphi)^{n}+(1-varphi)^{n-1}) &=a{varphi^{n}+b(1-varphi)^{n}}+a{varphi^{n-1}+b(1-varphi)^{n-1}} &=F_{a,b}(n)+F_{a,b}(n-1),. end{align}

Requiring that Fa,b(0) = 0 and Fa,b(1) = 1 yields $a=1/sqrt 5$ and $b=-1/sqrt 5$, resulting in the formula of Binet we started with. It has been shown that this formula satisfies the Fibonacci recursion. Furthermore, an explicit check can be made:

$F_{a,b}(0)=frac{1}{sqrt 5}-frac{1}{sqrt 5}=0,!$

and

$F_{a,b}(1)=frac{varphi}{sqrt 5}-frac{(1-varphi)}{sqrt 5}=frac{-1+2varphi}{sqrt 5}=frac{-1+(1+sqrt 5)}{sqrt 5}=1,$

establishing the base cases of the induction, proving that

$F(n)={{varphi^n-(1-varphi)^n} over {sqrt 5}}$ for all $n, .$

Therefore, for any two starting values, a combination a,b can be found such that the function $F_{a,b}(n),$ is the exact closed formula for the series.

#### Computation by rounding

Since $begin{matrix}|1-varphi|^n/sqrt 5 < 1/2end{matrix}$ for all $ngeq 0$, the number F(n) is the closest integer to $varphi^n/sqrt 5, .$ Therefore it can be found by rounding, or in terms of the floor function: Rounding is the process of reducing the number of significant digits in a number. ... The floor and fractional part functions In mathematics, the floor function of a real number x, denoted or floor(x), is the largest integer less than or equal to x (formally, ). For example, floor(2. ...

$F(n)=bigglfloorfrac{varphi^n}{sqrt 5} + frac{1}{2}biggrfloor.$

### Limit of consecutive quotients

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 $varphi$.[7] Kepler redirects here. ...

$lim_{ntoinfty}frac{F(n+1)}{F(n)}=varphi,$

This convergence does not depend on the starting values chosen, excluding 0, 0.

Proof:

It follows from the explicit formula that for any real $a ne 0, , b ne 0 ,$

begin{align} lim_{ntoinfty}frac{F_{a,b}(n+1)}{F_{a,b}(n)} &= lim_{ntoinfty}frac{avarphi^{n+1}-b(1-varphi)^{n+1}}{avarphi^n-b(1-varphi)^n} &= lim_{ntoinfty}frac{avarphi-b(1-varphi)(frac{1-varphi}{varphi})^n}{a-b(frac{1-varphi}{varphi})^n} &= varphi end{align}

because $bigl|{tfrac{1-varphi}{varphi}}bigr| < 1$ and thus $lim_{ntoinfty}left(tfrac{1-varphi}{varphi}right)^n=0 .$

### Decomposition of powers of the golden ratio

Since the golden ratio satisfies the equation

$varphi^2=varphi+1,,$

this expression can be used to decompose higher powers $varphi^n$ as a linear function of lower powers, which in turn can be decomposed all the way down to a linear combination of $varphi$ and 1. The resulting recurrence relationships yield Fibonacci numbers as the linear coefficients, thus closing the loop: In mathematics, a recurrence relation, also known as a difference equation, is an equation which defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms. ...

$varphi^n=F(n)varphi+F(n-1).$

This expression is also true for $n , <, 1 ,$ if the Fibonacci sequence $F(n) ,$ is extended to negative integers using the Fibonacci rule $F(n) = F(n-1) + F(n-2) . ,$ In mathematics, the Fibonacci numbers form a sequence defined recursively by: F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2), for integer n > 1 That is, after two starting values, each number is the sum of the two preceding numbers. ...

## Matrix form

A 2-dimensional system of linear difference equations that describes the Fibonacci sequence is In mathematics, a recurrence relation, also known as a difference equation, is an equation which defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms. ...

${F_{k+2} choose F_{k+1}} = begin{pmatrix} 1 & 1 1 & 0 end{pmatrix} {F_{k+1} choose F_{k}}$

or

$vec F_{k+1} = A vec F_{k}.,$

The eigenvalues of the matrix A are $varphi,!$ and $(1-varphi),!$, and the elements of the eigenvectors of A, ${varphi choose 1}$ and ${1 choose -varphi}$, are in the ratios $varphi,!$ and $(1-varphi,!).$ In mathematics, a number is called an eigenvalue of a matrix if there exists a nonzero vector such that the matrix times the vector is equal to the same vector multiplied by the eigenvalue. ... In linear algebra, the eigenvectors (from the German eigen meaning own) of a linear operator are non-zero vectors which, when operated on by the operator, result in a scalar multiple of themselves. ...

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: In algebra, a determinant is a function depending on n that associates a scalar, det(A), to every nÃ—n square matrix A. The fundamental geometric meaning of a determinant is as the scale factor for volume when A is regarded as a linear transformation. ... In mathematics, a unimodular matrix is a square matrix with determinant +1 or -1. ... In mathematics, a continued fraction is an expression such as where a0 is some integer and all the other numbers an are positive integers. ...

$varphi =1 + cfrac{1}{1 + cfrac{1}{1 + cfrac{1}{;;ddots,}}} ;.$

The Fibonacci numbers occur as the ratio of successive convergents of the continued fraction for $varphi,!$, and the matrix formed from successive convergents of any continued fraction has a determinant of +1 or −1.

The matrix representation gives the following closed expression for the Fibonacci numbers: In mathematics, an equation or system of equations is said to have a closed-form solution if, and only if, at least one solution can be expressed analytically in terms of a bounded number of well-known operations. ...

$begin{pmatrix} 1 & 1 1 & 0 end{pmatrix}^n = begin{pmatrix} F_{n+1} & F_n F_n & F_{n-1} end{pmatrix}.$

Taking the determinant of both sides of this equation yields Cassini's identity Cassinis identity is a mathematical identity for the Fibonacci numbers. ...

$(-1)^n = F_{n+1}F_{n-1} - F_n^2.,$

Additionally, since AnAm = Am + n for any square matrix A, the following identities can be derived:

${F_n}^2 + {F_{n-1}}^2 = F_{2n-1},,$
$F_{n+1}F_{m} + F_n F_{m-1} = F_{m+n}.,$

For the first one of these, there is a related identity:

$(2F_{n-1}+F_n)F_n = (F_{n-1}+F_{n+1})F_n = F_{2n}.,$

For another way to derive the F2n + k formulas see the "EWD note" by Dijkstra[8]. Portrait of Edsger Dijkstra (courtesy Brian Randell) Edsger Wybe Dijkstra (Rotterdam, May 11, 1930 – Nuenen, August 6, 2002) was a Dutch computer scientist. ...

## Recognizing Fibonacci numbers

The question may arise whether a positive integer z is a Fibonacci number. Since F(n) is the closest integer to $varphi^n/sqrt{5}$, the most straightforward, brute-force test is the identity

$Fbigg(bigglfloorlog_varphi(sqrt{5}z)+frac{1}{2}biggrfloorbigg)=z,$

which is true if and only if z is a Fibonacci number. â†” â‡” â‰¡ logical symbols representing iff. ...

Alternatively, a positive integer z is a Fibonacci number if and only if one of 5z2 + 4 or 5z2 − 4 is a perfect square.[9] The term perfect square is used in mathematics in two meanings: an integer which is the square of some other integer, i. ...

A slightly more sophisticated test uses the fact that the convergents of the continued fraction representation of $varphi$ are ratios of successive Fibonacci numbers, that is the inequality A convergent is one of a sequence of rational values obtained by evaluating successive truncations of a continued fraction. ... In mathematics, a continued fraction is an expression such as where a0 is some integer and all the other numbers an are positive integers. ...

$bigg|varphi-frac{p}{q}bigg|

(with coprime positive integers p, q) is true if and only if p and q are successive Fibonacci numbers. From this one derives the criterion that z is a Fibonacci number if and only if the closed interval In mathematics, the integers a and b are said to be coprime or relatively prime if they have no common factor other than 1 and âˆ’1, or equivalently, if their greatest common divisor is 1. ... In elementary algebra, an interval is a set that contains every real number between two indicated numbers, and possibly the two numbers themselves. ...

$bigg[varphi z-frac{1}{z},varphi z+frac{1}{z}bigg]$

contains a positive integer.[10]

## Identities

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. A combinatorial proof is a method of proving a statement, usually a combinatorics identity, by counting some carefully chosen object in different ways to obtain different expressions in the statement (see also double counting). ...

### First Identity

Fn + 1 = Fn + Fn − 1
The nth Fibonacci number is the sum of the previous two Fibonacci numbers.

#### Proof

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

### Second Identity

$sum_{i=0}^n F_i = F_{n+2} - 1$
The sum of the first n Fibonacci numbers is the (n+2)nd Fibonacci number minus 1.

#### Proof

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.

### Third Identity

$sum_{i=0}^n iF_i = nF_{n+2} - F_{n+3} + 2$

#### Proof

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

[F(n + 2) − 1] + [F(n + 1) − 1] + … + [F(2) − 1]
= [F(n + 2) − 1] + [F(n + 1) − 1] + … + [F(2) − 1] + [F(1) − 1] + F(0)
= F(n + 2) + [F(n + 1) + … + F(1) + F(0)] − (n + 2)
= F(n + 2) + [F(n + 3) − 1] − (n + 2)
= F(n + 2) + F(n + 3) − (n + 3).

On the other hand, we observe from the second identity that there are

• F(0) + F(1) + … + F(n − 1) + F(n) ways summing to n + 1;
• F(0) + F(1) + … + F(n − 1) ways summing to n;

……

• F(0) way summing to −1.

Adding up all n + 1 sums, we see that there are

• (n + 1) F(0) + n F(1) + … + F(n) ways summing to −1, 0, …, or n + 1.

Since the two methods of counting refer to the same number, we have

(n + 1) F(0) + n F(1) + … + F(n) = F(n + 2) + F(n + 3) − (n + 3)

Finally, we complete the proof by subtracting the above identity from n + 1 times the second identity.

### Fourth Identity

$sum_{i=0}^n {F_i}^2 = F_{n} F_{n+1}$
The sum of the first n Fibonacci numbers squared is the product of the nth and (n+1)th Fibonacci numbers.

### Identity for doubling n

$F_{2n} = F_{n+1}^2 - F_{n-1}^2 = F_n(F_{n+1}+F_{n-1})$

[11]

### Another Identity

Another identity useful for calculating Fn for large values of n is

$F_{kn+c} = sum_{i=0}^n {kchoose i} F_{c-i} F_N^i F_{n+1}^{k-i}$

[12]

From which other identities for specific values of k, n, and c can be derived below, including

$F_{2n+k} = F_k F_{n+1}^2 + 2 F_{k-1} F_{n+1} F_n + F_{k-2} F_n^2$

for all integers n and k. Dijkstra[8] points out that doubling identities of this type can be used to calculate Fn using O(log n) arithmetic 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. Portrait of Edsger Dijkstra (courtesy Brian Randell) Edsger Wybe Dijkstra (Rotterdam, May 11, 1930 – Nuenen, August 6, 2002) was a Dutch computer scientist. ...

(From practical standpoint it should be noticed that the calculation involves manipulation of numbers with length (number of digits) ${rm Theta}(n),$. Thus the actual performance depends mainly upon efficiency of the implemented long multiplication, and usually is ${rm Theta}(n ,log n)$ or ${rm Theta}(n ^{log_2 3})$.) A multiplication algorithm is an algorithm (or method) to multiply two numbers. ...

### Other identities

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. The Lucas numbers 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. ...

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

$F_{3n} = 2F_n^3 + 3F_n F_{n+1} F_{n-1} = 5F_{n}^3 + 3 (-1)^n F_{n}$ by Cassini's identity.

$F_{3n+1} = F_{n+1}^3 + 3 F_{n+1}F_n^2 - F_n^3$

$F_{3n+2} = F_{n+1}^3 + 3 F_{n+1}^2F_n + F_n^3$

$F_{4n} = 4F_nF_{n+1}(F_{n+1}^2 + 2F_n^2) - 3F_n^2(F_n^2 + 2F_{n+1}^2)$

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. The Lenstraâ€“Lenstraâ€“LovÃ¡sz lattice basis reduction (LLL) is a polynomial time algorithm which, given a lattice basis as input, outputs a basis with short, nearly orthogonal vectors. ... The special number field sieve (SNFS) is a special-purpose integer factorization algorithm. ... ... In mathematics, the Perrin numbers are defined by the recurrence relation P(0) = 3, P(1) = 0, P(2) = 2, and P(n) = P(n âˆ’ 2) + P(n âˆ’ 3) for n > 2. ...

## Power series

The generating function of the Fibonacci sequence is the power series In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an that is indexed by the natural numbers. ... In mathematics, a power series (in one variable) is an infinite series of the form where the coefficients an, the center c, and the argument x are usually real or complex numbers. ...

$s(x)=sum_{k=0}^{infty} F_k x^k.$

This series has a simple and interesting closed-form solution for $|x| < 1/varphi$

$s(x)=frac{x}{1-x-x^2}.$

This solution can be proven by using the Fibonacci recurrence to expand each coefficient in the infinite sum defining s(x):

begin{align} s(x) &= sum_{k=0}^{infty} F_k x^k &= F_0 + F_1x + sum_{k=2}^{infty} left( F_{k-1} + F_{k-2} right) x^k &= x + sum_{k=2}^{infty} F_{k-1} x^k + sum_{k=2}^{infty} F_{k-2} x^k &= x + xsum_{k=0}^{infty} F_k x^k + x^2sum_{k=0}^{infty} F_k x^k &= x + x s(x) + x^2 s(x) end{align}

Solving the equation s(x) = x + xs(x) + x2s(x) for s(x) results in the closed form solution.

In particular, math puzzle-books note the curious value $frac{s(frac{1}{10})}{10}=frac{1}{89}$, or more generally

$sum_{n = 1}^{infty}{frac {F(n)}{10^{(k + 1)(n + 1)}}} = frac {1}{10^{2k + 2} - 10^{k + 1} - 1}$

for all integers k > = 0.

Conversely,

$sum_{n=0}^infty,frac{F_n}{k^{n}},=,frac{k}{k^{2}-k-1}.$

## Reciprocal sums

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 In mathematics, theta functions are special functions of several complex variables. ...

$sum_{k=0}^infty frac{1}{F_{2k+1}} = frac{sqrt{5}}{4}vartheta_2^2 left(0, frac{3-sqrt 5}{2}right) ,$

and the sum of squared reciprocal Fibonacci numbers as

$sum_{k=1}^infty frac{1}{F_k^2} = frac{5}{24} left(vartheta_2^4left(0, frac{3-sqrt 5}{2}right) - vartheta_4^4left(0, frac{3-sqrt 5}{2}right) + 1 right).$

If we add 1 to each Fibonacci number in the first sum, there is also the closed form

$sum_{k=0}^infty frac{1}{1+F_{2k+1}} = frac{sqrt{5}}{2},$

and there is a nice nested sum of squared Fibonacci numbers giving the reciprocal of the golden ratio, Not to be confused with Golden mean (philosophy), the felicitous middle between two extremes, Golden numbers, an indicator of years in astronomy and calendar studies, or the Golden Rule. ...

$sum_{k=1}^infty frac{(-1)^{k+1}}{sum_{j=1}^k {F_{j}}^2} = frac{sqrt{5}-1}{2}.$

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 The reciprocal Fibonacci constant, or Ïˆ, is defined as the sum of the reciprocals of the Fibonacci numbers: The ratio of successive terms in this sum tends to the reciprocal of the golden ratio. ...

$psi = sum_{k=1}^{infty} frac{1}{F_k} = 3.359885666243 dots$

has been proved irrational by Richard André-Jeannin. In mathematics, an irrational number is any real number that is not a rational number â€” that is, it is a number which cannot be expressed as a fraction m/n, where m and n are integers, with n non-zero. ...

## Primes and divisibility

Main article: Fibonacci prime

A Fibonacci prime is a Fibonacci number that is prime (sequence A005478 in OEIS). The first few are: A Fibonacci prime is a Fibonacci number that is prime. ... In mathematics, a prime number (or a prime) is a natural number greater than 1 which has exactly two distinct natural number divisors: 1 and itself. ... The On-Line Encyclopedia of Integer Sequences (OEIS) is an extensive searchable database of integer sequences, freely available on the Web. ...

2, 3, 5, 13, 89, 233, 1597, 28657, 514229, …

Fibonacci primes with thousands of digits have been found, but it is not known whether there are infinitely many. They must all have a prime index, except F4 = 3. There are arbitrarily long runs of composite numbers and therefore also of composite Fibonacci numbers. In mathematics, the phrase arbitrarily large is used in contexts such as: is true for arbitrarily large which is actually shorthand for: for every , is true for at least one . ... A composite number is a positive integer which has a positive divisor other than one or itself. ...

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).[13] Carmichaels theorem, named after American mathematician R.D. Carmichael, states that for n greater than 12, the nth Fibonacci number F(n) has at least one prime factor that is not a factor of any earlier Fibonacci number. ...

No Fibonacci number greater than F6 = 8 is one greater or one less than a prime number.[14]

Any three consecutive Fibonacci numbers, taken two at a time, are relatively prime: that is, In mathematics, the integers a and b are said to be coprime or relatively prime if and only if they have no common factor other than 1 and −1, or equivalently, if their greatest common divisor is 1. ...

gcd(Fn, Fn+1) = gcd(Fn, Fn+2) = 1.

More generally, In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers without remainder. ...

gcd(Fn, Fm) = Fgcd(n, m).[15][16]

### Odd divisors

If n is odd all the odd divisors of Fn are ≡ 1 (mod 4).[17][18]
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

### Fibonacci and Legendre

There are some interesting formulas connecting the Fibonacci numbers and the Legendre symbol $;left(tfrac{p}{5}right).$ The Legendre symbol is a number theory concept. ...

$left(frac{p}{5}right) = left { begin{array}{cl} 0 & textrm{if};p =5 1 &textrm{if};p equiv pm1 pmod 5 -1 &textrm{if};p equiv pm2 pmod 5 end{array} right.$

If p is a prime number then[19][20] $F_{p} equiv left(frac{p}{5}right) pmod p ;;mbox{ and };;; F_{p-left(frac{p}{5}right)} equiv 0 pmod p.$

For example,

$(tfrac{2}{5}) = -1, ,, F_3 = 2, F_2=1,$
$(tfrac{3}{5}) = -1, ,, F_4 = 3,F_3=2,$
$(tfrac{5}{5}) = ;;,0,,, F_5 = 5,$
$(tfrac{7}{5}) = -1, ,,F_8 = 21,;;F_7=13,$
$(tfrac{11}{5}) = +1, F_{10} = 55, F_{11}=89.$

Also, if p ≠ 5 is an odd prime number[21] $;;;5F^2_{left(p pm 1 right) / 2} equiv left { begin{array}{cl} frac{5left(frac{p}{5}right)pm 5}{2} pmod p & textrm{if};p equiv 1 pmod 4 ; frac{5left(frac{p}{5}right)mp 3}{2} pmod p & textrm{if};p equiv 3 pmod 4 end{array} right.$

Examples of all the cases:

$p=7 equiv 3 pmod 4, ;;(tfrac{7}{5}) = -1, frac{5(frac{7}{5})+3}{2} =-1mbox{ and }frac{5(frac{7}{5})-3}{2}=-4.$
F3 = 2 and F4 = 3.
$5F_3^2=20equiv -1 pmod {7};;mbox{ and };;5F_4^2=45equiv -4 pmod {7}$
$p=11 equiv 3 pmod 4, ;;(tfrac{11}{5}) = +1, frac{5(frac{11}{5})+3}{2} =4mbox{ and }frac{5(frac{11}{5})- 3}{2}=1.$
F5 = 5 and F6 = 8.
$5F_5^2=125equiv 4 pmod {11} ;;mbox{ and };;5F_6^2=320equiv 1 pmod {11}$
$p=13 equiv 1 pmod 4, ;;(tfrac{13}{5}) = -1, frac{5(frac{13}{5})-5}{2} =-5mbox{ and }frac{5(frac{13}{5})+ 5}{2}=0.$
F6 = 8 and F7 = 13.
$5F_6^2=320equiv -5 pmod {13} ;;mbox{ and };;5F_7^2=845equiv 0 pmod {13}$
$p=29 equiv 1 pmod 4, ;;(tfrac{29}{5}) = +1, frac{5(frac{29}{5})-5}{2} =0mbox{ and }frac{5(frac{29}{5})+5}{2}=5.$
F14 = 377 and F15 = 610.
$5F_{14}^2=710645equiv 0 pmod {29} ;;mbox{ and };;5F_{15}^2=1860500equiv 5 pmod {29}$

### Divisibility by 11

$sum_{k=n}^{n+9} F_{k} = 11 F_{n+6}$

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

## Right triangles

Starting with 5, every second Fibonacci number is the length of the hypotenuse of a right triangle with integer sides, or in other words, the largest number in a Pythagorean triple. The length of the longer leg of this triangle is equal to the sum of the three sides of the preceding triangle in this series of triangles, and the shorter leg is equal to the difference between the preceding bypassed Fibonacci number and the shorter leg of the preceding triangle. The Pythagorean theorem: a2 + b2 = c2 A Pythagorean triple consists of three positive integers a, b, and c, such that a2 + b2 = c2. ...

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:

$displaystyle a_n = F_{2n-1}$
$displaystyle b_n = 2 F_n F_{n-1}$
$displaystyle c_n = {F_n}^2 - {F_{n-1}}^2$

These formulas satisfy $a_n ^2 = b_n ^2 + c_n ^2$ for all n, but they only represent triangle sides when n > 2.

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:

$a = F_n F_{n+3} , ; , b = 2 F_{n+1} F_{n+2} , ; , c = F_{n+1}^2 + F_{n+2}^2 , ; , a^2 + b^2 = c^2 ,.$

Example 1: let the Fibonacci numbers be 1, 2, 3 and 5. Then:

$displaystyle a = 1 times 5 = 5$
$displaystyle b = 2 times 2 times 3 = 12$
$displaystyle c = 2^2 + 3^2 = 13 ,$
$displaystyle 5^2 + 12^2 = 13^2 ,.$

Example 2: let the Fibonacci numbers be 8, 13, 21 and 34. Then:

$displaystyle a = 8 times 34 = 272$
$displaystyle b = 2 times 13 times 21 = 546$
$displaystyle c = 13^2 + 21^2 = 610 ,$
$displaystyle 272^2 + 546^2 = 610^2 ,.$

## Magnitude of Fibonacci numbers

Since Fn is asymptotic to $varphi^n/sqrt5$, the number of digits in the base b representation of $F_n,$ is asymptotic to $n,log_bvarphi$. In mathematics and applications, particularly the analysis of algorithms, asymptotic analysis is a method of classifying limiting behaviour, by concentrating on some trend. ...

In base 10, for every integer greater than 1 there are 4 or 5 Fibonacci numbers with that number of digits, in most cases 5.

## Applications

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. In number theory, the Euclidean algorithm (also called Euclids algorithm) is an algorithm to determine the greatest common divisor (GCD) of two elements of any Euclidean domain (for example, the integers). ... In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers without remainder. ...

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. Yuri Matiyasevich born March 2, 1947 in Leningrad, is a Russian mathematician. ... In mathematics, a Diophantine equation is an indeterminate polynomial equation that allows the variables to be integers only. ... Matiyasevichs theorem, proven in 1970 by Yuri Matiyasevich, implies that Hilberts tenth problem is unsolvable. ... Hilberts tenth problem is the tenth on the list of Hilberts problems of 1900. ...

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). The first five rows of Pascals triangle In mathematics, Pascals triangle is a geometric arrangement of the binomial coefficients in a triangle. ... LozaniÄ‡s triangle (sometimes called Losanitschs triangle) is a geometric arrangement of binomial coefficients in a manner very similar to that of Pascals triangle. ... In mathematics, particularly in combinatorics, a binomial coefficient is a coefficient of any of the terms in the expansion of the binomial (x+1)n. ...

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. Zeckendorfs theorem, named after Belgian mathematician Edouard Zeckendorf, is a theorem about the representation of integers as sums of Fibonacci numbers. ...

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. In finance, financial markets facilitate: The raising of capital (in the capital markets); The transfer of risk (in the derivatives markets); and International trade (in the currency markets). ...

Fibonacci numbers are used by some pseudorandom number generators. A pseudorandom number generator (PRNG) is an algorithm that generates a sequence of numbers, the elements of which are approximately independent of each other. ...

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. A merge sort algorithm used to sort an array of 7 integer values. ... Cover of books The Art of Computer Programming[1] is a comprehensive monograph written by Donald Knuth which covers many kinds of programming algorithms and their analysis. ...

Fibonacci numbers arise in the analysis of the Fibonacci heap data structure. In computer science, a Fibonacci heap is a data structure similar to a binomial heap but with a better amortized running time. ...

A one-dimensional optimization method, called the Fibonacci search technique, uses Fibonacci numbers.[22] The Fibonacci search technique is a method of searching a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers. ...

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. For other uses, see Music (disambiguation). ... Look up content in Wiktionary, the free dictionary. ... The term musical form is used in two related ways: a generic type of composition such as the symphony or concerto the structure of a particular piece, how its parts are put together to make the whole; this too can be generic, such as binary form or sonata form Musical... Bartok redirects here. ... Music for Strings, Percussion and Celesta is a piece of classical music by Béla Bartók. ...

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.[23][24][25] Conversion of units refers to conversion factors between different units of measurement for the same quantity. ... â€œMilesâ€ redirects here. ... Not to be confused with Golden mean (philosophy), the felicitous middle between two extremes, Golden numbers, an indicator of years in astronomy and calendar studies, or the Golden Rule. ... The radix (Latin for root), also called base, is the number of various unique symbols (or digits or numerals) a positional numeral system uses to represent numbers. ... The Fibonacci code is a universal code which encodes positive integers into binary code words. ... In computer architecture, a processor register is a small amount of very fast computer memory used to speed the execution of computer programs by providing quick access to frequently used valuesâ€”typically, these values are involved in multiple expression evaluations occurring within a small region on the program. ... Golden ratio base refers to the use of the golden ratio, the irrational number â‰ˆ1. ...

## Fibonacci numbers in nature

Sunflower head displaying florets in spirals of 34 and 55 around the outside

Fibonacci sequences appear in biological settings,[26] in two consecutive Fibonacci numbers, such as branching in trees, the fruitlets of a pineapple,[27] the flowering of artichoke, an uncurling fern and the arrangement of a pine cone.[28] 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[citation needed]. Image File history File links Helianthus_whorl. ... Image File history File links Helianthus_whorl. ... For other uses, see Sunflower (disambiguation). ... For other uses, see Pineapple (disambiguation). ... This article is about the globe artichoke. ... A cone (in formal botanical usage: strobilus, plural strobili) is an organ on plants in the division Pinophyta (conifers) that contains the reproductive structures. ... The golden ratio is a number, approximately 1. ...

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.[29] A Polish mathematician who has advanced the idea that fibonacci numbers in nature can be in part understood as the expression of certain algebraic constraints on free groups, specifically as certain Lindenmeyer grammars. ... The Cayley graph of the free group on two generators a and b In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many... See L-system for information on Lindenmayer systems. ...

A model for the pattern of florets in the head of a sunflower was proposed by H. Vogel in 1979.[30] This has the form Wildflowers A flower is the reproductive organ of those plants classified as angiosperms (flowering plants; Division Magnoliophyta). ... For other uses, see Sunflower (disambiguation). ...

$theta = frac{2pi}{phi^2} n$, $r = c sqrt{n}$

where n is the index number of the floret and c is a constant scaling factor; the florets thus lie on Fermat's spiral. The divergence angle, approximately 137.51°, is the golden angle, dividing the circle in the golden ratio. Because this ratio is irrational, no floret has a neighbor at exactly the same angle from the center, so the florets pack efficiently. Because the rational approximations to the golden ratio are of the form F(j):F(j+1), the nearest neighbors of floret number n are those at n±F(j) for some index j which depends on r, the distance from the center. It is often said that sunflowers and similar arrangements have 55 spirals in one direction and 89 in the other (or some other pair of adjacent Fibonacci numbers), but this is true only of one range of radii, typically the outermost and thus most conspicuous.[31] Fermats spiral (also known as a parabolic spiral) follows the equation in polar coordinates. ... The golden angle is the angle subtended by the smaller (red) arc when two arcs that make up a circle are in the golden ratio In geometry, the golden angle is the smaller of the two angles created by sectioning the circumference of a circle according to the golden section... Not to be confused with Golden mean (philosophy), the felicitous middle between two extremes, Golden numbers, an indicator of years in astronomy and calendar studies, or the Golden Rule. ...

## Popular culture

The Fibonacci numbers form a sequence of integers, mathematically defined by: So after the two initial numbers, each number is the sum of the two preceding numbers: This concept is easily understood by non-mathematicians and has appeared many times in popular culture. ...

## Generalizations

The Fibonacci sequence has been generalized in many ways. These include: In mathematics, the Fibonacci numbers form a sequence defined recursively by: F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2), for integer n > 1 That is, after two starting values, each number is the sum of the two preceding numbers. ...

• Generalizing the index to negative integers to produce the Negafibonacci numbers.
• Generalizing the index to real numbers using a modification of Binet's formula. [32]
• Starting with other integers. Lucas numbers have L1 = 1, L2 = 3, and Ln = Ln−1 + Ln−2. Primefree sequences use the Fibonacci recursion with other starting points in order to generate sequences in which all numbers are composite.
• Letting a number be a linear function (other than the sum) of the 2 preceding numbers. The Pell numbers have Pn = 2Pn – 1 + Pn – 2.
• Not adding the immediately preceding numbers. The Padovan sequence and Perrin numbers have P(n) = P(n – 2) + P(n – 3).
• Generating the next number by adding 3 numbers (tribonacci numbers), 4 numbers (tetranacci numbers), or more.
• Adding other objects than integers, for example functions or strings -- one essential example is Fibonacci polynomials.

In mathematics, negaFibonacci numbers are the negatively indexed elements of the Fibonacci sequence. ... The Lucas numbers 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. ... In mathematics, a primefree sequence is a sequence of integers that does not contain any prime numbers. ... A composite number is a positive integer which has a positive divisor other than one or itself. ... In mathematics, the Pell numbers and companion Pell numbers (Pell-Lucas numbers) are both sequences of integers. ... The Padovan sequence is the sequence of integers P(n) defined by the initial values and the recurrence relation The first few values of P(n) are 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 144, 151, 200. ... In mathematics, the Perrin numbers are defined by the recurrence relation P(0) = 3, P(1) = 0, P(2) = 2, and P(n) = P(n âˆ’ 2) + P(n âˆ’ 3) for n > 2. ... In mathematics, Fibonacci polynomials are a generalization of Fibonacci numbers. ...

## Numbers properties

### Periodicity mod n: Pisano periods

It is easily seen that if the members of the Fibonacci sequence are taken mod n, the resulting sequence must be periodic with period at most n2. The lengths of the periods for various n form the so-called Pisano periods (sequence A001175 in OEIS). Determining the Pisano periods in general is an open problem,[citation needed] although for any particular n it can be solved as an instance of cycle detection. In mathematics, a periodic function is a function that repeats its values, after adding some definite period to the variable. ... The nth Pisano period, written π(n), is the period with which the sequence of Fibonacci numbers, modulo n, repeats. ... The On-Line Encyclopedia of Integer Sequences (OEIS) is an extensive searchable database of integer sequences, freely available on the Web. ...

## The bee ancestry code

Fibonacci numbers also appear in the description of the reproduction of a population of idealized bees, according to the following rules:

• If an egg is laid by an unmated female, it hatches a male.
• If, however, an egg was fertilized by a male, it hatches a female.

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.[33]

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.

## Miscellaneous

In 1963, John H. E. Cohn proved that the only squares among the Fibonacci numbers are 0, 1, and 144.[34]

A logarithmic spiral, equiangular spiral or growth spiral is a special kind of spiral curve which often appears in nature. ... Wikibooks logo Wikibooks, previously called Wikimedia Free Textbook Project and Wikimedia-Textbooks, is a wiki for the creation of books. ... The Fibonacci Association is a group that promotes reasearch into mathematics related to the Fibonacci numbers. ... The Fibonacci Quarterly (sometimes in bibliographies) is the official publication of the Fibonacci Association, intended to serve as a focal point for interest in Fibonacci numbers and related questions, especially with respect to new results, research proposals, challenging problems, and innovative proofs of old ideas. ... In mathematics, negaFibonacci numbers are the negatively indexed elements of the Fibonacci sequence. ... The Lucas numbers 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. ...

## References

1. ^ Parmanand Singh. "Acharya Hemachandra and the (so called) Fibonacci Numbers". Math. Ed. Siwan, 20(1):28-30, 1986. ISSN 0047-6269]
2. ^ Parmanand Singh,"The So-called Fibonacci numbers in ancient and medieval India." Historia Mathematica 12(3), 229–44, 1985.
3. ^ By modern convention, the sequence begins with F0=0. The Liber Abaci began the sequence with F1 = 1, omitting the initial 0, and the sequence is still written this way by some.
4. ^ The website [1] has the first 300 Fn factored into primes and links to more extensive tables.
5. ^ Sigler, Laurence E. (trans.) (2002). Fibonacci's Liber Abaci. Springer-Verlag. ISBN 0-387-95419-8.  Chapter II.12, pp. 404–405.
6. ^ Knott, Ron. Fibonacci's Rabbits. University of Surrey School of Electronics and Physical Sciences.
7. ^ Kepler, Johannes (1966). A New Year Gift: On Hexagonal Snow. Oxford University Press, 92. ISBN 0198581203.  Strena seu de Nive Sexangula (1611)
8. ^ a b E. W. Dijkstra (1978). In honour of Fibonacci. Report EWD654
9. ^ Posamentier, Alfred; Lehmann, Ingmar (2007). The (Fabulous) FIBONACCI Numbers. Prometheus Books, 305. ISBN 978-1-59102-475-0.
10. ^ M. Möbius, Wie erkennt man eine Fibonacci Zahl?, Math. Semesterber. (1998) 45; 243–246
11. ^ Fibonacci Number - from Wolfram MathWorld
12. ^ Fibonacci Number - from Wolfram MathWorld
13. ^ Ron Knott, "The Fibonacci numbers".
14. ^ Ross Honsberger Mathematical Gems III (AMS Dolciani Mathematcal Expositions No. 9), 1985, ISBN 0-88385-318-3, p. 133.
15. ^ Paulo Ribenboim, My Numbers, My Friends, Springer-Verlag 2000
16. ^ Su, Francis E., et al. "Fibonacci GCD's, please.", Mudd Math Fun Facts.
17. ^ Lemmermeyer, ex. 2.27 p. 73
18. ^ The website [2] has the first 300 Fibonacci numbers factored into primes.
19. ^ Paulo Ribenboim (1996), The New Book of Prime Number Records, New York: Springer, ISBN 0-387-94457-5, p. 64
20. ^ Franz Lemmermeyer (2000), Reciprocity Laws, New York: Springer, ISBN 3-540-66957-4, ex 2.25-2.28, pp. 73-74
21. ^ Lemmermeyer, ex. 2.38, pp. 73-74
22. ^ M. Avriel and D.J. Wilde (1966). "Optimality of the Symmetric Fibonacci Search Technique". Fibonacci Quarterly (3): 265–269.
23. ^ An Application of the Fibonacci Number Representation
24. ^ A Practical Use of the Sequence
25. ^ Zeckendorf representation
26. ^ S. Douady and Y. Couder (1996). "Phyllotaxis as a Dynamical Self Organizing Process". Journal of Theoretical Biology 178 (178): 255–274. doi:10.1006/jtbi.1996.0026.
27. ^ Jones, Judy; William Wilson (2006). "Science", An Incomplete Education. Ballantine Books, 544. ISBN 978-0-7394-7582-9.
28. ^ A. Brousseau (1969). "Fibonacci Statistics in Conifers". Fibonacci Quarterly (7): 525–532.
29. ^ Prusinkiewicz, Przemyslaw; James Hanan (1989). Lindenmayer Systems, Fractals, and Plants (Lecture Notes in Biomathematics). Springer-Verlag. ISBN 0-387-97092-4.
30. ^ Vogel, H (1979), “A better way to construct the sunflower head”, Mathematical Biosciences 44 (44): 179–189, DOI 10.1016/0025-5564(79)90080-4
31. ^ Prusinkiewicz, Przemyslaw; Lindenmayer, Aristid (1990). The Algorithmic Beauty of Plants. Springer-Verlag, 101-107. ISBN 978-0387972978.
32. ^ Pravin Chandra and Eric W. Weisstein, Fibonacci Number at MathWorld.
33. ^ The Fibonacci Numbers and the Ancestry of Bees
34. ^ J H E Cohn. "Square Fibonacci Numbers Etc", pp. 109-113.

The University of Surrey is a public university in Guildford, England. ... Paulo Ribenboim is a Canadian mathematician who speciliazes in number theory. ... Paulo Ribenboim is a Canadian mathematician who speciliazes in number theory. ... The Fibonacci Quarterly (sometimes in bibliographies) is the official publication of the Fibonacci Association, intended to serve as a focal point for interest in Fibonacci numbers and related questions, especially with respect to new results, research proposals, challenging problems, and innovative proofs of old ideas. ... A digital object identifier (or DOI) is a standard for persistently identifying a piece of intellectual property on a digital network and associating it with related data, the metadata, in a structured extensible way. ... The Fibonacci Quarterly (sometimes in bibliographies) is the official publication of the Fibonacci Association, intended to serve as a focal point for interest in Fibonacci numbers and related questions, especially with respect to new results, research proposals, challenging problems, and innovative proofs of old ideas. ... Springer Science+Business Media or Springer (IPA: ) is a worldwide publishing company based in Germany which focuses on academic journals and books in the fields of science, technology, mathematics, and medicine. ... A Polish mathematician who has advanced the idea that fibonacci numbers in nature can be in part understood as the expression of certain algebraic constraints on free groups, specifically as certain Lindenmeyer grammars. ... Aristid Lindenmayer (November 17, 1925 _ 1989) was a Hungarian biologist. ... Eric W. Weisstein (born March 18, 1969, in Bloomington, Indiana) is an encyclopedist who created and maintains MathWorld and Eric Weissteins World of Science (ScienceWorld). ... MathWorld is an online mathematics reference work, sponsored by Wolfram Research Inc. ...

Results from FactBites:

 Fibonacci Number -- from Wolfram MathWorld (1871 words) The Fibonacci numbers are the sequence of numbers NUMB3RS, math genius Charlie Eppes mentions that the Fibonacci numbers are found in the structure of crystals and the spiral of galaxies and a nautilus shell. triangular Fibonacci numbers are 1, 3, 21, and 55.
 Fibonacci number - Wikipedia, the free encyclopedia (3690 words) 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. 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. Fibonacci sequences have been noted to appear in biological settings, such as the branching patterns of leaves in grasses and flowers, branching in bushes and trees, the arrangement of pines on a pine cone, seeds on a raspberry, and spiral patterns in horns and shells.
More results at FactBites »

Share your thoughts, questions and commentary here