Fibonacci sequence

Fibonacci numbers are also strongly related to the golden ratio: Binet's formula expresses the n-th Fibonacci number in terms of n and the golden ratio, and implies that the ratio of two consecutive Fibonacci numbers tends to the golden ratio as n increases. Fibonacci numbers are also closely related to Lucas numbers, which obey the same recurrence relation and with the Fibonacci numbers form a complementary pair of Lucas sequences.

Definition

The Fibonacci numbers may be defined by the recurrence relation^[6]

$${\displaystyle F_{0}=0,\quad F_{1}=1,}$$

$${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$$

Under some older definitions, the value ${\displaystyle F_{0}=0}$ is omitted, so that the sequence starts with ${\displaystyle F_{1}=F_{2}=1,}$ and the recurrence ${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$ is valid for n > 2.^[7][8]

The first 20 Fibonacci numbers F_n are:^[1]

F0	F1	F2	F3	F4	F5	F6	F7	F8	F9	F10	F11	F12	F13	F14	F15	F16	F17	F18	F19
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181

History

India

The Fibonacci sequence appears in Indian mathematics, in connection with Sanskrit prosody.^[3][9][10] In the Sanskrit poetic tradition, there was interest in enumerating all patterns of long (L) syllables of 2 units duration, juxtaposed with short (S) syllables of 1 unit duration. Counting the different patterns of successive L and S with a given total duration results in the Fibonacci numbers: the number of patterns of duration m units is F_m+1.^[4]

Knowledge of the Fibonacci sequence was expressed as early as

Variations of two earlier meters [is the variation] ... For example, for [a meter of length] four, variations of meters of two [and] three being mixed, five happens. [works out examples 8, 13, 21] ... In this way, the process should be followed in all mātrā-vṛttas [prosodic combinations].^[a]

Hemachandra (c. 1150) is credited with knowledge of the sequence as well,^[2] writing that "the sum of the last and the one before the last is the number ... of the next mātrā-vṛtta."^[14][15]

Europe

The Fibonacci sequence first appears in the book Liber Abaci (The Book of Calculation, 1202) by Fibonacci^[16][17] where it is used to calculate the growth of rabbit populations.^[18][19] Fibonacci considers the growth of an idealized (biologically unrealistic) rabbit population, assuming that: a newly born breeding pair of rabbits are put in a field; each breeding pair mates at the age of one month, and at the end of their second month they always produce another pair of rabbits; and rabbits never die, but continue breeding forever. Fibonacci posed the puzzle: how many pairs will there be in one year?

• At the end of the first month, they mate, but there is still only 1 pair.
• At the end of the second month they produce a new pair, so there are 2 pairs in the field.
• At the end of the third month, the original pair produce a second pair, but the second pair only mate to gestate for a month, so there are 3 pairs in all.
• At the end of the fourth month, the original pair has produced yet another new pair, and the pair born two months ago also produces their first pair, making 5 pairs.

At the end of the n-th month, the number of pairs of rabbits is equal to the number of mature pairs (that is, the number of pairs in month n – 2) plus the number of pairs alive last month (month n – 1). The number in the n-th month is the n-th Fibonacci number.^[20]

The name "Fibonacci sequence" was first used by the 19th-century number theorist Édouard Lucas.^[21]

Relation to the golden ratio

Closed-form expression

Like every sequence defined by a linear recurrence with constant coefficients, the Fibonacci numbers have a closed-form expression. It has become known as Binet's formula, named after French mathematician Jacques Philippe Marie Binet, though it was already known by Abraham de Moivre and Daniel Bernoulli:^[22]

$${\displaystyle F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}={\frac {\varphi ^{n}-\psi ^{n}}{\sqrt {5}}},}$$

where

$${\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1.61803\,39887\ldots }$$

is the golden ratio, and ψ is its conjugate:^[23]

$${\displaystyle \psi ={\frac {1-{\sqrt {5}}}{2}}=1-\varphi =-{1 \over \varphi }\approx -0.61803\,39887\ldots .}$$

Since ${\displaystyle \psi =-\varphi ^{-1}}$, this formula can also be written as

$${\displaystyle F_{n}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{\sqrt {5}}}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{2\varphi -1}}.}$$

To see the relation between the sequence and these constants,^[24] note that φ and ψ are both solutions of the equation ${\textstyle x^{2}=x+1}$ and thus ${\displaystyle x^{n}=x^{n-1}+x^{n-2},}$ so the powers of φ and ψ satisfy the Fibonacci recursion. In other words,

