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.

Recurrence equation

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

$F_{0}:=0,\,$

$F_{1}:=1,\,$

$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

.

${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)

$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)

$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

${\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

${\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

$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

${\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

$f(x)=x+xf(x)+x^{2}f(x).\,$

Solving this equation for

f  (x)

, we get

$f(x)={\frac {x}{1-x-x^{2}}}={\frac {x}{(1-kx)(1+{\frac {1}{k}}x)}},\,$

with

−1 = ⎛ ⎝   −k + 1 k     ⎞ ⎠

, giving the quadratic equation

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

$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

$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

$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

$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

$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

$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

$\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

$F_{0}=0,\,$

$F_{2}=1,\,$

$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.

Odd indexed Fibonacci numbers

The odd indexed Fibonacci numbers are given by the recurrence

$F_{-1}=1,\,$

$F_{1}=1,\,$

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

• Lucas numbers
• Golden ratio
• Phi numeral system
• Binary Fibonacci rabbits sequence

• {{Fibonacci}} (mathematical function template)

• Tribonacci numbers