This site is supported by donations to The OEIS Foundation.

# Fibonacci numbers

(Redirected from Binet formula)

The Fibonacci sequence [or Fibonacci numbers] is named after Leonardo of Pisa, known as Fibonacci. Fibonacci's 1202 book Liber Abaci introduced the sequence as an exercise, although the sequence had been previously described by Virahanka in a commentary of the metrical work of Pingala.

## Recurrence equation

The Fibonacci numbers are defined by the following homogeneous linear recurrence of order 2 and signature (1, 1)

${\displaystyle F_{0}:=0,\,}$
${\displaystyle F_{1}:=1,\,}$
${\displaystyle F_{n}:=F_{n-1}+F_{n-2},\quad n\geq 2.\,}$
A000045 Fibonacci numbers:
 F (n) = F (n − 1) + F (n − 2)
with
 F (0) = 0
and
 F (1) = 1
.
${\displaystyle {0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,...}}$

## Generating function

The ordinary generating function of the Fibonacci numbers is (the proof is given in the next section)

${\displaystyle G_{\{F_{n},\,n\geq 0\}}(x)={\frac {x}{1-x-x^{2}}}=\sum _{n=0}^{\infty }F_{n}\,x^{n}.}$

Rewriting the generating function as (which shows the form of the recurrence in the denominator)

${\displaystyle G_{\{F_{n},\,n\geq 0\}}(x)={\frac {(x^{-1})^{1}}{(x^{-1})^{2}-(x^{-1})^{1}-(x^{-1})^{0}}},}$
and setting
 x −1
to
 10 k
, we get the form
${\displaystyle {\frac {(10^{k})^{1}}{(10^{k})^{2}-(10^{k})^{1}-(10^{k})^{0}}}={\frac {10^{k}}{10^{2k}-10^{k}-1}}=\sum _{i=0}^{\infty }{\frac {F_{i}}{(10^{k})^{i}}},\quad k\geq 1.}$
For example, for the first few values of
 k
, we have (note that overlapping occurs when Fibonacci numbers have more than
 k
digits)
 k = 1: 10 / 89 = 0.11235955056179775280898876404...
 k = 2: 100 / 9899 = 0.010102030508132134559046368320...
 k = 3: 1000 / 998999 = 0.0010010020030050080130210340550...
 k = 4: 10000 / 99989999 = 0.00010001000200030005000800130021...

A variant of the above is

${\displaystyle {\frac {1}{(10^{k})^{2}-(10^{k})^{1}-(10^{k})^{0}}}={\frac {1}{10^{2k}-10^{k}-1}}=\sum _{i=0}^{\infty }{\frac {F_{i}}{(10^{k})^{i+1}}},\quad k\geq 1.\,}$
For example, for the first few values of
 k
, we have (note that overlapping occurs when Fibonacci numbers have more than
 k
digits)
 k = 1: 1 / 89 = 0.011235955056179775280898876404...
(A021093)
 k = 2: 1 / 9899 = 0.00010102030508132134559046368320...
 k = 3: 1 / 998999 = 0.0000010010020030050080130210340550...
 k = 4: 1 / 99989999 = 0.000000010001000200030005000800130021...

## Binet's closed-form formula

Let's consider the problem of finding a closed-form formula for the Fibonacci numbers. Assume that
 f  (x)
is the (yet to be found) ordinary generating function
${\displaystyle f(x)=\sum _{n=0}^{\infty }F_{n}~x^{n}\,}$
for this sequence. The generating function for the sequence
 Fn −1
is
 x f  (x)
and that of
 Fn −2
is
 x 2 f  (x)
. From the recurrence relation, we see that the power series
 x f  (x) + x 2 f  (x)
agrees with
 f  (x)
except for the first two coefficients
${\displaystyle {\begin{array}{rcrcrcrcrcrcr}f(x)&=&F_{0}\,x^{0}&+&F_{1}\,x^{1}&+&F_{2}\,x^{2}&+&\cdots &+&F_{i}\,x^{i}&+&\cdots \\xf(x)&=&&&F_{0}\,x^{1}&+&F_{1}\,x^{2}&+&\cdots &+&F_{i-1}\,x^{i}&+&\cdots \\x^{2}f(x)&=&&&&&F_{0}\,x^{2}&+&\cdots &+&F_{i-2}\,x^{i}&+&\cdots \\(x+x^{2})f(x)&=&&&F_{0}\,x^{1}&+&(F_{0}+F_{1})\,x^{2}&+&\cdots &+&(F_{i-1}+F_{i-2})\,x^{i}&+&\cdots \\&=&&&&&F_{2}\,x^{2}&+&\cdots &+&F_{i}\,x^{i}&+&\cdots \\\end{array}}}$
Since
 F0 = 0
