View source for Padovan sequence

{{short description|Sequence of integers}}
In [[number theory]], the '''Padovan sequence''' is the [[sequence]] of [[integer]]s ''P''(''n'') defined<ref name="ps">{{MathWorld|urlname=PadovanSequence|title=Padovan Sequence}}.</ref> by the initial values

:<math>P(0)=P(1)=P(2)=1,</math>

and the [[recurrence relation]]

:<math>P(n)=P(n-2)+P(n-3).</math>

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}}

[[Image:Padovan triangles (1).png|thumb|350px|Spiral of equilateral triangles with side lengths which follow the Padovan sequence.]]
The Padovan sequence is named after [[Richard Padovan]] who attributed its discovery to [[Netherlands|Dutch]] architect [[Hans van der Laan]] in his 1994 essay ''Dom. Hans van der Laan : Modern Primitive''.<ref name=dhdl>Richard Padovan. ''Dom Hans van der Laan: modern primitive'': Architectura & Natura Press, {{ISBN|9789071570407}}.</ref> The sequence was described by [[Ian Stewart (mathematician)|Ian Stewart]] in his [[Scientific American]] column ''Mathematical Recreations'' in June 1996.<ref>Ian Stewart, [https://web.archive.org/web/20060131123213/http://members.fortunecity.com/templarser/padovan.html ''Tales of a Neglected Number''], ''Scientific American'', No. 6, June 1996, pp. 92-93.</ref> He also writes about it in one of his books, "Math Hysteria: Fun Games With Mathematics".
<ref name=stewart>{{citation
 | author = Ian Stewart 
 | author-link = Ian Stewart (mathematician)
 | isbn = 978-0-19-861336-7
 | page = 87
 | publisher = Oxford University Press
 | title = Math hysteria: fun and games with mathematics
 | year = 2004}}.</ref>

''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
:<math>P(n)=P(n-1)+P(n-5)</math>

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 <math>P(m)</math> by <math>P(m - 2) + P(m - 3)</math>

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

:<math>\mathrm{Perrin}(n)=P(n+1)+P(n-10).\,</math>

==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

:<math>P(m) = P(m+3) - P(m+1),</math>

Starting with ''m'' = −1 and working backwards, we extend ''P''(''m'') to negative indices:

:{| class="wikitable" style="text-align:right"
|-
| ''P''<sub>−20</sub>
| ''P''<sub>−19</sub>
| ''P''<sub>−18</sub>
| ''P''<sub>−17</sub>
| ''P''<sub>−16</sub> 
| ''P''<sub>−15</sub>
| ''P''<sub>−14</sub>
| ''P''<sub>−13</sub>
| ''P''<sub>−12</sub>
| ''P''<sub>−11</sub>
| ''P''<sub>−10</sub>
| ''P''<sub>−9</sub>
| ''P''<sub>−8</sub>
| ''P''<sub>−7</sub>
| ''P''<sub>−6</sub>
| ''P''<sub>−5</sub>
| ''P''<sub>−4</sub>
| ''P''<sub>−3</sub>
| ''P''<sub>−2</sub>
| ''P''<sub>−1</sub>
| ''P''<sub>0</sub>
| ''P''<sub>1</sub>
| ''P''<sub>2</sub>
|-
| 7
| −7
| 4
| 0
| −3
| 4
| −3
| 1
| 1
| −2
| 2
| −1
| 0
| 1
| −1
| 1
| 0
| 0
| 1
| 0
| 1
| 1
| 1
|-
|}

==Sums of terms==
The sum of the first ''n'' terms in the Padovan sequence is 2 less than ''P''(''n''&nbsp;+&nbsp;5) i.e.

:<math>\sum_{m=0}^n P(m)=P(n+5)-2.</math>

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

:<math>\sum_{m=0}^n P(2m)=P(2n+3)-1</math> {{OEIS2C|A077855}}

:<math>\sum_{m=0}^n P(2m+1)=P(2n+4)-1</math>

:<math>\sum_{m=0}^n P(3m)=P(3n+2)</math> {{OEIS2C|A034943}}

:<math>\sum_{m=0}^n P(3m+1)=P(3n+3)-1</math>

:<math>\sum_{m=0}^n P(3m+2)=P(3n+4)-1</math>

:<math>\sum_{m=0}^n P(5m)=P(5n+1).</math> {{OEIS2C|A012772}}

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

:<math>\sum_{m=0}^n P(m)^2=P(n+2)^2-P(n-1)^2-P(n-3)^2</math>

:<math>\sum_{m=0}^n P(m)^2P(m+1)=P(n)P(n+1)P(n+2)</math>

:<math>\sum_{m=0}^n P(m)P(m+2)=P(n+2)P(n+3)-1.</math>

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

:<math>P(n)^2-P(n+1)P(n-1)=P(-n-7).\,</math>

The Padovan sequence is related to sums of [[binomial coefficient]]s by the following identity:

:<math>P(k-2)=\sum_{2m+n=k}{m \choose n}=\sum_{m=\lceil k/3\rceil}^{\lfloor k/2\rfloor}{m \choose k-2m}.</math>

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

:<math>{6 \choose 0}+{5 \choose 2}+{4 \choose 4}=1+10+1=12=P(10).\,</math>

==Binet-like formula==
[[File:Triangles in ratio of the plastic number in a three armed counter clockwise spiral.svg|thumb|Triangles with sides in ratio of 1/{{math|''ρ''}} form a closed spiral]]

The Padovan sequence numbers can be written in terms of powers of the roots of the equation<ref name="ps"/>

:<math> x^3 -x -1 = 0.\,</math>

This equation has 3 roots;  one real root ''p'' (known as the [[plastic number]]) and two complex conjugate roots ''q'' and ''r''.<ref>Richard Padovan, [http://www.nexusjournal.com/conferences/N2002-Padovan.html "Dom Hans Van Der Laan and the Plastic Number"], pp. 181-193 in Nexus IV: Architecture and Mathematics, eds. Kim Williams and Jose Francisco Rodrigues, Fucecchio (Florence): Kim Williams Books, 2002.</ref> Given these three roots, the Padovan sequence can be expressed by a formula involving ''p'', ''q'' and ''r'':

:<math>P\left(n\right) = a p^n + b q^n + c r^n</math>

where ''a'', ''b'' and ''c'' are constants.<ref name="ps"/>

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 <math>P\left(n\right) - a {p^n}</math> tends to zero.

<!-- it would be nice to use a p^n below instead of p^(n-1)/s, but it would be nice to express that a as a cubic root as well. Failing that, I prefer the older formula. ~~~~ -->
For all <math>n \ge 0</math>, P(n) is the integer closest to <math>  \frac {p^{n-1}} {s}</math>, 
where ''s'' = ''p''/''a'' = 1.0453567932525329623... is the only real root of ''s''<sup>3</sup>&nbsp;&minus;&nbsp;2''s''<sup>2</sup>&nbsp;+&nbsp;23''s''&nbsp;&minus;&nbsp;23&nbsp;=&nbsp;0.   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 sequence and the [[Perrin sequence]] as the [[golden ratio]] does to the [[Fibonacci sequence]].
<!-- ... and to all Fibonacci-type sequences. -->

==Combinatorial interpretations==
* ''P''(''n'') is the number of ways of writing ''n''&nbsp;+&nbsp;2 as an ordered sum in which each term is either 2 or 3 (i.e. the number of [[composition (number theory)|compositions]] of ''n''&nbsp;+&nbsp;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''&nbsp;&minus;&nbsp;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 odd and greater than 1 is equal to ''P''(''n''&nbsp;&minus;&nbsp;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 writing ''n'' as an ordered sum in which each term is congruent to 2 mod 3 is equal to ''P''(''n''&nbsp;&minus;&nbsp;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

:<math>G(P(n);x)=\frac{1+x}{1-x^2-x^3}.</math>

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

:<math>\sum_{n=0}^{\infty}\frac{P(n)}{2^n} = \frac{12}{5}.</math>
:<math>\sum_{n=0}^\infty \frac{P(n)}{\alpha^n} = \frac{\alpha^2(\alpha+1)}{\alpha^3-\alpha-1}.</math>

== 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 L-system ==

If we define the following simple grammar:

:     '''variables''' :   A  B  C
:     '''constants''' :   none
:     '''start'''     :   A
:     '''rules'''     :   (A &rarr; B), (B &rarr; C), (C &rarr; 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''th
string, you have ''P''(''n''&nbsp;&minus;&nbsp;5) ''A''s, ''P''(''n''&nbsp;&minus;&nbsp;3) ''B''s and ''P''(''n''&nbsp;&minus;&nbsp;4) ''C''s.  The count of ''BB'' pairs, ''AA'' pairs
and ''CC'' pairs are also Padovan numbers.

== Cuboid spiral ==
{{main|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 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''<ref>Erv Wilson (1993), [http://www.anaphoria.com/meruone.pdf ''Scales of Mt. Meru'']</ref> observed certain diagonals in [[Pascal's triangle]] (see diagram) and drew them on paper in 1993. The Padovan numbers were discovered in 1994. Paul Barry (2004) showed that these diagonals generate the Padovan sequence by summing the diagonal numbers.{{cn|date=March 2019}}

[[File:Padovan Sequence 2.jpg|500x500px]]

==References==
{{Reflist}}
* Ian Stewart, A Guide to Computer Dating (Feedback), Scientific American, Vol. 275, No. 5, November 1996, Pg. 118.

==External links==
*{{OEIS el|sequencenumber=A000931|name=Padovan sequence|formalname=Padovan sequence (or Padovan numbers): a(n) = a(n-2) + a(n-3) with a(0)=1, a(1)=a(2)=0}}
*[https://web.archive.org/web/20070216024906/http://www.plenilune.pwp.blueyonder.co.uk/fibonacci-calculator.asp A Padovan sequence calculator]

[[Category:Integer sequences]]
[[Category:Recurrence relations]]