Fibonacci numbers

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