and
 F1 = 1
, we obtain
${\displaystyle f(x)=x+xf(x)+x^{2}f(x).\,}$
Solving this equation for
 f  (x)
, we get
${\displaystyle f(x)={\frac {x}{1-x-x^{2}}}={\frac {x}{(1-kx)(1+{\frac {1}{k}}x)}},\,}$
with
−1 =
 ⎛ ⎝
−k +
 1 k

 ⎞ ⎠
 k 2 − k − 1 = 0
with the roots
k + =
 1 + 2√  5 2
(the golden ratio) and
k − =
 1 − 2√  5 2
. Defining
 ϕ : k +
and
 φ : k −
, and noting that
 ϕ φ = −1
, the technique of partial fraction decomposition yields
${\displaystyle f(x)={\frac {x}{(1-\phi x)(1-\varphi x)}}={\frac {1}{\phi -\varphi }}\left({\frac {1}{1-\phi x}}-{\frac {1}{1-\varphi x}}\right)={\frac {1}{\sqrt {5}}}\left({\frac {1}{1-\phi x}}-{\frac {1}{1-\varphi x}}\right).\,}$

These two formal power series are known explicitly because they are geometric series; comparing coefficients

${\displaystyle f(x)={\frac {1}{\sqrt {5}}}\left(\sum _{n=0}^{\infty }(\phi x)^{n}-\sum _{n=0}^{\infty }(\varphi x)^{n}\right)=\sum _{n=0}^{\infty }{\frac {\phi ^{n}-\varphi ^{n}}{\sqrt {5}}}\,x^{n},\,}$

we find the explicit formula

${\displaystyle F_{n}={\frac {\phi ^{n}-\varphi ^{n}}{\phi -\varphi }}={\frac {\phi ^{n}-\varphi ^{n}}{\sqrt {5}}},\,}$
where
ϕ =
 1 + 2√  5 2
and
φ =
 1 − 2√  5 2
.

### Fibonacci function

We can rewrite the Binet formula for Fibonacci numbers as

${\displaystyle F_{n}={\frac {1}{\sqrt {5}}}\left(\phi ^{n}-\varphi ^{n}\right)={\frac {1}{\sqrt {5}}}\left(\phi ^{n}-\left({\frac {-1}{\phi }}\right)^{n}\right)={\frac {1}{\sqrt {5}}}\left(\phi ^{n}-(-1)^{n}{\phi }^{-n}\right),\quad n\in \mathbb {Z} .}$

This provides a way to generalize to a Fibonacci function over the real numbers as

${\displaystyle F(x)={\frac {1}{\sqrt {5}}}\left(\phi ^{x}-\cos(\pi x)\,{\phi }^{-x}\right),\quad x\in \mathbb {R} .}$

Or we could generalize over the complex numbers thus

${\displaystyle F(z)={\frac {1}{\sqrt {5}}}\left(\phi ^{z}-e^{i\pi z}\,{\phi }^{-z}\right)={\frac {1}{\sqrt {5}}}\left(\phi ^{z}-\left({\frac {e^{i\pi }}{\phi }}\right)^{z}\right),\quad z\in \mathbb {C} .}$

## 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

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

## Formulae

### Even indexed Fibonacci numbers

The even indexed Fibonacci numbers are given by the recurrence

${\displaystyle F_{0}=0,\,}$
${\displaystyle F_{2}=1,\,}$
${\displaystyle F_{2n}=3F_{2n-2}-F_{2n-4},\quad n\geq 2.\,}$
A001906
 F (2 n) =
bisection of Fibonacci sequence:
 a (n) = 3 a (n − 1) − a (n − 2)
.
 {0, 1, 3, 8, 21, 55, 144, 377, 987, 2584, 6765, 17711, 46368, 121393, 317811, 832040, 2178309, 5702887, 14930352, 39088169, 102334155, 267914296, 701408733, 1836311903, ...}

The even indexed Fibonacci numbers are related to ordered partitions.[1]

### Odd indexed Fibonacci numbers

The odd indexed Fibonacci numbers are given by the recurrence

${\displaystyle F_{-1}=1,\,}$
${\displaystyle F_{1}=1,\,}$
${\displaystyle F_{2n-1}=3F_{2n-3}-F_{2n-5},\quad n\geq 2.\,}$
A001519
 a (n) = 3 a (n − 1) − a (n − 2)
, with
 a (0) = a (1) = 1
.
 {1, 1, 2, 5, 13, 34, 89, 233, 610, 1597, 4181, 10946, 28657, 75025, 196418, 514229, 1346269, 3524578, 9227465, 24157817, 63245986, 165580141, 433494437, 1134903170, 2971215073, ...}

