This site is supported by donations to The OEIS Foundation.
Fibonacci numbers
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.
Contents
Recurrence equation
The Fibonacci numbers are defined by the following homogeneous linear recurrence of order 2 and signature (1, 1)
F (n) = F (n − 1) + F (n − 2) |
F (0) = 0 |
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)
x −1 |
10 k |
k |
k |
-
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
k |
k |
-
(A021093)k = 1: 1 / 89 = 0.011235955056179775280898876404...
-
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 thatf (x) |
Fn −1 |
x f (x) |
Fn −2 |
x 2 f (x) |
x f (x) + x 2 f (x) |
f (x) |
F0 = 0 |
F1 = 1 |
f (x) |
−1 =
|
k 2 − k − 1 = 0 |
k + =
|
k − =
|
ϕ : k + |
φ : k − |
ϕ φ = −1 |
These two formal power series are known explicitly because they are geometric series; comparing coefficients
we find the explicit formula
ϕ =
|
φ =
|
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
F (2 n) = |
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
a (n) = 3 a (n − 1) − a (n − 2) |
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
n |
n |
(minimal? i.e.
m > n ⟹ |
(m) > |
(n) |
(see A189761)
residues[2]
A066853
A189768 Irregular triangle in which row
n |
Fibonacci (i) mod n |
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, ...}
n |
F (i) mod n |
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, ...}
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, ...}
n |
F (k) mod n |
{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, ...}
n |
{Fibonacci (k) mod n, k = 0, 1, 2, ...} |
-
{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, ...}
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, ...}
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, ...}
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, ...}
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, ...}
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 modn |
-
{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, ...}
k |
{Fibonacci (i) mod n, i = 0 .. k − 1} |
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 |
-
{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).
- ???
??? (Some terms from 1 to 55 might be missing ...){1, 2, 3, 4, 5, 7, 8, 11, 13, 17, 21, 34, 55, ...}
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
- ↑ Partitions and the Fibonacci Numbers, YouTube Video, Uploaded by Dr. James Tanton on Apr 20, 2011.
- ↑ Note that some integers, e.g.
, never happen as the number of residues of Fibonacci numbers mod8
, for anyn
.n ∈ ℕ+