Innumber theory, thePadovan sequence is thesequence of integersP(n) defined^[1] by the initial values:

$${\displaystyle P(0)=P(1)=P(2)=1,}$$

and therecurrence relation

$${\displaystyle P(n)=P(n-2)+P(n-3).}$$

The first few values ofP(n) are

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, ... (sequenceA000931 in theOEIS)

The Padovan sequence is named afterRichard Padovan who attributed its discovery toDutch architectHans van der Laan in his 1994 essayDom. Hans van der Laan: Modern Primitive.^[2] Thesequence was described byIan Stewart in hisScientific American columnMathematical Recreations in June 1996.^[3] He also writes about it in one of his books, "Math Hysteria: Fun Games With Mathematics".^[4]

The above definition is the one given by Ian Stewart and byMathWorld. 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.

In the spiral, eachtriangle shares a side with two others giving a visual proof that the Padovan sequence also satisfies the recurrence relation

${\displaystyle P(n)=P(n-1)+P(n-5)}$

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${\displaystyle P(m)}$ by${\displaystyle P(m-2)+P(m-3)}$

ThePerrin sequence satisfies the same recurrence relations as the Padovan sequence, although it has different initial values.

The Perrin sequence can be obtained from the Padovan sequence by the following formula:

${\displaystyle \mathrm{P}\mathrm{e}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{n}(n)=P(n+1)+P(n-10).}$

As with any sequence defined by a recurrence relation, Padovan numbersP(m) form<0 can be defined by rewriting the recurrence relation as

${\displaystyle P(m)=P(m+3)-P(m+1),}$

Starting withm = −1 and working backwards, we extendP(m) to negative indices:

P−20

P−19

P−18

P−17

P−16

P−15

P−14

P−13

P−12

P−11

P−10

P−9

P−8

P−7

P−6

P−5

P−4

P−3

P−2

P−1

P0

P1

P2

7

−7

4

0

−3

4

−3

1

1

−2

2

−1

0

1

−1

1

0

0

1

0

1

1

1

The sum of the firstn terms in the Padovan sequence is 2 less thanP(n + 5), i.e.

${\displaystyle \sum _{m=0}^{n}P(m)=P(n+5)-2.}$

Sums of alternate terms, sums of every third term and sums of every fifth term are also related to other terms in the sequence:

${\displaystyle \sum _{m=0}^{n}P(2m)=P(2n+3)-1}$OEIS: A077855

${\displaystyle \sum _{m=0}^{n}P(2m+1)=P(2n+4)-1}$

${\displaystyle \sum _{m=0}^{n}P(3m)=P(3n+2)}$OEIS: A034943

${\displaystyle \sum _{m=0}^{n}P(3m+1)=P(3n+3)-1}$

${\displaystyle \sum _{m=0}^{n}P(3m+2)=P(3n+4)-1}$

${\displaystyle \sum _{m=0}^{n}P(5m)=P(5n+1).}$OEIS: A012772

Sums involving products of terms in the Padovan sequence satisfy the following identities:

${\displaystyle \sum _{m=0}^{n}P(m{)}^2=P(n+2{)}^2-P(n-1{)}^2-P(n-3{)}^2}$

${\displaystyle \sum _{m=0}^{n}P(m{)}^{2}P(m+1)=P(n)P(n+1)P(n+2)}$

${\displaystyle \sum _{m=0}^{n}P(m)P(m+2)=P(n+2)P(n+3)-1.}$

The Padovan sequence also satisfies the identity

${\displaystyle P(n{)}^2-P(n+1)P(n-1)=P(-n-7).}$

The Padovan sequence is related to sums ofbinomial coefficients by the following identity:

${\displaystyle P(k-2)=\sum _{2m+n=k}(\genfrac{}{}{0ex}{}{m}{n})=\sum _{m=\lceil k/3\rceil }^{\lfloor k/2\rfloor }(\genfrac{}{}{0ex}{}{m}{k-2m}).}$

For example, fork = 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:

${\displaystyle (\genfrac{}{}{0ex}{}{6}{0})+(\genfrac{}{}{0ex}{}{5}{2})+(\genfrac{}{}{0ex}{}{4}{4})=1+10+1=12=P(10).}$

The Padovan sequence numbers can be written in terms of powers of theroots of the equation^[1]

${\displaystyle x^3-x-1=0.}$

This equation has 3 roots; onereal rootp (known as theplastic ratio) and twocomplex conjugate rootsq andr.^[5] Given these three roots, the Padovan sequence can be expressed by a formula involvingp,q andr :

${\displaystyle P(n)=a{p}^n+b{q}^n+c{r}^n}$

wherea,b andc are constants.^[1]

