Fibonacci numbers - OeisWiki (2024)

This is the latest approved revision, approved on 8 February 2018.The draft has 15 changes awaiting review.

Readability: Reviewed

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.

1 Recurrence equation
2 Generating function
3 Binet's closed-form formula
- 3.1 Fibonacci function
4 Limit of consecutive quotients
5 Formulae
- 5.1 Even indexed Fibonacci numbers
- 5.2 Odd indexed Fibonacci numbers
6 Fibonacci numbers mod n
- 6.1 Pisano periods
  - 6.1.1 Numbers for which the Pisano period is minimal
7 Fibonacci primes
8 Sequences
9 See also
10 Notes

Recurrence equation

The Fibonacci numbers are defined by the following hom*ogeneous 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

10 k

, we get the form

For example, for the first few values of

, we have (note that overlapping occurs when Fibonacci numbers have more than

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

, we have (note that overlapping occurs when Fibonacci numbers have more than

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

x f (x)

and that of

Fn −2

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

Since

F0 = 0

and

F1 = 1

, we obtain

Solving this equation for

f (x)

, we get

with

−1 =

⎛

⎝

−k +

⎞

⎠

, giving the quadratic equation

k 2 − k − 1 = 0

with the roots

k + =

1 + 2√ 5

(the golden ratio) and

k − =

1 − 2√ 5

.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

and

φ =

1 − 2√ 5

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)

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) ? (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

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

(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

{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

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

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

{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

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, ...}

Notes

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

Fibonacci numbers - OeisWiki (2024)

Contents

Recurrence equation

Generating function

Binet's closed-form formula

Fibonacci function

Limit of consecutive quotients

Formulae

Even indexed Fibonacci numbers

Odd indexed Fibonacci numbers

Fibonacci numbers mod n

Pisano periods

Numbers for which the Pisano period is minimal

Fibonacci primes

Sequences

See also

Notes