$${\displaystyle {\begin{aligned}\varphi ^{n}&=\varphi ^{n-1}+\varphi ^{n-2},\\[3mu]\psi ^{n}&=\psi ^{n-1}+\psi ^{n-2}.\end{aligned}}}$$

It follows that for any values a and b, the sequence defined by

$${\displaystyle U_{n}=a\varphi ^{n}+b\psi ^{n}}$$

satisfies the same recurrence,

$${\displaystyle {\begin{aligned}U_{n}&=a\varphi ^{n}+b\psi ^{n}\\[3mu]&=a(\varphi ^{n-1}+\varphi ^{n-2})+b(\psi ^{n-1}+\psi ^{n-2})\\[3mu]&=a\varphi ^{n-1}+b\psi ^{n-1}+a\varphi ^{n-2}+b\psi ^{n-2}\\[3mu]&=U_{n-1}+U_{n-2}.\end{aligned}}}$$

If a and b are chosen so that U₀ = 0 and U₁ = 1 then the resulting sequence U_n must be the Fibonacci sequence. This is the same as requiring a and b satisfy the system of equations:

$${\displaystyle \left\{{\begin{aligned}a+b&=0\\\varphi a+\psi b&=1\end{aligned}}\right.}$$

which has solution

$${\displaystyle a={\frac {1}{\varphi -\psi }}={\frac {1}{\sqrt {5}}},\quad b=-a,}$$

producing the required formula.

Taking the starting values U₀ and U₁ to be arbitrary constants, a more general solution is:

$${\displaystyle U_{n}=a\varphi ^{n}+b\psi ^{n}}$$

where

$${\displaystyle {\begin{aligned}a&={\frac {U_{1}-U_{0}\psi }{\sqrt {5}}},\\[3mu]b&={\frac {U_{0}\varphi -U_{1}}{\sqrt {5}}}.\end{aligned}}}$$

Computation by rounding

Since ${\textstyle \left|{\frac {\psi ^{n}}{\sqrt {5}}}\right|<{\frac {1}{2}}}$ for all n ≥ 0, the number F_n is the closest integer to ${\displaystyle {\frac {\varphi ^{n}}{\sqrt {5}}}}$. Therefore, it can be found by rounding, using the nearest integer function:

$${\displaystyle F_{n}=\left\lfloor {\frac {\varphi ^{n}}{\sqrt {5}}}\right\rceil ,\ n\geq 0.}$$

In fact, the rounding error is very small, being less than 0.1 for n ≥ 4, and less than 0.01 for n ≥ 8. This formula is easily inverted to find an index of a Fibonacci number F:

$${\displaystyle n(F)=\left\lfloor \log _{\varphi }{\sqrt {5}}F\right\rceil ,\ F\geq 1.}$$

Instead using the

$${\displaystyle n_{\mathrm {largest} }(F)=\left\lfloor \log _{\varphi }{\sqrt {5}}(F+1/2)\right\rfloor ,\ F\geq 0,}$$

${\displaystyle \log _{\varphi }(x)=\ln(x)/\ln(\varphi )=\log _{10}(x)/\log _{10}(\varphi )}$

${\displaystyle \ln(\varphi )=0.481211\ldots }$

${\displaystyle \log _{10}(\varphi )=0.208987\ldots }$

Magnitude

Since F_n is asymptotic to ${\displaystyle \varphi ^{n}/{\sqrt {5}}}$, the number of digits in F_n is asymptotic to ${\displaystyle n\log _{10}\varphi \approx 0.2090\,n}$. As a consequence, for every integer d > 1 there are either 4 or 5 Fibonacci numbers with d decimal digits.

More generally, in the base b representation, the number of digits in F_n is asymptotic to ${\displaystyle n\log _{b}\varphi ={\frac {n\log \varphi }{\log b}}.}$

Limit of consecutive quotients

${\displaystyle \varphi \colon }$

$${\displaystyle \lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}=\varphi .}$$

This convergence holds regardless of the starting values ${\displaystyle U_{0}}$ and ${\displaystyle U_{1}}$, unless ${\displaystyle U_{1}=-U_{0}/\varphi }$. This can be verified using Binet's formula. For example, the initial values 3 and 2 generate the sequence 3, 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, 343, 555, ... . The ratio of consecutive terms in this sequence shows the same convergence towards the golden ratio.

