Padovan sequence

In number theory, the Padovan sequence is the sequence of integers P(n) defined by the initial values:

and the recurrence relation

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, ...

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 Dutch architect Hans van der Laan in his 1994 essay Dom. Hans van der Laan: Modern Primitive. The sequence was described by Ian Stewart in his Scientific American column Mathematical Recreations in June 1996. He also writes about it in one of his books, "Math Hysteria: Fun Games With Mathematics".

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

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

| −2

| 2

| −1

| 0

| 1

| −1

| 1

| 0

| 1

| 0

| 1

Sums of terms

The sum of the first n terms in the Padovan sequence is 2 less than P(n + 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 coefficients 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, n) with 2m + n = 12 which give non-zero binomial coefficients are (6, 0), (5, 2) and (4, 4), and:

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

Binet-like formula

thumb|Triangles with sides in ratio of 1/ form a closed spiral

The Padovan sequence numbers can be written in terms of powers of the roots of the equation Given these three roots, the Padovan sequence can be expressed by a formula involving p, q and r :

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

where a, b and c are constants. 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) observed that these diagonals generate the Padovan sequence by summing the diagonal numbers.

500x500px

Geometric analogies

It is also analogous to the Fibonacci sequence in the geometric sense; the Fibonaccis make a square spiral and the Padovans make a triangular one.

References

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

External links

A Padovan sequence calculator