## Fibonacci numbers mod n

Set of residues of the Fibonacci numbers mod
 n

 n
Set of residues
(minimal? i.e.
 m > n ⟹
A066853
 (m) >
A066853
 (n)
? (yes), (no))
(see A189761)
Number of
residues[2]
A066853
1 {0} 1
2 {0, 1} 2
3 {0, 1, 2} 3
4 {0, 1, 2, 3} 4
5 {0, 1, 2, 3, 4} 5
6 {0, 1, 2, 3, 4, 5} 6
7 {0, 1, 2, 3, 4, 5, 6} 7
8 {0, 1, 2, 3, 5, 7} 6
9 {0, 1, 2, 3, 4, 5, 6, 7, 8} 9
10 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 10
11 {0, 1, 2, 3, 5, 8, 10} 7
12 {0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11} 11
13 {0, 1, 2, 3, 5, 8, 10, 11, 12} 9
14 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13} 14
15 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14} 15
16 {0, 1, 2, 3, 5, 7, 8, 9, 11, 13, 15} 11
17 {0, 1, 2, 3, 4, 5, 8, 9, 12, 13, 14, 15, 16} 13
18 {0, 1, 2, 3, 5, 8, 10, 13, 15, 16, 17} 11
19 {0, 1, 2, 3, 5, 8, 11, 13, 15, 16, 17, 18} 12
20 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19} 20
21 {0, 1, 2, 3, 5, 8, 13, 18, 20} 9
22 {0, 1, 2, 3, 5, 8, 10, 11, 12, 13, 14, 16, 19, 21} 14
23 {0, 1, 2, 3, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17, 18, 20, 21, 22} 19
24 {0, 1, 2, 3, 5, 7, 8, 10, 13, 16, 17, 21, 23} 13
25 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24} 25
26 {0, 1, 2, 3, 5, 8, 10, 11, 12, 13, 14, 15, 16, 18, 21, 23, 24, 25} 18
27 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26} 27
28 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 15, 17, 20, 21, 22, 24, 25, 26, 27} 21
29 {0, 1, 2, 3, 5, 8, 13, 21, 26, 28} 10
30 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29} 30

A189768 Irregular triangle in which row
 n
contains the set of residues of the sequence
 Fibonacci (i) mod n
for all
 i ≥ 0
.
 {0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 5, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 5, 8, 10, 0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 0, 1, 2, 3, ...}
A066853 Number of different remainders (or residues) for the Fibonacci numbers (A000045) when divided by
 n
(i.e. the size of the set of
 F (i) mod n
over all
 i ≥ 0
).
 {1, 2, 3, 4, 5, 6, 7, 6, 9, 10, 7, 11, 9, 14, 15, 11, 13, 11, 12, 20, 9, 14, 19, 13, 25, 18, 27, 21, 10, 30, 19, 21, 19, 13, 35, 15, 29, 13, 25, 30, 19, 18, 33, 20, 45, 21, 15, 15, 37, 50, 35, 30, 37, 29, 12, 25, ...}
A118965 Number of missing residues in Fibonacci sequence mod
 n
.
 {0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 4, 1, 4, 0, 0, 5, 4, 7, 7, 0, 12, 8, 4, 11, 0, 8, 0, 7, 19, 0, 12, 11, 14, 21, 0, 21, 8, 25, 14, 10, 22, 24, 10, 24, 0, 25, 32, 33, 12, 0, 16, 22, 16, 25, 43, 31, 24, 38, 22, 5, 36, 41, ...}
A079002 Numbers
 n
such that the Fibonacci residues
 F (k) mod n
form the complete set
 {0, 1, 2, ..., n − 1}
.
 {1, 2, 3, 4, 5, 6, 7, 9, 10, 14, 15, 20, 25, 27, 30, 35, 45, 50, 70, 75, 81, 100, 125, 135, 150, 175, 225, 243, 250, 350, 375, 405, 500, 625, 675, 729, 750, 875, 1125, 1215, 1250, 1750, 1875, 2025, 2187, ...}
A189761 Numbers
 n
for which the set of residues
 {Fibonacci (k) mod n, k = 0, 1, 2, ...}
is minimal.
 {1, 2, 3, 4, 5, 8, 11, 21, 29, 55, 76, 144, 199, 377, 521, 987, 1364, 2584, 3571, 6765, 9349, 17711, 24476, 46368, 64079, 121393, 167761, 317811, 439204, 832040, 1149851, 2178309, 3010349, 5702887, ...}
A007887
 Fibonacci (n) mod 9
.
 {0, 1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8, 0, 8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1, 0, 1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8, 0, 8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1, 0, 1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8, 0, 8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1, 0, 1, 1, 2, 3, 5, ...}
