- Padovan sequence
The

**Padovan sequence**is thesequence ofinteger s "P"("n") defined by the initial values:$P(0)=P(1)=P(2)=1,$

and the

recurrence relation :$P(n)=P(n-2)+P(n-3).$

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, ... OEIS|id=A000931

The Padovan sequence is named after

Richard Padovan who attributed its discovery to Dutch architectHans van der Laan in his 1994 essay "Dom. Hans van der Laan : Modern Primitive". The sequence was described by Ian Stewart in hisScientific American column "Mathematical Recreations" in June 1996."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**The Padovan sequence also satisfies the recurrence relations

:$P(n)=P(n-1)+P(n-5)$:$P(n)=P(n-2)+P(n-4)+P(n-8)$:$P(n)=2P(n-2)-P(n-7)$:$P(n)=P(n-3)+P(n-4)+P(n-5)$:$P(n)=P(n-3)+P(n-5)+P(n-7)+P(n-8)+P(n-9)$:$P(n)=P(n-4)+P(n-5)+P(n-6)+P(n-7)+P(n-8)$:$P(n)=4P(n-5)+P(n-14).$

The Perrin 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:

:$mathrm\{Perrin\}(n)=P(n+1)+P(n-10).,$

**Extension to negative parameters**The Padovan sequence can be extended to negative parameters using the recurrence relation

:$P(-n)\; =\; P(-n+3)\; -\; P(-n+1).$

(this is similar to the extension of the

Fibonacci number s to negative index values). Extending "P"("n") to negative parameters gives the values:..., −7, 4, 0, −3, 4, −3, 1, 1, −2, 2, −1, 0, 1, −1, 1, 0, 0, 1, 0, 1, 1, 1, ...

**ums of terms**The sum of the first "n" terms in the Padovan sequence is 2 less than "P"("n" + 5) i.e.

:$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:

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

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

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

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

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

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

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

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

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

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

**Other identities**The Padovan sequence also satisfies the identity

:$P(n)^2-P(n+1)P(n-1)=P(-n-7).,$

The Padovan sequence is related to sums of

binomial coefficient s by the following identity::$sum\_\{2m+n=k\}\{m\; choose\; n\}=P(k-2).$

For example, for "k" = 12, the values for the pair ("m", "n") with 2"m" + "n" = 12 which give non-zero binomial coefficients are (6, 0), (5, 2) and (4, 4), and:

:$\{6\; choose\; 0\}+\{5\; choose\; 2\}+\{4\; choose\; 4\}=1+10+1=12=P(10).,$

**Binet-like formula**The Padovan sequence numbers can be written in terms of powers of the roots of the equation

:$x^3\; -x\; -1\; =\; 0.,$

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 analogue of theFibonacci sequence Binet formula is:$Pleft(n\; ight)\; =\; frac\; \{p^n\}\; \{left(3p^2-1\; ight)\}\; +\; frac\; \{q^n\}\; \{left(3q^2-1\; ight)\}+\; frac\; \{r^n\}\; \{left(3r^2-1\; ight)\}.$

Since the magnitudes of the complex roots "q" and "r" are both less than 1, the powers of these roots approach 0 for large "n". For large "n" the formula reduces to

:$Pleft(n\; ight)\; approx\; frac\; \{p^n\}\; \{left(3p^2-1\; ight)\}\; =\; frac\; \{p^n\}\; \{s\}approx\; frac\; \{p^n\}\; \{4.264632...\}.$

where s is the only real root of $s^3-3\; s^2-23=0$. This formula can be used to quickly calculate values of the Padovan sequence for large n. The ratio of successive terms in the Padovan sequence approaches "p", which has a value of approximately 1.324718. This constant bears the same relationship to the Padovan sequenceand the

Perrin sequence as thegolden ratio does to the Fibonacci sequence.**Combinatorial interpretations*** "P"("n") is the number of ways of writing "n" + 2 as an ordered sum in which each term is either 2 or 3 (i.e. the number of compositions of "n" + 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 writing "n" as an ordered sum in which no term is 2 is "P"(2"n" − 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 writing "n" as a palindromic ordered sum in which no term is 2 is "P"("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 writing "n" as an ordered sum in which each term is congruent to 2 mod 3 is equal to "P"("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

**Generating function**The

generating function of the Padovan sequence is:$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 with geometric terms, such as:

:$sum\_\{m=0\}^\{infty\}frac\{P(n)\}\{2^n\}\; =\; frac\{12\}\{5\}.$

**Generalizations**In a similar way to the

Fibonacci numbers that can be generalized to a set of polynomialscalled theFibonacci polynomials , the Padovan sequence numbers can be generalized toyield thePadovan polynomials .**Padovan prime**A

**Padovan prime**is "P"("n") that is prime. The first few Padovan primes OEIS2C|id=A100891 are:2, 3, 5, 7, 37, 151, 3329, 23833, ....

**Padovan L-system**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 or

L-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 sequence of numbers:

: 1 1 1 2 2 3 4 5 ...

Also, if you count the number of "A"s, "B"s and "C"s in each string, then for the "n"thstring, you have "P"("n" − 5) "A"s, "P"("n" − 3) "B"s and "P"("n" − 4) "C"s. The count of "BB" pairs, "AA" pairsand "CC" pairs are also Padovan numbers.

**Padovan 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 arethe Padovan sequence numbers multiplied by the square root of 2.**External links*** [

*http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000931 Padovan sequence (sequence A000931)*] inOEIS

*MathWorld|urlname=PadovanSequence|title=Padovan Sequence

* [*http://www.nexusjournal.com/conferences/N2002-Padovan.html "Dom Hans Van Der Laan And The Plastic Number"*] by Richard Padovan

* [*http://members.fortunecity.com/templarser/padovan.html "Tales of a Neglected Number"*] by Ian Stewart

* [*http://www.plenilune.pwp.blueyonder.co.uk/fibonacci-calculator.asp A Padovan Sequence Calculator can be found here.*]

*Wikimedia Foundation.
2010.*