In general, ${\displaystyle \lim _{n\to \infty }{\frac {F_{n+m}}{F_{n}}}=\varphi ^{m}}$, because the ratios between consecutive Fibonacci numbers approaches ${\displaystyle \varphi }$.

Decomposition of powers

Since the golden ratio satisfies the equation

$${\displaystyle \varphi ^{2}=\varphi +1,}$$

this expression can be used to decompose higher powers ${\displaystyle \varphi ^{n}}$ as a linear function of lower powers, which in turn can be decomposed all the way down to a linear combination of ${\displaystyle \varphi }$ and 1. The resulting recurrence relationships yield Fibonacci numbers as the linear coefficients:

$${\displaystyle \varphi ^{n}=F_{n}\varphi +F_{n-1}.}$$

$${\displaystyle \varphi ^{n+1}=(F_{n}\varphi +F_{n-1})\varphi =F_{n}\varphi ^{2}+F_{n-1}\varphi =F_{n}(\varphi +1)+F_{n-1}\varphi =(F_{n}+F_{n-1})\varphi +F_{n}=F_{n+1}\varphi +F_{n}.}$$

${\displaystyle \psi =-1/\varphi }$

${\displaystyle \psi ^{2}=\psi +1}$

$${\displaystyle \psi ^{n}=F_{n}\psi +F_{n-1}.}$$

These expressions are also true for n < 1 if the Fibonacci sequence F_n is extended to negative integers using the Fibonacci rule ${\displaystyle F_{n}=F_{n+2}-F_{n+1}.}$

Identification

Binet's formula provides a proof that a positive integer x is a Fibonacci number if and only if at least one of ${\displaystyle 5x^{2}+4}$ or ${\displaystyle 5x^{2}-4}$ is a perfect square.^[29] This is because Binet's formula, which can be written as ${\displaystyle F_{n}=(\varphi ^{n}-(-1)^{n}\varphi ^{-n})/{\sqrt {5}}}$, can be multiplied by ${\displaystyle {\sqrt {5}}\varphi ^{n}}$ and solved as a quadratic equation in ${\displaystyle \varphi ^{n}}$ via the quadratic formula:

$${\displaystyle \varphi ^{n}={\frac {F_{n}{\sqrt {5}}\pm {\sqrt {5{F_{n}}^{2}+4(-1)^{n}}}}{2}}.}$$

Comparing this to ${\displaystyle \varphi ^{n}=F_{n}\varphi +F_{n-1}=(F_{n}{\sqrt {5}}+F_{n}+2F_{n-1})/2}$, it follows that

$${\displaystyle 5{F_{n}}^{2}+4(-1)^{n}=(F_{n}+2F_{n-1})^{2}\,.}$$

In particular, the left-hand side is a perfect square.

Matrix form

A 2-dimensional system of linear

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

$${\displaystyle {\vec {F}}_{k+1}=\mathbf {A} {\vec {F}}_{k},}$$

which yields ${\displaystyle {\vec {F}}_{n}=\mathbf {A} ^{n}{\vec {F}}_{0}}$. The

A are ${\displaystyle \varphi ={\tfrac {1}{2}}{\bigl (}1+{\sqrt {5}}~\!{\bigr )}}$ and ${\displaystyle \psi =-\varphi ^{-1}={\tfrac {1}{2}}{\bigl (}1-{\sqrt {5}}~\!{\bigr )}}$ corresponding to the respective

eigenvectors

$${\displaystyle {\vec {\mu }}={\varphi \choose 1},\quad {\vec {\nu }}={-\varphi ^{-1} \choose 1}.}$$

As the initial value is

$${\displaystyle {\vec {F}}_{0}={1 \choose 0}={\frac {1}{\sqrt {5}}}{\vec {\mu }}-{\frac {1}{\sqrt {5}}}{\vec {\nu }},}$$

it follows that the nth term is

$${\displaystyle {\begin{aligned}{\vec {F}}_{n}&={\frac {1}{\sqrt {5}}}A^{n}{\vec {\mu }}-{\frac {1}{\sqrt {5}}}A^{n}{\vec {\nu }}\\&={\frac {1}{\sqrt {5}}}\varphi ^{n}{\vec {\mu }}-{\frac {1}{\sqrt {5}}}(-\varphi )^{-n}{\vec {\nu }}\\&={\cfrac {1}{\sqrt {5}}}\left({\cfrac {1+{\sqrt {5}}}{2}}\right)^{\!n}{\varphi \choose 1}\,-\,{\cfrac {1}{\sqrt {5}}}\left({\cfrac {1-{\sqrt {5}}}{2}}\right)^{\!n}{-\varphi ^{-1} \choose 1}.\end{aligned}}}$$

