Namespaces
Variants
Actions

Difference between revisions of "Fibonacci numbers"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(shorter introduction)
(11 intermediate revisions by the same user not shown)
Line 1: Line 1:
The elements of the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f0400201.png" /> given by the initial values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f0400202.png" /> and the recurrence relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f0400203.png" />. The first 14 Fibonacci numbers were produced for the first time in 1228 in the manuscripts of Leonardo da Pisa (Fibonacci).
+
{{TEX|done}}{{MSC|11B39}}
 +
 
 +
A [[recursive sequence]] of integers in which each term is the sum of the two preceding.
 +
The elements of the sequence $u_1,u_2,\ldots$ are given by the initial values $u_1 = u_2 = 1$ and the recurrence relation $u_{n+1} = u_n + u_{n-1}$. The first 14 Fibonacci numbers were produced for the first time in 1228 in the manuscripts of Leonardo da Pisa (Fibonacci).
  
 
Operations that can be performed on the indices of the Fibonacci numbers can be reduced to operations on the numbers themselves. The basis for this lies in the  "addition formula" :
 
Operations that can be performed on the indices of the Fibonacci numbers can be reduced to operations on the numbers themselves. The basis for this lies in the  "addition formula" :
 
+
$$
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f0400204.png" /></td> </tr></table>
+
u_{n+m} = u_{m-1} u_n + u_m u_{n+1}
 +
$$
  
 
Immediate corollaries of it are:
 
Immediate corollaries of it are:
 
+
$$
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f0400205.png" /></td> </tr></table>
+
u_{2n} = u_n(u_{n+1} + u_{n-1})\,\ \  u_{3n} = u_{n+1}^3 + u_n^3 - u_{n-1}^3
 
+
$$
 
etc. The general  "multiplication formula"  is more complicated:
 
etc. The general  "multiplication formula"  is more complicated:
 +
$$
 +
u_{mn} = \sum_{k=1}^m \binom{m}{k} u_k u_n^k u_{n-1}^{m-k} \ . 
 +
$$
 +
The elementary divisibility properties of the Fibonacci numbers are mainly determined by the following facts: $u_{(m,n)} = (u_m,u_n)$; if $p$ is a prime number of the form $p \equiv \pm 1 \pmod 5$, then $u_{p-1}$ is divisible by $p$, while if it is of the form $p \equiv \pm 2 \pmod 5$, then $u_{p+1}$ is; if $u_n$ is divisible by a prime number $q$ and if $p \neq q$, then $u_{pn}/u_n$ is not divisible by $q$; if $u_n$ is divisible by a prime number $p \neq 2$, then $u_{pn}/u_n$ is divisible by $p$, but not by $p^2$; if $u_n$ is divisible by 4, then $u_{2n}/u_n$ is divisible by 2, but not by 4; if $u_n$ is divisible by 2 but not by 4, then $u_{2n}/u_n$ is divisible by 4, but not by 8. At the same time, some number-theoretic problems connected with Fibonacci numbers are extremely hard. For example, the question of whether the set of prime Fibonacci numbers is finite or not has not been solved (1984).
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f0400206.png" /></td> </tr></table>
+
An important role in the theory of Fibonacci numbers is played by the number $\phi = (1+\sqrt 5)/2$, which is a root of the equation $x^2 - x - 1 = 0$. Thus Binet's formula
 +
$$
 +
u_n = \frac{1}{\sqrt 5}(\phi^n - (-\phi)^{-n})
 +
$$
 +
holds; it implies that $u_n$ is the nearest integer to $\phi^n/\sqrt 5$, and that
 +
$$
 +
\lim_{n \rightarrow \infty} \frac{u_{n+1}}{u_n} = \phi \ .
 +
$$
  
