![]() | ||
The Padovan sequence is the sequence of integers P(n) defined by the initial values
Contents
- Recurrence relations
- Extension to negative parameters
- Sums of terms
- Other identities
- Binet like formula
- Combinatorial interpretations
- Generating function
- Generalizations
- Padovan prime
- Padovan L system
- Cuboid spiral
- Pascals Triangle
- References
and the recurrence relation
The first few values of P(n) are
1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, ... (sequence A000931 in the OEIS)The Padovan sequence is named after Richard Padovan who attributed its discovery to Dutch architect Hans van der Laan in his 1994 essay Dom. Hans van der Laan : Modern Primitive. The sequence was described by Ian Stewart in his Scientific American column Mathematical Recreations in June 1996. He also writes about it in one of his books, "Math Hysteria: Fun Games With Mathematics".
The above definition is the one given by Ian Stewart and by MathWorld. Other sources may start the sequence at a different place, in which case some of the identities in this article must be adjusted with appropriate offsets.
Recurrence relations
In the spiral, each triangle shares a side with two others giving a visual proof that the Padovan sequence also satisfies the recurrence relation
Starting from this, the defining recurrence and other recurrences as they are discovered, one can create an infinite number of further recurrences by repeatedly replacing
The Perrin sequence satisfies the same recurrence relations as the Padovan sequence, although it has different initial values. This is a property of recurrence relations.
The Perrin sequence can be obtained from the Padovan sequence by the following formula:
Extension to negative parameters
As with any sequence defined by a recurrence relation, Padovan numbers P(m) for m<0 can be defined by rewriting the recurrence relation as
Starting with m = −1 and working backwards, we extend P(m) to negative indices:
Sums of terms
The sum of the first n terms in the Padovan sequence is 2 less than P(n + 5) i.e.
Sums of alternate terms, sums of every third term and sums of every fifth term are also related to other terms in the sequence:
Sums involving products of terms in the Padovan sequence satisfy the following identities:
Other identities
The Padovan sequence also satisfies the identity
The Padovan sequence is related to sums of binomial coefficients by the following identity:
For example, for k = 12, the values for the pair (m, n) with 2m + n = 12 which give non-zero binomial coefficients are (6, 0), (5, 2) and (4, 4), and:
Binet-like formula
The Padovan sequence numbers can be written in terms of powers of the roots of the equation
This equation has 3 roots; one real root p (known as the plastic number) and two complex conjugate roots q and r. Given these three roots, the Padovan sequence can be expressed by a formula involving p,q and r:
where a, b and c are constants.
Since the magnitudes of the complex roots q and r are both less than 1 (and hence p is a Pisot–Vijayaraghavan number), the powers of these roots approach 0 for large n, and
For all
Combinatorial interpretations
Generating function
The generating function of the Padovan sequence is
This can be used to prove identities involving products of the Padovan sequence with geometric terms, such as:
Generalizations
In a similar way to the Fibonacci numbers that can be generalized to a set of polynomials called the Fibonacci polynomials, the Padovan sequence numbers can be generalized to yield the Padovan polynomials.
Padovan prime
A Padovan prime is P(n) that is prime. The first few Padovan primes are
2, 3, 5, 7, 37, 151, 3329, 23833, .... (sequence A100891 in the OEIS)Padovan L-system
If we define the following simple grammar:
variables : A B Cconstants : nonestart : Arules : (A → B), (B → C), (C → AB)then this Lindenmayer system or L-system produces the following sequence of strings:
n = 0 : An = 1 : Bn = 2 : Cn = 3 : ABn = 4 : BCn = 5 : CABn = 6 : ABBCn = 7 : BCCABn = 8 : CABABBCand if we count the length of each string, we obtain the Padovan sequence of numbers:
1 1 1 2 2 3 4 5 ...Also, if you count the number of As, Bs and Cs in each string, then for the nth string, you have P(n − 5) As, P(n − 3) Bs and P(n − 4) Cs. The count of BB pairs, AA pairs and CC pairs are also Padovan numbers.
Cuboid spiral
A spiral can be formed based on connecting the corners of a set of 3-dimensional cuboids. This is the Padovan cuboid spiral. Successive sides of this spiral have lengths that are the Padovan sequence numbers multiplied by the square root of 2.
Pascal's Triangle
Erv Wilson in his paper The Scales of Mt. Meru discovered the Padovan sequence in Pascal's Triangle by summing the diagonal numbers (see diagram). Correction, Erv Wilson noticed these diagonals and drew them on paper in 1993, yet the Padovan numbers were not discovered until 1994. Tony Foster (2016) actually defined these diagonals as being related to the Padovan sequence. Below is his chart.