Fibonacci numbers appear to have first arisen in perhaps 200 BC in work by the influential ancient scholar
Pingala (from India) on enumerating possible patterns of poetry formed from syllables of two lengths. The
Fibonacci sequence is named after Italian mathematician Leonardo of Pisa, known later by his nickname Fibonacci. His 1202 book
Liber Abaci (meaning "The Book of Calculation") introduced the sequence (as well as Hindu-Arabic numbers) to Western European mathematicians,
although the sequence had been described earlier in Indian mathematics.
These numbers can be computed with the aid of the Fibonacci matrix
The determinant of the above power matrix satisfy so called ‘‘Cassini formula’’ in honor of the
well-known 17th century astronomer Giovanni Domenico Cassini (1625--1712) who derived this formula:
Cassini was an Italian (naturalised French) mathematician and engineer. He was born in Perinaldo,
near Imperia, at that time in the County of Nice, part of the Savoyard state. Cassini is known for his
work in the fields of astronomy and engineering. In 1669, Cassini moved to France and through a grant from
Louis XIV of France helped to set up the Paris Observatory, which opened in 1671. Later, Cassini discovered
four satellites of the planet Saturn
and noted the division of the rings of Saturn; the Cassini Division was named after him.
Giovanni Domenico Cassini was also the first of his family to begin work on the project of creating a
topographic map of France.
The Fibonacci recurrence relation \( F_n = F_{n-1} + F_{n-2} \) can be expressed in matrix form:
Thus, we can compute the n-th Fibonacci number Fn by finding the n-1 power of matrix F
and multiplying it on the right by the column vector y1. We will learn later how to find any power
of a matrix avoiding tedious job.
In 1977, the Russian mathematician A.P. Stakhov introduced so-called Fibonacci p-numbers:
Note that the Qp-matrix is a square (p + 1)-by-(p + 1) matrix. It contains a
\( p\times p \) identity matrix bordered by the last
row of 0’s and the first column, which consists of 0’s bordered by 1’s. The integer powers of the
generalized Fibonacci matrix satisfy the Cassini identity
The generalized Fibonacci matrices allow us to develop the following application to coding theory.
Let us represent an initial message in the form of the square matrix M of the size
\( (p+1)\times (p+1) , \) where \( p=0,1,2,\ldots . \)
Let us choose the \( (p+1)\times (p+1) \) generalized Fibonacci matrix Qpn
as a coding matrix and its inverse Qp-n of the same size as a decoding matrix.
We will name a transformation \( {\bf M} \times {\bf Q}_p^n = {\bf E} \)
as Fibonacci coding and a transformation \( {\bf E} \times {\bf Q}_p^{-n} = {\bf M} \) as
Fibonacci decoding. We will name the matrix E as code matrix.
Example: Let us consider now the simplest Fibonacci coding/decoding method based on
application of the classical Fibonacci Q-matrix. Let us represent the initial message in the form of the following
\( 2\times 2 \) matrix
Then the code message \( E = e_1 , e_2 , e_3 , e_4 \) is sent to a channel.
The decoding of the code message E given with the inverse matrix is performed in the following manner.
The code message E that is represented in the matrix form is multiplied by the inverse matrix
The coding/decoding method considered above gives interesting possibility to detect and correct ‘‘errors’’ in the code
message E. The main idea of error detection and correction is based on the property of the matrix determinant given by
above formula. This mathematical relation plays an important role of ‘‘checking
relations’’ of the Fibonacci coding/decoding method.
The error correcting codes are used widely in modern computer systems and computer networks. The main idea of
modern algebraic error correcting codes consists in the following. A n-bit redundant code combination consists of
two groups of bits, k information bits and m checking bits formed from the information bits by modulo 2 addition
of certain groups of information bits. A minimal code distance (Hamming’s distance), which determines a code ability
to detect and correct errors of given multiplicity, is a principal parameter of redundant code.
Recurrences
We consider arbitrary difference equation with constant coefficients