The elementary divisibility properties of the Fibonacci numbers are mainly determined by the following facts: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f0400207.png" />; if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f0400208.png" /> is a prime number of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f0400209.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002010.png" /> is divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002011.png" />, while if it is of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002012.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002013.png" /> is; if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002014.png" /> is divisible by a prime number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002015.png" /> and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002016.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002017.png" /> is not divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002018.png" />; if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002019.png" /> is divisible by a prime number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002020.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002021.png" /> is divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002022.png" />, but not by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002023.png" />; if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002024.png" /> is divisible by 4, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002025.png" /> is divisible by 2, but not by 4; if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002026.png" /> is divisible by 2 but not by 4, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002027.png" /> is divisible by 4, but not by 8. At the same time, some number-theoretic problems connected with Fibonacci numbers are extremely hard. For example, the question of whether the set of prime Fibonacci numbers is finite or not has not been solved (1984).
+
The Fibonacci numbers occupy a special position in the theory of [[continued fraction]]s. In the continued-fraction expansion of $u_{n+1}/u_n$ all the partial quotients are ones and the number of them is not less than that of the incomplete quotients of the expansion of any other fraction with denominator less than $u_n$. In a certain sense the number $\phi$ is described by its [[Convergent of a continued fraction|approximating fraction]]s $u_{n+1}/u_n$ in a "worst possible" way.
  
An important role in the theory of Fibonacci numbers is played by the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002028.png" />, which is a root of the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002029.png" />. Thus Binet's formula
+
====References====
 +
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top">  B. Boncompagni,  "Il Liber Abbaci di Leonardo Pisano" , Rome  (1857)</TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top">  N.N. Vorob'ev,  "Fibonacci numbers" , Moscow  (1984)  (In Russian). English translation by Mircea Martin: Birkhäuser (2002) ISBN 3764361352 {{ZBL|1014.11012}}</TD></TR>
 +
<TR><TD valign="top">[3]</TD> <TD valign="top">  V.E. Hoggatt,  "Fibonacci and Lucas numbers" , Univ. Santa Clara  (1969)</TD></TR>
 +
<TR><TD valign="top">[4]</TD> <TD valign="top">  U. (or A. Brousseau) Alfred,  "An introduction to Fibonacci discovery" , San José, CA  (1965)</TD></TR>
 +
<TR><TD valign="top">[5]</TD> <TD valign="top">  ''Fibonacci Quart.''  (1963-)</TD></TR>
 +
</table>
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002030.png" /></td> </tr></table>
+
====Comments====
 +
Let $P,Q$ be non-zero integers with $\mathrm{hcf}(P,Q) = 1$ and $D = P^2 - 4Q \neq 0$. A ''[[Lucas sequence]]'', or a sequence of Lucas numbers, is defined by $U_0 = 0$, $U_1 = 1$ and the linear recurrence relation
 +
$$
 +
U_{n+1} = P.U_n - Q.U_{n-1} \ .
 +
$$
  
