This site is supported by donations to The OEIS Foundation.

Fibonacci numbers

From OeisWiki
(Redirected from Binet formula)
Jump to: navigation, search

This article needs more work.

Please contribute in expanding it!


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)

A000045 Fibonacci numbers:
F (n) = F (n − 1) + F (n − 2)
with
F (0) = 0
and
F (1) = 1
.

Generating function

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

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

and setting
x −1
to
10k
, we get the form
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

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
for this sequence. The generating function for the sequence
Fn −1
is
xf  (x)
and that of
Fn −2
is
x 2f  (x)
. From the recurrence relation, we see that the power series
xf  (x) + x 2f  (x)
agrees with
f  (x)
except for the first two coefficients
Since
F0 = 0
and
F1 = 1
, we obtain
Solving this equation for
f  (x)
, we get
with
−1 =
  −k +
1
k
   
, giving the quadratic equation
k 2k − 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

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

we find the explicit formula

where
ϕ =
1 + 2  5 
2
and
φ =
1 − 2  5 
2
.

Fibonacci function

We can rewrite the Binet formula for Fibonacci numbers as

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

Or we could generalize over the complex numbers thus

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

Formulae

Even indexed Fibonacci numbers

The even indexed Fibonacci numbers are given by the recurrence

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

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)
? Green tickY (yes), Red crossY (no))
(see A189761)
Number of
residues[2]
A066853
1 {0} Green tickY 1
2 {0, 1} Green tickY 2
3 {0, 1, 2} Green tickY 3
4 {0, 1, 2, 3} Green tickY 4
5 {0, 1, 2, 3, 4} Green tickY 5
6 {0, 1, 2, 3, 4, 5} Red crossY 6
7 {0, 1, 2, 3, 4, 5, 6} Red crossY 7
8 {0, 1, 2, 3, 5, 7} Green tickY 6
9 {0, 1, 2, 3, 4, 5, 6, 7, 8} Red crossY 9
10 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Red crossY 10
11 {0, 1, 2, 3, 5, 8, 10} Green tickY 7
12 {0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11} Red crossY 11
13 {0, 1, 2, 3, 5, 8, 10, 11, 12} Red crossY 9
14 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13} Red crossY 14
15 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14} Red crossY 15
16 {0, 1, 2, 3, 5, 7, 8, 9, 11, 13, 15} Red crossY 11
17 {0, 1, 2, 3, 4, 5, 8, 9, 12, 13, 14, 15, 16} Red crossY 13
18 {0, 1, 2, 3, 5, 8, 10, 13, 15, 16, 17} Red crossY 11
19 {0, 1, 2, 3, 5, 8, 11, 13, 15, 16, 17, 18} Red crossY 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} Green tickY 9
22 {0, 1, 2, 3, 5, 8, 10, 11, 12, 13, 14, 16, 19, 21} Red crossY 14
23 {0, 1, 2, 3, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17, 18, 20, 21, 22} Red crossY 19
24 {0, 1, 2, 3, 5, 7, 8, 10, 13, 16, 17, 21, 23} Red crossY 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} Red crossY 25
26 {0, 1, 2, 3, 5, 8, 10, 11, 12, 13, 14, 15, 16, 18, 21, 23, 24, 25} Red crossY 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} Red crossY 27
28 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 15, 17, 20, 21, 22, 24, 25, 26, 27} Red crossY 21
29 {0, 1, 2, 3, 5, 8, 13, 21, 26, 28} Green tickY 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} Red crossY 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, ...}

See also


  • {{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 ∈ ℕ+
    .