Padovan episode

The Padovan sequence is the integer result , the recursively defined by ${\displaystyle (P_{n})}$

${\displaystyle P_{0}=P_{1}=P_{2}=1}$

and for  n > 2

${\displaystyle P_{n}=P_{n-2}+P_{n-3}}$ .

The sequence begins with the numbers

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

The Padovan episode has the number A000931 in the OEIS episode database (with another 5 upstream links) . The episode is named after the British architect Richard Padovan , who attributes its discovery to the Dutch architect Hans van der Laan . It was by Ian Stewart in the Mathematical Recreations of the journal Scientific American described in June 1996th

Calculation of the terms of the sequence

The Padovan sequence satisfies the following sum formula with binomial coefficients :

${\displaystyle P_{n-2}=\sum _{j=\lceil n/3\rceil }^{\lfloor n/2\rfloor }{j \choose n-2j}}$

Another representation is the linear combination of the n -th powers of the solutions of

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

The real solution to this equation is the plastic number . With the conjugate complex solutions and for n > 2: ${\displaystyle \psi }$ ${\displaystyle q}$ ${\displaystyle {\bar {q}}}$

${\displaystyle P_{n}={\frac {\psi ^{n}}{3\psi ^{2}-1}}+{\frac {q^{n}}{3q^{2}-1}}+{\frac {{\bar {q}}^{n}}{3{\bar {q}}^{2}-1}}}$

Recursion and sum formulas

The Padovan sequence can also be described recursively by

${\displaystyle P_{n}=P_{n-1}+P_{n-5}}$ .

From this one obtains further recursion formulas by repeatedly replacing with  . The partial sums of the Padovan sequence can be calculated easily: ${\displaystyle P_{n}}$ ${\displaystyle P_{n-2}+P_{n-3}}$

${\displaystyle \sum _{n=0}^{m}P_{n}=P_{m+5}-2}$

The Perrin sequence satisfies the same recursion formulas as the Padovan sequence, but has different starting values. The two sequences are connected via the formula

${\displaystyle \mathrm {Perrin} _{n}=P_{n+1}+P_{n-10}}$ .

Generating function

De generating function of the Padovan sequence is

${\displaystyle \sum _{n=0}^{\infty }P_{n}x^{n}={\frac {1+x}{1-x^{2}-x^{3}}}}$  .

Relationship with the plastic number

The quotients of successive terms converge to the plastic number :

${\displaystyle \psi =\lim _{n\to \infty }{\frac {P_{n}}{P_{n-1}}}\approx 1{,}3247}$

Interpretation in combinatorics

${\displaystyle P_{n}}$is the number of possible decompositions of into an ordered sum with the summands or . For example is , so there are ways to write such a sum as: ${\displaystyle n+2}$ ${\displaystyle 2}$ ${\displaystyle 3}$ ${\displaystyle P_{6}=4}$ ${\displaystyle 4}$ ${\displaystyle 8}$

${\displaystyle 2+2+2+2\ \ ;\ \ 2+3+3\ \ ;\ \ 3+2+3\ \ ;\ \ 3+3+2}$

Individual evidence

1. ^ ^{A b} Eric W. Weisstein : Padovan Sequence , In: MathWorld
2. ^ Richard Padovan presents the plastic number , Nexus Network Journal