From this, the nth element in the Fibonacci series may be read off directly as a closed-form expression:

$${\displaystyle F_{n}={\cfrac {1}{\sqrt {5}}}\left({\cfrac {1+{\sqrt {5}}}{2}}\right)^{\!n}-\,{\cfrac {1}{\sqrt {5}}}\left({\cfrac {1-{\sqrt {5}}}{2}}\right)^{\!n}.}$$

Equivalently, the same computation may be performed by

$${\displaystyle {\begin{aligned}A&=S\Lambda S^{-1},\\[3mu]A^{n}&=S\Lambda ^{n}S^{-1},\end{aligned}}}$$

where

$${\displaystyle \Lambda ={\begin{pmatrix}\varphi &0\\0&-\varphi ^{-1}\!\end{pmatrix}},\quad S={\begin{pmatrix}\varphi &-\varphi ^{-1}\\1&1\end{pmatrix}}.}$$

The closed-form expression for the nth element in the Fibonacci series is therefore given by

$${\displaystyle {\begin{aligned}{F_{n+1} \choose F_{n}}&=A^{n}{F_{1} \choose F_{0}}\\&=S\Lambda ^{n}S^{-1}{F_{1} \choose F_{0}}\\&=S{\begin{pmatrix}\varphi ^{n}&0\\0&(-\varphi )^{-n}\end{pmatrix}}S^{-1}{F_{1} \choose F_{0}}\\&={\begin{pmatrix}\varphi &-\varphi ^{-1}\\1&1\end{pmatrix}}{\begin{pmatrix}\varphi ^{n}&0\\0&(-\varphi )^{-n}\end{pmatrix}}{\frac {1}{\sqrt {5}}}{\begin{pmatrix}1&\varphi ^{-1}\\-1&\varphi \end{pmatrix}}{1 \choose 0},\end{aligned}}}$$

which again yields

$${\displaystyle F_{n}={\cfrac {\varphi ^{n}-(-\varphi )^{-n}}{\sqrt {5}}}.}$$

The matrix A 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 φ:

$${\displaystyle \varphi =1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+\ddots }}}}}}.}$$

The

The matrix formed from successive convergents of any continued fraction has a determinant of +1 or −1. The matrix representation gives the following closed-form expression for the Fibonacci numbers:

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

For a given n, this matrix can be computed in O(log n) arithmetic operations, using the exponentiation by squaring method.

Taking the determinant of both sides of this equation yields

$${\displaystyle (-1)^{n}=F_{n+1}F_{n-1}-{F_{n}}^{2}.}$$

Moreover, since AⁿA^m = A^n+m for any

$${\displaystyle {\begin{aligned}{F_{m}}{F_{n}}+{F_{m-1}}{F_{n-1}}&=F_{m+n-1},\\[3mu]F_{m}F_{n+1}+F_{m-1}F_{n}&=F_{m+n}.\end{aligned}}}$$

In particular, with m = n,

$${\displaystyle {\begin{aligned}F_{2n-1}&={F_{n}}^{2}+{F_{n-1}}^{2}\\[6mu]F_{2n{\phantom {{}-1}}}&=(F_{n-1}+F_{n+1})F_{n}\\[3mu]&=(2F_{n-1}+F_{n})F_{n}\\[3mu]&=(2F_{n+1}-F_{n})F_{n}.\end{aligned}}}$$

These last two identities provide a way to compute Fibonacci numbers recursively in O(log n) arithmetic operations. This matches the time for computing the n-th Fibonacci number from the closed-form matrix formula, but with fewer redundant steps if one avoids recomputing an already computed Fibonacci number (recursion with memoization).^[31]

Combinatorial identities

Combinatorial proofs

Most identities involving Fibonacci numbers can be proved using combinatorial arguments using the fact that ${\displaystyle F_{n}}$ can be interpreted as the number of (possibly empty) sequences of 1s and 2s whose sum is ${\displaystyle n-1}$. This can be taken as the definition of ${\displaystyle F_{n}}$ with the conventions ${\displaystyle F_{0}=0}$, meaning no such sequence exists whose sum is −1, and ${\displaystyle F_{1}=1}$, meaning the empty sequence "adds up" to 0. In the following, ${\displaystyle |{...}|}$ is the cardinality of a set:

${\displaystyle F_{0}=0=|\{\}|}$

${\displaystyle F_{1}=1=|\{()\}|}$