holds; it implies that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002031.png" /> is the nearest integer to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002032.png" />, and that
+
Still more generally, a sequence $U_0,U_1,\ldots$ of complex numbers, i.e. a number-theoretic or [[arithmetic function]], is said to be recurrent of order $r$ if there is a complex-valued function $f$ of $r$ variables such that $U_{n+r} = f(U_{n+r-1},\ldots, U_n)$, $n = 0,1,\ldots$. If $f$ is linear, $(U_n)$ is called a ''linear recurrent sequence''. Both the Fibonacci and the Lucas numbers are linearly recurrent of order 2. Cf. [[Recurrence relation]], [[Recursive sequence]].
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002033.png" /></td> </tr></table>
+
For some more results on Fibonacci numbers, Lucas numbers and recurrent sequences, as well as for their manifold applications, cf. also [[#References|[a1]]].
 
 
The Fibonacci numbers occupy a special position in the theory of continued fractions. In the continued-fraction expansion of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002034.png" /> all the partial quotients are ones and the number of them is not less than that of the incomplete quotients of the expansion of any other fraction with denominator less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002035.png" />. In a certain sense the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002036.png" /> is described by its approximating fractions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002037.png" /> in a  "worst possible"  way.
 
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  B. Boncompagni,  "Illiber Abbaci di Leonardo Pisano" , Rome  (1857)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  N.N. Vorob'ev,  "Fibonacci numbers" , Moscow  (1984)  (In Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> V.E. Hoggatt,  "Fibonacci and Lucas numbers" , Univ. Santa Clara  (1969)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top"> U. (or A. Brousseau) Alfred,  "An introduction to Fibonacci discovery" , San José, CA  (1965)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  ''Fibonacci Quart.''  (1963-)</TD></TR></table>
+
<table>
 
+
<TR><TD valign="top">[a1]</TD> <TD valign="top">  A.N. Phillipou (ed.)  G.E. Bergum (ed.)  A.F. Horodam (ed.) , ''Fibonacci numbers and their applications'' , Reidel (1986)</TD></TR>
 
+
</table>
  
 
====Comments====
 
====Comments====
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002038.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002039.png" /> be non-zero integers with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002040.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002041.png" />. A Lucas sequence, or a sequence of Lucas numbers, is defined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002042.png" /> and the linear recurrence relation
+
The Fibonacci sequence may be extended to non-positive indices by setting $u_0 = 0$ and $u_{-n} = (-1)^n u_n$. The recurrence relation remains valid and Binet's formula still holds.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002043.png" /></td> </tr></table>
+
The '''Lucas numbers''' $(v_n)$ are defined by $v_0 = 2$, $v_1 = 1$ and the same recurrence relation $v_{n+1} = v_n + v_{n-1}$.  They have a close connection with the Fibonacci numbers and similar addition and multiplication formulae, many of which may be derived from the formulae
 +
$$
 +
v_n = \phi^n + (-\phi)^{-n}
 +
$$
 +
and
 +
$$
 +
\phi^n = \frac{v_n + u_n\sqrt5}{2} \ .
 +
$$
 +
The Fibonacci and Lucas numbers are the [[Lucas sequence]]s of the first and second kind respectively for the parameters $P=1$, $Q=1$.
  
Still more generally, a sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002044.png" /> of complex numbers, i.e. a number-theoretic or [[Arithmetic function|arithmetic function]], is said to be recurrent of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002045.png" /> if there is a complex-valued function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002046.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002047.png" /> variables such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002048.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002049.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002050.png" /> is linear, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040020/f04002051.png" /> is called a linear recurrent sequence. Both the Fibonacci and the Lucas numbers are linearly recurrent of order 2.
+
For a translation of the ''Liber Abaci'', see [[#References|[b1]]]: the sequence is defined in Chapter 12.
 
 
For some more results on Fibonacci numbers, Lucas numbers and recurrent sequences, as well as for their manifold applications, cf. also [[#References|[a1]]].
 
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A.N. Phillipou (ed.)  G.E. Bergum (ed.)  A.F. Horodam (ed.) , ''Fibonacci numbers and their applications'' , Reidel  (1986)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[b1]</TD> <TD valign="top">  Laurence Sigler, "Fibonacci's Liber Abaci: A Translation Into Modern English of Leonardo Pisano's Book of Calculation", Sources and Studies in the History of Mathematics and Physical Sciences, Springer (2003) ISBN 0-387-40737-5 {{ZBL|1038.01025}}</TD></TR>
 +
</table>

Revision as of 22:28, 30 December 2014

2020 Mathematics Subject Classification: Primary: 11B39 [MSN][ZBL]

A recursive sequence of integers in which each term is the sum of the two preceding. The elements of the sequence $u_1,u_2,\ldots$ are given by the initial values $u_1 = u_2 = 1$ and the recurrence relation $u_{n+1} = u_n + u_{n-1}$. The first 14 Fibonacci numbers were produced for the first time in 1228 in the manuscripts of Leonardo da Pisa (Fibonacci).

Operations that can be performed on the indices of the Fibonacci numbers can be reduced to operations on the numbers themselves. The basis for this lies in the "addition formula" : $$ u_{n+m} = u_{m-1} u_n + u_m u_{n+1} $$

Immediate corollaries of it are: $$ u_{2n} = u_n(u_{n+1} + u_{n-1})\,\ \ u_{3n} = u_{n+1}^3 + u_n^3 - u_{n-1}^3 $$ etc. The general "multiplication formula" is more complicated: $$ u_{mn} = \sum_{k=1}^m \binom{m}{k} u_k u_n^k u_{n-1}^{m-k} \ . $$ The elementary divisibility properties of the Fibonacci numbers are mainly determined by the following facts: $u_{(m,n)} = (u_m,u_n)$; if $p$ is a prime number of the form $p \equiv \pm 1 \pmod 5$, then $u_{p-1}$ is divisible by $p$, while if it is of the form $p \equiv \pm 2 \pmod 5$, then $u_{p+1}$ is; if $u_n$ is divisible by a prime number $q$ and if $p \neq q$, then $u_{pn}/u_n$ is not divisible by $q$; if $u_n$ is divisible by a prime number $p \neq 2$, then $u_{pn}/u_n$ is divisible by $p$, but not by $p^2$; if $u_n$ is divisible by 4, then $u_{2n}/u_n$ is divisible by 2, but not by 4; if $u_n$ is divisible by 2 but not by 4, then $u_{2n}/u_n$ is divisible by 4, but not by 8. At the same time, some number-theoretic problems connected with Fibonacci numbers are extremely hard. For example, the question of whether the set of prime Fibonacci numbers is finite or not has not been solved (1984).

An important role in the theory of Fibonacci numbers is played by the number $\phi = (1+\sqrt 5)/2$, which is a root of the equation $x^2 - x - 1 = 0$. Thus Binet's formula $$ u_n = \frac{1}{\sqrt 5}(\phi^n - (-\phi)^{-n}) $$ holds; it implies that $u_n$ is the nearest integer to $\phi^n/\sqrt 5$, and that $$ \lim_{n \rightarrow \infty} \frac{u_{n+1}}{u_n} = \phi \ . $$

The Fibonacci numbers occupy a special position in the theory of continued fractions. In the continued-fraction expansion of $u_{n+1}/u_n$ all the partial quotients are ones and the number of them is not less than that of the incomplete quotients of the expansion of any other fraction with denominator less than $u_n$. In a certain sense the number $\phi$ is described by its approximating fractions $u_{n+1}/u_n$ in a "worst possible" way.

References

[1] B. Boncompagni, "Il Liber Abbaci di Leonardo Pisano" , Rome (1857)
[2] N.N. Vorob'ev, "Fibonacci numbers" , Moscow (1984) (In Russian). English translation by Mircea Martin: Birkhäuser (2002) ISBN 3764361352 Zbl 1014.11012
[3] V.E. Hoggatt, "Fibonacci and Lucas numbers" , Univ. Santa Clara (1969)
[4] U. (or A. Brousseau) Alfred, "An introduction to Fibonacci discovery" , San José, CA (1965)
[5] Fibonacci Quart. (1963-)

Comments

Let $P,Q$ be non-zero integers with $\mathrm{hcf}(P,Q) = 1$ and $D = P^2 - 4Q \neq 0$. A Lucas sequence, or a sequence of Lucas numbers, is defined by $U_0 = 0$, $U_1 = 1$ and the linear recurrence relation $$ U_{n+1} = P.U_n - Q.U_{n-1} \ . $$

Still more generally, a sequence $U_0,U_1,\ldots$ of complex numbers, i.e. a number-theoretic or arithmetic function, is said to be recurrent of order $r$ if there is a complex-valued function $f$ of $r$ variables such that $U_{n+r} = f(U_{n+r-1},\ldots, U_n)$, $n = 0,1,\ldots$. If $f$ is linear, $(U_n)$ is called a linear recurrent sequence. Both the Fibonacci and the Lucas numbers are linearly recurrent of order 2. Cf. Recurrence relation, Recursive sequence.

For some more results on Fibonacci numbers, Lucas numbers and recurrent sequences, as well as for their manifold applications, cf. also [a1].

References

[a1] A.N. Phillipou (ed.) G.E. Bergum (ed.) A.F. Horodam (ed.) , Fibonacci numbers and their applications , Reidel (1986)

Comments

The Fibonacci sequence may be extended to non-positive indices by setting $u_0 = 0$ and $u_{-n} = (-1)^n u_n$. The recurrence relation remains valid and Binet's formula still holds.

The Lucas numbers $(v_n)$ are defined by $v_0 = 2$, $v_1 = 1$ and the same recurrence relation $v_{n+1} = v_n + v_{n-1}$. They have a close connection with the Fibonacci numbers and similar addition and multiplication formulae, many of which may be derived from the formulae $$ v_n = \phi^n + (-\phi)^{-n} $$ and $$ \phi^n = \frac{v_n + u_n\sqrt5}{2} \ . $$ The Fibonacci and Lucas numbers are the Lucas sequences of the first and second kind respectively for the parameters $P=1$, $Q=1$.

For a translation of the Liber Abaci, see [b1]: the sequence is defined in Chapter 12.

References

[b1] Laurence Sigler, "Fibonacci's Liber Abaci: A Translation Into Modern English of Leonardo Pisano's Book of Calculation", Sources and Studies in the History of Mathematics and Physical Sciences, Springer (2003) ISBN 0-387-40737-5 Zbl 1038.01025
How to Cite This Entry:
Fibonacci numbers. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Fibonacci_numbers&oldid=12076
This article was adapted from an original article by N.N. Vorob'ev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article