Padovan sequence 2161709 206673825 2008-04-19T11:47:22Z 212.115.231.130 The '''Padovan sequence''' is the [[sequence]] of [[integer]]s ''P''(''n'') defined 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.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''. The sequence was described by [[Ian Stewart (mathematician)|Ian Stewart]] in his [[Scientific 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 :<math>P(n)=P(n-1)+P(n-5)</math> :<math>P(n)=P(n-2)+P(n-4)+P(n-8)</math> :<math>P(n)=2P(n-2)-P(n-7)</math> :<math>P(n)=P(n-3)+P(n-4)+P(n-5)</math> :<math>P(n)=P(n-3)+P(n-5)+P(n-7)+P(n-8)+P(n-9)</math> :<math>P(n)=P(n-4)+P(n-5)+P(n-6)+P(n-7)+P(n-8)</math> :<math>P(n)=4P(n-5)+P(n-14).</math> The [[Perrin pseudoprime|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: :<math>\mathrm{Perrin}(n)=P(n+1)+P(n-10).\,</math> ==Extension to negative parameters== The Padovan sequence can be extended to negative parameters using the recurrence relation :<math>P(-n) = P(-n+3) - P(-n+1).</math> (this is similar to the extension of the [[Fibonacci number]]s to negative index values). Extending ''P''(''n'') to negative parameters gives the values :..., &minus;7, 4, 0, &minus;3, 4, &minus;3, 1, 1, &minus;2, 2, &minus;1, 0, 1, &minus;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> :<math>\sum_{m=0}^n P(2m+1)=P(2n+4)-1</math> :<math>\sum_{m=0}^n P(3m)=P(3n+2)</math> :<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> 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> \sum_{2m+n=k}{m \choose n}=P(k-2).</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== The Padovan sequence numbers can be written in terms of powers of the roots of the equation :<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''. Given these three roots, the Padovan sequence analogue of the [[Fibonacci sequence]] Binet formula is :<math>P\left(n\right) = \frac {p^n} {\left(3p^2-1\right)} + \frac {q^n} {\left(3q^2-1\right)}+ \frac {r^n} {\left(3r^2-1\right)}. </math> 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 :<math>P\left(n\right) \approx \frac {p^n} {\left(3p^2-1\right)} = \frac {p^n} {s}\approx \frac {p^n} {4.264632...}.</math> where s is the only real root of <math>s^3-3 s^2-23=0</math>. 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 sequence and the [[Perrin sequence]] as the [[golden ratio]] does to the Fibonacci sequence. ==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 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_{m=0}^{\infty}\frac{P(n)}{2^n} = \frac{12}{5}.</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 prime == A '''Padovan prime''' is ''P''(''n'') that is [[prime number|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 &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. == 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. ==External links== *[http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000931 Padovan sequence (sequence A000931)] in [[OEIS]] *{{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.] [[Category:Integer sequences]] [[Category:Recurrence relations]] [[es:Secuencia de Padovan]] [[fr:Suite de Padovan]] [[nl:Rij van Padovan]] [[zh:巴都萬數列]] [[ru:Последовательность Падована]]