Namespaces
Variants
Actions

Difference between revisions of "Fibonacci numbers"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(LaTeX)
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}}
 +
The elements of the sequence $u_1,u_2,\ldots$ 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
 
 
 
<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>
 
 
 
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
 
 
 
<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>
 
 
 
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">[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>
  
  
  
 
====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
+
Let $P,Q$ be non-zero integers with $\mathrm{hcf}(P,Q) = 1$ and $D = P^2 - 4Q$. A ''Lucas sequence'', or a sequence of Lucas numbers, is defined by $U_0 = 0$, $U_1 = 1$ and the linear recurrence relation
 
+
$$
<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>
+
U_{n+1} = P.U_n - Q.U_{n-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.
+
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 [[#References|[a1]]].
 
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">[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>

Revision as of 17:20, 29 December 2014

The elements of the sequence $u_1,u_2,\ldots$ 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, "Illiber Abbaci di Leonardo Pisano" , Rome (1857)
[2] N.N. Vorob'ev, "Fibonacci numbers" , Moscow (1984) (In Russian)
[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$. 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)
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