A003893
 Fibonacci (n) mod 10
.
 {0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1, 0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, ...}
A089911
 Fibonacci (n) mod 12
.
 {0, 1, 1, 2, 3, 5, 8, 1, 9, 10, 7, 5, 0, 5, 5, 10, 3, 1, 4, 5, 9, 2, 11, 1, 0, 1, 1, 2, 3, 5, 8, 1, 9, 10, 7, 5, 0, 5, 5, 10, 3, 1, 4, 5, 9, 2, 11, 1, 0, 1, 1, 2, 3, 5, 8, 1, 9, 10, 7, 5, 0, 5, 5, 10, 3, 1, 4, 5, 9, 2, 11, 1, 0, ...}
A079345
 Fibonacci (n) mod 16
.
 {0, 1, 1, 2, 3, 5, 8, 13, 5, 2, 7, 9, 0, 9, 9, 2, 11, 13, 8, 5, 13, 2, 15, 1, 0, 1, 1, 2, 3, 5, 8, 13, 5, 2, 7, 9, 0, 9, 9, 2, 11, 13, 8, 5, 13, 2, 15, 1, 0, 1, 1, 2, 3, 5, 8, 13, 5, 2, 7, 9, 0, 9, 9, 2, 11, 13, 8, 5, 13, 2, 15, ...}
A105471
 Fibonacci (n) mod 100
.
 {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 44, 33, 77, 10, 87, 97, 84, 81, 65, 46, 11, 57, 68, 25, 93, 18, 11, 29, 40, 69, 9, 78, 87, 65, 52, 17, 69, 86, 55, 41, 96, 37, 33, 70, 3, 73, 76, 49, 25, 74, 99, 73, 72, 45, ...}

### Pisano periods

A001175 Pisano periods (or Pisano numbers): period of Fibonacci numbers mod
 n
.
 {1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, 24, 18, 60, 16, 30, 48, 24, 100, 84, 72, 48, 14, 120, 30, 48, 40, 36, 80, 24, 76, 18, 56, 60, 40, 48, 88, 30, 120, 48, 32, 24, 112, 300, 72, 84, 108, ...}
A189767 Least number
 k
such that the set of numbers
 {Fibonacci (i) mod n, i = 0 .. k − 1}
contains all possible residues of
 Fibonacci (i) mod n
.
 {1, 2, 4, 5, 10, 10, 13, 11, 17, 22, 9, 23, 19, 37, 20, 23, 25, 19, 17, 53, 15, 25, 37, 23, 50, 61, 53, 45, 13, 58, 29, 47, 39, 25, 77, 23, 55, 17, 47, 59, 31, 37, 65, 29, 93, 37, 25, 23, 81, 148, 67, 75, 77, 53, 19, ...}

#### Numbers for which the Pisano period is minimal

The numbers for which the Pisano period is minimal are conjectured to be A109794
 (n)
,
 n ≥ 4
. (see {{Sequence of the Day for August 7}})
 {8, 11, 21, 29, 55, 76, 144, 199, 377, 521, 987, 1364, 2584, 3571, 6765, 9349, 17711, 24476, 46368, 64079, 121393, 167761, 317811, 439204, 832040, 1149851, 2178309, 3010349, 5702887, 7881196, ...}

## Fibonacci primes

Fibonacci primes.

 {2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, ...}

Indexes of Fibonacci primes.

 {3, 4, 5, 7, 11, 13, 17, 23, 29, 43, ...}

## Sequences

A065108 Numbers [positive integers] expressible as a product of Fibonacci numbers (A000045).

 {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 15, 16, 18, 20, 21, 24, 25, 26, 27, 30, 32, 34, 36, 39, 40, 42, 45, 48, 50, 52, 54, 55, 60, 63, 64, 65, 68, 72, 75, 78, 80, 81, 84, 89, 90, 96, ...}

A?????? Numbers [positive integers] expressible as a quotient of Fibonacci numbers (A000045).

???
 {1, 2, 3, 4, 5, 7, 8, 11, 13, 17, 21, 34, 55, ...}
??? (Some terms from 1 to 55 might be missing ...)

A178772 Fibonacci integers, i.e. positive integers that can be written as the product and/or quotient of Fibonacci numbers (A000045).

 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 38, 39, 40, 41, 42, 44, 45, 46, 47, 48, 49, 50, ...}

• {{Fibonacci}} (mathematical function template)

## Notes

1. Partitions and the Fibonacci Numbers, YouTube Video, Uploaded by Dr. James Tanton on Apr 20, 2011.
2. Note that some integers, e.g.
 8
, never happen as the number of residues of Fibonacci numbers mod
 n
, for any
 n ∈ ℕ+
.