Padovan Sequence

The Padovan sequence is the integer sequence defined by the recurrence relation

(1)

for , with the initial conditions . The terms of the Padovan sequence are known as Padovan numbers. This is the same recurrence relation as for the Perrin sequence, but with different initial conditions.

The recurrence relation can be solved explicitly, giving

(2)

where , , and are the three roots of

(3)

Another form of the solution is

(4)

where , , and are the three roots of

(5)

The first few terms starting at are 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, ... (OEIS A000931).

Using shifted versions of the tribonacci sequence and Padovan sequence, Slavík and Vestenická (2026) count, respectively, tilings of an -board by squares, dominoes, and trominoes, and tilings by dominoes and trominoes. Denote these shifted sequences by and , respectively, with , , and , . Then the convolution identity is

(6)

for .

Padovan sequence numbers that are prime are known as Padovan primes.

The ratio

(7)

where is the unique positive real root of , is called the plastic constant.

Padovan numbers also count the copies in a pentagonal substitution system associated with the plastic constant (Pegg 2026). Each largest copy is replaced by two copies with relative linear scale factors and . Starting with a single seed, the total after replacements of all largest copies is . The stages illustrated above contain , , and copies. These counts describe substitution copies and do not assert a tiling by the seed pentagon.

A matrix analogous to the Fibonacci Q-matrix exists for Padovan numbers. Defining

(8)

for nonnegative integer , the powers of give

(9)

(J. Lien, pers. comm., Mar. 11, 2005), where the recurrence relation is extended backwards to give , , , and .