Since theabsolute values of thecomplex rootsq andr are both less than 1 (and hencep is aPisot–Vijayaraghavan number), the powers of these rootsapproach 0 for largen, and${\displaystyle P(n)-a{p}^n}$ tends to zero.

For all${\displaystyle n\ge 0}$,P(n) is theinteger closest to${\displaystyle \frac{p^5}{2p+3}{p}^n}$. Indeed,${\displaystyle \frac{p^5}{2p+3}}$ is the value of constanta above, whileb andc are obtained by replacingp withq andr, respectively.

The ratio of successive terms in the Padovan sequence approachesp, which has a value of approximately 1.324718. This constant bears the same relationship to the Padovan sequence and thePerrin sequence as thegolden ratio does to theFibonacci sequence.

• P(n) is the number of ways of writingn + 2 as an ordered sum in which each term is either 2 or 3 (i.e. the number ofcompositions ofn + 2 in which each term is either 2 or 3). For example,P(6) = 4, and there are 4 ways to write 8 as an ordered sum of 2s and 3s:

2 + 2 + 2 + 2  ; 2 + 3 + 3  ; 3 + 2 + 3  ; 3 + 3 + 2

• The number of ways of writingn as an ordered sum in which no term is 2 isP(2n − 2). For example,P(6) = 4, and there are 4 ways to write 4 as an ordered sum in which no term is 2:

4  ; 1 + 3  ; 3 + 1  ; 1 + 1 + 1 + 1

• The number of ways of writingn as a palindromic ordered sum in which no term is 2 isP(n). For example,P(6) = 4, and there are 4 ways to write 6 as a palindromic ordered sum in which no term is 2:

6  ; 3 + 3  ; 1 + 4 + 1  ; 1 + 1 + 1 + 1 + 1 + 1

• The number of ways of writingn as an ordered sum in which each term isodd and greater than 1 is equal toP(n − 5). For example,P(6) = 4, and there are 4 ways to write 11 as an ordered sum in which each term is odd and greater than 1:

11 ; 5 + 3 + 3 ; 3 + 5 + 3 ; 3 + 3 + 5

• The number of ways of writingn as an ordered sum in which each term iscongruent to 2 mod 3 is equal toP(n − 4). For example,P(6) = 4, and there are 4 ways to write 10 as an ordered sum in which each term is congruent to 2 mod 3:

8 + 2  ; 2 + 8  ; 5 + 5  ; 2 + 2 + 2 + 2 + 2

Thegenerating function of the Padovan sequence is

${\displaystyle G(P(n);x)=\frac{1+x}{1-x^2-x^3}.}$

This can be used to prove identities involving products of the Padovan sequence withgeometric terms, such as:

${\displaystyle \sum _{n=0}^{\mathrm{\infty }}\frac{P(n)}{2^n}=\frac{12}{5}.}$

${\displaystyle \sum _{n=0}^{\mathrm{\infty }}\frac{P(n)}{{\alpha }^n}=\frac{{\alpha }^2(\alpha +1)}{{\alpha }^3-\alpha -1}.}$

In a similar way to theFibonacci numbers that can be generalized to a set ofpolynomialscalled theFibonacci polynomials, the Padovan sequence numbers can be generalized toyield thePadovan polynomials.

If we define the following simple grammar:

variables : A B C

constants : none

start  : A

rules  : (A → B), (B → C), (C → AB)

then this Lindenmayer system orL-system produces the following sequence of strings:

n = 0 : A

n = 1 : B

n = 2 : C

n = 3 : AB

n = 4 : BC

n = 5 : CAB

n = 6 : ABBC

n = 7 : BCCAB

n = 8 : CABABBC

and if we count the length of each string, we obtain the Padovan numbers:

1, 1, 1, 2, 2, 3, 4, 5, ...

Also, if you count the number ofAs,Bs andCs in each string, then for thenthstring, you haveP(n − 5)As,P(n − 3)Bs andP(n − 4)Cs. The count ofBB pairsandCC pairs are also Padovan numbers.

A spiral can be formed based on connecting the corners of a set of 3-dimensionalcuboids.This is thePadovan cuboid spiral. Successive sides of this spiral have lengths that arethe Padovan numbers multiplied by thesquare root of 2.

Erv Wilson in his paperThe Scales of Mt. Meru^[6] observed certain diagonals inPascal's triangle (see diagram) and drew them on paper in 1993. The Padovan numbers were discovered in 1994. Paul Barry (2004) observed that these diagonals generate the Padovan sequence by summing the diagonal numbers.^[7]

• Ian Stewart, A Guide to Computer Dating (Feedback), Scientific American, Vol. 275, No. 5, November 1996, Pg. 118.

• OEISsequence A000931 (Padovan sequence)
• A Padovan sequence calculator

• Integer sequences
• Recurrence relations

• Webarchive template wayback links
• Articles with short description
• Short description matches Wikidata