${\displaystyle F_{2}=1=|\{(1)\}|}$

${\displaystyle F_{3}=2=|\{(1,1),(2)\}|}$

${\displaystyle F_{4}=3=|\{(1,1,1),(1,2),(2,1)\}|}$

${\displaystyle F_{5}=5=|\{(1,1,1,1),(1,1,2),(1,2,1),(2,1,1),(2,2)\}|}$

In this manner the recurrence relation

$${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$$

${\displaystyle F_{n}}$

$${\displaystyle F_{n}=|\{(1,...),(1,...),...\}|+|\{(2,...),(2,...),...\}|}$$

${\displaystyle n-2}$

${\displaystyle n-3}$

${\displaystyle F_{n-1}}$

${\displaystyle F_{n-2}}$

${\displaystyle F_{n-1}+F_{n-2}}$

${\displaystyle F_{n}}$

In a similar manner it may be shown that the sum of the first Fibonacci numbers up to the n-th is equal to the (n + 2)-th Fibonacci number minus 1.^[32] In symbols:

$${\displaystyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1}$$

This may be seen by dividing all sequences summing to ${\displaystyle n+1}$ based on the location of the first 2. Specifically, each set consists of those sequences that start ${\displaystyle (2,...),(1,2,...),...,}$ until the last two sets ${\displaystyle \{(1,1,...,1,2)\},\{(1,1,...,1)\}}$ each with cardinality 1.

Following the same logic as before, by summing the cardinality of each set we see that

${\displaystyle F_{n+2}=F_{n}+F_{n-1}+...+|\{(1,1,...,1,2)\}|+|\{(1,1,...,1)\}|}$

... where the last two terms have the value ${\displaystyle F_{1}=1}$. From this it follows that ${\displaystyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1}$.

A similar argument, grouping the sums by the position of the first 1 rather than the first 2 gives two more identities:

$${\displaystyle \sum _{i=0}^{n-1}F_{2i+1}=F_{2n}}$$

$${\displaystyle \sum _{i=1}^{n}F_{2i}=F_{2n+1}-1.}$$

${\displaystyle F_{2n-1}}$

${\displaystyle F_{2n}}$

A different trick may be used to prove

$${\displaystyle \sum _{i=1}^{n}F_{i}^{2}=F_{n}F_{n+1}}$$

${\displaystyle F_{n}}$

${\displaystyle F_{n}\times F_{n+1}}$

${\displaystyle F_{n},F_{n-1},...,F_{1}}$

Symbolic method

The sequence ${\displaystyle (F_{n})_{n\in \mathbb {N} }}$ is also considered using the

${\displaystyle \operatorname {Seq} ({\mathcal {Z+Z^{2}}})}$

${\displaystyle n}$

${\displaystyle n-1}$

It follows that the

${\displaystyle \sum _{i=0}^{\infty }F_{i}z^{i}}$

${\displaystyle {\frac {z}{1-z-z^{2}}}.}$

Induction proofs

Fibonacci identities often can be easily proved using mathematical induction.

For example, reconsider

$${\displaystyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1.}$$

${\displaystyle F_{n+1}}$

${\displaystyle \sum _{i=1}^{n}F_{i}+F_{n+1}=F_{n+1}+F_{n+2}-1}$

and so we have the formula for ${\displaystyle n+1}$

$${\displaystyle \sum _{i=1}^{n+1}F_{i}=F_{n+3}-1}$$

Similarly, add ${\displaystyle {F_{n+1}}^{2}}$ to both sides of

$${\displaystyle \sum _{i=1}^{n}F_{i}^{2}=F_{n}F_{n+1}}$$

$${\displaystyle \sum _{i=1}^{n}F_{i}^{2}+{F_{n+1}}^{2}=F_{n+1}\left(F_{n}+F_{n+1}\right)}$$

$${\displaystyle \sum _{i=1}^{n+1}F_{i}^{2}=F_{n+1}F_{n+2}}$$

Binet formula proofs

The Binet formula is

$${\displaystyle {\sqrt {5}}F_{n}=\varphi ^{n}-\psi ^{n}.}$$

For example, to prove that ${\textstyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1}$ note that the left hand side multiplied by ${\displaystyle {\sqrt {5}}}$ becomes

$${\displaystyle {\begin{aligned}1+&\varphi +\varphi ^{2}+\dots +\varphi ^{n}-\left(1+\psi +\psi ^{2}+\dots +\psi ^{n}\right)\\&={\frac {\varphi ^{n+1}-1}{\varphi -1}}-{\frac {\psi ^{n+1}-1}{\psi -1}}\\&={\frac {\varphi ^{n+1}-1}{-\psi }}-{\frac {\psi ^{n+1}-1}{-\varphi }}\\&={\frac {-\varphi ^{n+2}+\varphi +\psi ^{n+2}-\psi }{\varphi \psi }}\\&=\varphi ^{n+2}-\psi ^{n+2}-(\varphi -\psi )\\&={\sqrt {5}}(F_{n+2}-1)\\\end{aligned}}}$$

${\textstyle \varphi \psi =-1}$

${\textstyle \varphi -\psi ={\sqrt {5}}}$

Other identities

Numerous other identities can be derived using various methods. Here are some of them:^[35]

Cassini's and Catalan's identities

Cassini's identity states that

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

$${\displaystyle {F_{n}}^{2}-F_{n+r}F_{n-r}=(-1)^{n-r}{F_{r}}^{2}}$$

d'Ocagne's identity

$${\displaystyle F_{m}F_{n+1}-F_{m+1}F_{n}=(-1)^{n}F_{m-n}}$$

$${\displaystyle F_{2n}={F_{n+1}}^{2}-{F_{n-1}}^{2}=F_{n}\left(F_{n+1}+F_{n-1}\right)=F_{n}L_{n}}$$

$${\displaystyle F_{3n}=2{F_{n}}^{3}+3F_{n}F_{n+1}F_{n-1}=5{F_{n}}^{3}+3(-1)^{n}F_{n}}$$

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

$${\displaystyle F_{3n+2}={F_{n+1}}^{3}+3{F_{n+1}}^{2}F_{n}+{F_{n}}^{3}}$$

$${\displaystyle F_{4n}=4F_{n}F_{n+1}\left({F_{n+1}}^{2}+2{F_{n}}^{2}\right)-3{F_{n}}^{2}\left({F_{n}}^{2}+2{F_{n+1}}^{2}\right)}$$

More generally,^[35]

$${\displaystyle F_{kn+c}=\sum _{i=0}^{k}{k \choose i}F_{c-i}{F_{n}}^{i}{F_{n+1}}^{k-i}.}$$

or alternatively

$${\displaystyle F_{kn+c}=\sum _{i=0}^{k}{k \choose i}F_{c+i}{F_{n}}^{i}{F_{n-1}}^{k-i}.}$$

Putting k = 2 in this formula, one gets again the formulas of the end of above section Matrix form.

Generating function

The generating function of the Fibonacci sequence is the power series

$${\displaystyle s(z)=\sum _{k=0}^{\infty }F_{k}z^{k}=0+z+z^{2}+2z^{3}+3z^{4}+\dots .}$$

This series is convergent for any complex number ${\displaystyle z}$ satisfying ${\displaystyle |z|<1/\varphi ,}$ and its sum has a simple closed form:^[36]

$${\displaystyle s(z)={\frac {z}{1-z-z^{2}}}.}$$

This can be proved by multiplying by ${\textstyle (1-z-z^{2})}$:

$${\displaystyle {\begin{aligned}(1-z-z^{2})s(z)&=\sum _{k=0}^{\infty }F_{k}z^{k}-\sum _{k=0}^{\infty }F_{k}z^{k+1}-\sum _{k=0}^{\infty }F_{k}z^{k+2}\\&=\sum _{k=0}^{\infty }F_{k}z^{k}-\sum _{k=1}^{\infty }F_{k-1}z^{k}-\sum _{k=2}^{\infty }F_{k-2}z^{k}\\&=0z^{0}+1z^{1}-0z^{1}+\sum _{k=2}^{\infty }(F_{k}-F_{k-1}-F_{k-2})z^{k}\\&=z,\end{aligned}}}$$

where all terms involving ${\displaystyle z^{k}}$ for ${\displaystyle k\geq 2}$ cancel out because of the defining Fibonacci recurrence relation.

The partial fraction decomposition is given by

$${\displaystyle s(z)={\frac {1}{\sqrt {5}}}\left({\frac {1}{1-\varphi z}}-{\frac {1}{1-\psi z}}\right)}$$

${\textstyle \varphi ={\tfrac {1}{2}}\left(1+{\sqrt {5}}\right)}$

${\displaystyle \psi ={\tfrac {1}{2}}\left(1-{\sqrt {5}}\right)}$

The related function ${\textstyle z\mapsto -s\left(-1/z\right)}$ is the generating function for the

${\displaystyle s(z)}$

$${\displaystyle s(z)=s\!\left(-{\frac {1}{z}}\right).}$$

Using ${\displaystyle z}$ equal to any of 0.01, 0.001, 0.0001, etc. lays out the first Fibonacci numbers in the decimal expansion of ${\displaystyle s(z)}$. For example, ${\displaystyle s(0.001)={\frac {0.001}{0.998999}}={\frac {1000}{998999}}=0.001001002003005008013021\ldots .}$

Reciprocal sums

Infinite sums over reciprocal Fibonacci numbers can sometimes be evaluated in terms of theta functions. For example, the sum of every odd-indexed reciprocal Fibonacci number can be written as

$${\displaystyle \sum _{k=1}^{\infty }{\frac {1}{F_{2k-1}}}={\frac {\sqrt {5}}{4}}\;\vartheta _{2}\!\left(0,{\frac {3-{\sqrt {5}}}{2}}\right)^{2},}$$

and the sum of squared reciprocal Fibonacci numbers as

$${\displaystyle \sum _{k=1}^{\infty }{\frac {1}{{F_{k}}^{2}}}={\frac {5}{24}}\!\left(\vartheta _{2}\!\left(0,{\frac {3-{\sqrt {5}}}{2}}\right)^{4}-\vartheta _{4}\!\left(0,{\frac {3-{\sqrt {5}}}{2}}\right)^{4}+1\right).}$$

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

$${\displaystyle \sum _{k=1}^{\infty }{\frac {1}{1+F_{2k-1}}}={\frac {\sqrt {5}}{2}},}$$

and there is a nested sum of squared Fibonacci numbers giving the reciprocal of the golden ratio,

$${\displaystyle \sum _{k=1}^{\infty }{\frac {(-1)^{k+1}}{\sum _{j=1}^{k}{F_{j}}^{2}}}={\frac {{\sqrt {5}}-1}{2}}.}$$

The sum of all even-indexed reciprocal Fibonacci numbers is^[37]

$${\displaystyle \sum _{k=1}^{\infty }{\frac {1}{F_{2k}}}={\sqrt {5}}\left(L(\psi ^{2})-L(\psi ^{4})\right)}$$

${\displaystyle \textstyle L(q):=\sum _{k=1}^{\infty }{\frac {q^{k}}{1-q^{k}}},}$

${\displaystyle \textstyle {\frac {1}{F_{2k}}}={\sqrt {5}}\left({\frac {\psi ^{2k}}{1-\psi ^{2k}}}-{\frac {\psi ^{4k}}{1-\psi ^{4k}}}\right)\!.}$

So the reciprocal Fibonacci constant is^[38]

$${\displaystyle \sum _{k=1}^{\infty }{\frac {1}{F_{k}}}=\sum _{k=1}^{\infty }{\frac {1}{F_{2k-1}}}+\sum _{k=1}^{\infty }{\frac {1}{F_{2k}}}=3.359885666243\dots }$$

Moreover, this number has been proved irrational by Richard André-Jeannin.^[39]

Millin's series gives the identity^[40]

$${\displaystyle \sum _{k=0}^{\infty }{\frac {1}{F_{2^{k}}}}={\frac {7-{\sqrt {5}}}{2}},}$$

$${\displaystyle \sum _{k=0}^{N}{\frac {1}{F_{2^{k}}}}=3-{\frac {F_{2^{N}-1}}{F_{2^{N}}}}.}$$

Primes and divisibility

Divisibility properties

Every third number of the sequence is even (a multiple of ${\displaystyle F_{3}=2}$) and, more generally, every k-th number of the sequence is a multiple of F_k. Thus the Fibonacci sequence is an example of a divisibility sequence. In fact, the Fibonacci sequence satisfies the stronger divisibility property^[41][42]

$${\displaystyle \gcd(F_{a},F_{b},F_{c},\ldots )=F_{\gcd(a,b,c,\ldots )}\,}$$

In particular, any three consecutive Fibonacci numbers are pairwise coprime because both ${\displaystyle F_{1}=1}$ and ${\displaystyle F_{2}=1}$. That is,

${\displaystyle \gcd(F_{n},F_{n+1})=\gcd(F_{n},F_{n+2})=\gcd(F_{n+1},F_{n+2})=1}$

for every n.

Every prime number p divides a Fibonacci number that can be determined by the value of p modulo 5. If p is congruent to 1 or 4 modulo 5, then p divides F_p−1, and if p is congruent to 2 or 3 modulo 5, then, p divides F_p+1. The remaining case is that p = 5, and in this case p divides F_p.

$${\displaystyle {\begin{cases}p=5&\Rightarrow p\mid F_{p},\\p\equiv \pm 1{\pmod {5}}&\Rightarrow p\mid F_{p-1},\\p\equiv \pm 2{\pmod {5}}&\Rightarrow p\mid F_{p+1}.\end{cases}}}$$

These cases can be combined into a single, non-piecewise formula, using the Legendre symbol:^[43]

$${\displaystyle p\mid F_{p\;-\,\left({\frac {5}{p}}\right)}.}$$

Primality testing

The above formula can be used as a primality test in the sense that if

$${\displaystyle n\mid F_{n\;-\,\left({\frac {5}{n}}\right)},}$$

$${\displaystyle {\begin{pmatrix}F_{m+1}&F_{m}\\F_{m}&F_{m-1}\end{pmatrix}}\equiv {\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{m}{\pmod {n}}.}$$

Fibonacci primes

A Fibonacci prime is a Fibonacci number that is prime. The first few are:^[45]

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.^[46]

F_kn is divisible by F_n, so, apart from F₄ = 3, any Fibonacci prime must have a prime index. As there are arbitrarily long runs of composite numbers, there are therefore also arbitrarily long runs of composite Fibonacci numbers.

No Fibonacci number greater than F₆ = 8 is one greater or one less than a prime number.^[47]

The only nontrivial square Fibonacci number is 144.^[48] Attila Pethő proved in 2001 that there is only a finite number of perfect power Fibonacci numbers.^[49] In 2006, Y. Bugeaud, M. Mignotte, and S. Siksek proved that 8 and 144 are the only such non-trivial perfect powers.^[50]

1, 3, 21, and 55 are the only triangular Fibonacci numbers, which was conjectured by Vern Hoggatt and proved by Luo Ming.^[51]

No Fibonacci number can be a perfect number.^[52] More generally, no Fibonacci number other than 1 can be multiply perfect,^[53] and no ratio of two Fibonacci numbers can be perfect.^[54]

Prime divisors

With the exceptions of 1, 8 and 144 (F₁ = F₂, F₆ and F₁₂) every Fibonacci number has a prime factor that is not a factor of any smaller Fibonacci number (Carmichael's theorem).^[55] As a result, 8 and 144 (F₆ and F₁₂) are the only Fibonacci numbers that are the product of other Fibonacci numbers.^[56]

The divisibility of Fibonacci numbers by a prime p is related to the Legendre symbol ${\displaystyle \left({\tfrac {p}{5}}\right)}$ which is evaluated as follows:

$${\displaystyle \left({\frac {p}{5}}\right)={\begin{cases}0&{\text{if }}p=5\\1&{\text{if }}p\equiv \pm 1{\pmod {5}}\\-1&{\text{if }}p\equiv \pm 2{\pmod {5}}.\end{cases}}}$$

If p is a prime number then

$${\displaystyle F_{p}\equiv \left({\frac {p}{5}}\right){\pmod {p}}\quad {\text{and}}\quad F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p}}.}$$

For example,

$${\displaystyle {\begin{aligned}({\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.\end{aligned}}}$$

It is not known whether there exists a prime p such that

$${\displaystyle F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p^{2}}}.}$$

Such primes (if there are any) would be called Wall–Sun–Sun primes.

Also, if p ≠ 5 is an odd prime number then:^[59]

$${\displaystyle 5{F_{\frac {p\pm 1}{2}}}^{2}\equiv {\begin{cases}{\tfrac {1}{2}}\left(5\left({\frac {p}{5}}\right)\pm 5\right){\pmod {p}}&{\text{if }}p\equiv 1{\pmod {4}}\\{\tfrac {1}{2}}\left(5\left({\frac {p}{5}}\right)\mp 3\right){\pmod {p}}&{\text{if }}p\equiv 3{\pmod {4}}.\end{cases}}}$$

Example 1. p = 7, in this case p ≡ 3 (mod 4) and we have:

$${\displaystyle ({\tfrac {7}{5}})=-1:\qquad {\tfrac {1}{2}}\left(5({\tfrac {7}{5}})+3\right)=-1,\quad {\tfrac {1}{2}}\left(5({\tfrac {7}{5}})-3\right)=-4.}$$

$${\displaystyle F_{3}=2{\text{ and }}F_{4}=3.}$$