In mathematics, the Lucas sequences and are certain constant-recursive integer sequences that satisfy the recurrence relation
where and are fixed integers. Any sequence satisfying this recurrence relation can be represented as a linear combination of the Lucas sequences and
More generally, Lucas sequences and represent sequences of polynomials in and with integer coefficients.
Famous examples of Lucas sequences include the Fibonacci numbers, Mersenne numbers, Pell numbers, Lucas numbers, Jacobsthal numbers, and a superset of Fermat numbers (see below). Lucas sequences are named after the French mathematician Édouard Lucas.
Given two integer parameters and , the Lucas sequences of the first kind and of the second kind are defined by the recurrence relations:
and
It is not hard to show that for ,
The above relations can be stated in matrix form as follows:
Initial terms of Lucas sequences and are given in the table:
The characteristic equation of the recurrence relation for Lucas sequences and is:
It has the discriminant and the roots:
Thus:
Note that the sequence and the sequence also satisfy the recurrence relation. However these might not be integer sequences.
When , a and b are distinct and one quickly verifies that
It follows that the terms of Lucas sequences can be expressed in terms of a and b as follows
The case occurs exactly when for some integer S so that . In this case one easily finds that
The ordinary generating functions are
When , the Lucas sequences and satisfy certain Pell equations:
The terms of Lucas sequences satisfy relations that are generalizations of those between Fibonacci numbers and Lucas numbers . For example:
Among the consequences is that is a multiple of , i.e., the sequence is a divisibility sequence. This implies, in particular, that can be prime only when n is prime. Another consequence is an analog of exponentiation by squaring that allows fast computation of for large values of n. Moreover, if , then is a strong divisibility sequence.
Other divisibility properties are as follows: [1]
The last fact generalizes Fermat's little theorem. These facts are used in the Lucas–Lehmer primality test. The converse of the last fact does not hold, as the converse of Fermat's little theorem does not hold. There exists a composite n relatively prime to D and dividing , where . Such a composite is called a Lucas pseudoprime.
A prime factor of a term in a Lucas sequence that does not divide any earlier term in the sequence is called primitive. Carmichael's theorem states that all but finitely many of the terms in a Lucas sequence have a primitive prime factor. [2] Indeed, Carmichael (1913) showed that if D is positive and n is not 1, 2 or 6, then has a primitive prime factor. In the case D is negative, a deep result of Bilu, Hanrot, Voutier and Mignotte [3] shows that if n > 30, then has a primitive prime factor and determines all cases has no primitive prime factor.
The Lucas sequences for some values of P and Q have specific names:
Some Lucas sequences have entries in the On-Line Encyclopedia of Integer Sequences:
−1 | 3 | OEIS: A214733 | |
1 | −1 | OEIS: A000045 | OEIS: A000032 |
1 | 1 | OEIS: A128834 | OEIS: A087204 |
1 | 2 | OEIS: A107920 | OEIS: A002249 |
2 | −1 | OEIS: A000129 | OEIS: A002203 |
2 | 1 | OEIS: A001477 | OEIS: A007395 |
2 | 2 | OEIS: A009545 | |
2 | 3 | OEIS: A088137 | |
2 | 4 | OEIS: A088138 | |
2 | 5 | OEIS: A045873 | |
3 | −5 | OEIS: A015523 | OEIS: A072263 |
3 | −4 | OEIS: A015521 | OEIS: A201455 |
3 | −3 | OEIS: A030195 | OEIS: A172012 |
3 | −2 | OEIS: A007482 | OEIS: A206776 |
3 | −1 | OEIS: A006190 | OEIS: A006497 |
3 | 1 | OEIS: A001906 | OEIS: A005248 |
3 | 2 | OEIS: A000225 | OEIS: A000051 |
3 | 5 | OEIS: A190959 | |
4 | −3 | OEIS: A015530 | OEIS: A080042 |
4 | −2 | OEIS: A090017 | |
4 | −1 | OEIS: A001076 | OEIS: A014448 |
4 | 1 | OEIS: A001353 | OEIS: A003500 |
4 | 2 | OEIS: A007070 | OEIS: A056236 |
4 | 3 | OEIS: A003462 | OEIS: A034472 |
4 | 4 | OEIS: A001787 | |
5 | −3 | OEIS: A015536 | |
5 | −2 | OEIS: A015535 | |
5 | −1 | OEIS: A052918 | OEIS: A087130 |
5 | 1 | OEIS: A004254 | OEIS: A003501 |
5 | 4 | OEIS: A002450 | OEIS: A052539 |
6 | 1 | OEIS: A001109 | OEIS: A003499 |
Sagemath implements and as lucas_number1()
and lucas_number2()
, respectively. [7]
In mathematics, the Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted Fn . The sequence commonly starts from 0 and 1, although some authors start the sequence from 1 and 1 or sometimes from 1 and 2. Starting from 0 and 1, the sequence begins
In mathematics, the Euler numbers are a sequence En of integers defined by the Taylor series expansion
In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Unlike an ordinary series, the formal power series is not required to converge: in fact, the generating function is not actually regarded as a function, and the "variable" remains an indeterminate. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general linear recurrence problem. One can generalize to formal power series in more than one indeterminate, to encode information about infinite multi-dimensional arrays of numbers.
In mathematics, the orthogonal group in dimension , denoted , is the group of distance-preserving transformations of a Euclidean space of dimension that preserve a fixed point, where the group operation is given by composing transformations. The orthogonal group is sometimes called the general orthogonal group, by analogy with the general linear group. Equivalently, it is the group of orthogonal matrices, where the group operation is given by matrix multiplication. The orthogonal group is an algebraic group and a Lie group. It is compact.
In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Catalan.
In number theory, a Wall–Sun–Sun prime or Fibonacci–Wieferich prime is a certain kind of prime number which is conjectured to exist, although none are known.
In number theory, the Mertens function is defined for all positive integers n as
In mathematics, the Heisenberg group, named after Werner Heisenberg, is the group of 3×3 upper triangular matrices of the form
In mathematics, the Fibonacci polynomials are a polynomial sequence which can be considered as a generalization of the Fibonacci numbers. The polynomials generated in a similar way from the Lucas numbers are called Lucas polynomials.
In mathematics, the determinant of an m×m skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries, a polynomial with integer coefficients that only depends on m. When m is odd, the polynomial is zero. When m is even, it is a nonzero polynomial of degree m/2, and is unique up to multiplication by ±1. The convention on skew-symmetric tridiagonal matrices, given below in the examples, then determines one specific polynomial, called the Pfaffian polynomial. The value of this polynomial, when applied to the entries of a skew-symmetric matrix, is called the Pfaffian of that matrix. The term Pfaffian was introduced by Cayley (1852), who indirectly named them after Johann Friedrich Pfaff.
Lucas pseudoprimes and Fibonacci pseudoprimes are composite integers that pass certain tests which all primes and very few composite numbers pass: in this case, criteria relative to some Lucas sequence.
In number theory, the nth Pisano period, written as π(n), is the period with which the sequence of Fibonacci numbers taken modulo n repeats. Pisano periods are named after Leonardo Pisano, better known as Fibonacci. The existence of periodic functions in Fibonacci numbers was noted by Joseph Louis Lagrange in 1774.
In mathematics, in particular number theory, an odd composite number N is a Somer–Lucas d-pseudoprime (with given d ≥ 1) if there exists a nondegenerate Lucas sequence with the discriminant such that and the rank appearance of N in the sequence U(P, Q) is
A Fibonacci prime is a Fibonacci number that is prime, a type of integer sequence prime.
In algebra, the Bring radical or ultraradical of a real number a is the unique real root of the polynomial
In mathematics, the Fibonacci numbers form a sequence defined recursively by:
A repeating decimal or recurring decimal is a decimal representation of a number whose digits are periodic and the infinitely repeated portion is not zero. It can be shown that a number is rational if and only if its decimal representation is repeating or terminating. For example, the decimal representation of 1/3 becomes periodic just after the decimal point, repeating the single digit "3" forever, i.e. 0.333.... A more complicated example is 3227/555, whose decimal becomes periodic at the second digit following the decimal point and then repeats the sequence "144" forever, i.e. 5.8144144144.... At present, there is no single universally accepted notation or phrasing for repeating decimals. Another example of this is 593/53, which becomes periodic after the decimal point, repeating the 13-digit pattern "1886792452830" forever, i.e. 11.18867924528301886792452830....
Common integrals in quantum field theory are all variations and generalizations of Gaussian integrals to the complex plane and to multiple dimensions. Other integrals can be approximated by versions of the Gaussian integral. Fourier integrals are also considered.
In mathematics and theoretical computer science, a constant-recursive sequence is an infinite sequence of numbers in which each number in the sequence is equal to a fixed linear combination of one or more of its immediate predecessors. The concept is variously known as a linear recurrence sequence, linear-recursive sequence, linear-recurrent sequence, a C-finite sequence, or a solution to a linear recurrence with constant coefficients.
In mathematics, a transformation of a sequence's generating function provides a method of converting the generating function for one sequence into a generating function enumerating another. These transformations typically involve integral formulas applied to a sequence generating function or weighted sums over the higher-order derivatives of these functions.