Padovan sequence - Citizendia

The Padovan sequence is the sequence of integers 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). In Mathematics, a sequence is an ordered list of objects (or events The integers (from the Latin integer, literally "untouched" hence "whole" the word entire comes from the same origin but via French "Difference equation" redirects here It should not be confused with a Differential equation.

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, . . . (sequence A000931 in OEIS)

Spiral of equilateral triangles with side lengths which follow the Padovan sequence. The On-Line Encyclopedia of Integer Sequences ( OEIS) also cited simply as Sloane's, is an extensive searchable Database of Integer sequences

The Padovan sequence is named after Richard Padovan who attributed its discovery to Dutch architect Hans van der Laan in his 1994 essay Dom. Richard Padovan (born 1935 is an Architect, Author, Translator and Lecturer. The Netherlands ( Dutch:, ˈnedərlɑnt is the European part of the Kingdom of the Netherlands, which consists of the Netherlands the Netherlands Hans van der Laan : Modern Primitive. The sequence was described by Ian Stewart in his Scientific American column Mathematical Recreations in June 1996. Ian Nicholas Stewart (born 1945) is a professor of Mathematics at University of Warwick, England and a widely known popular-science and science-fiction Scientific American is a Popular science magazine, published (first weekly and later monthly since August 28, 1845, making it

The above definition is the one given by Ian Stewart and by MathWorld. MathWorld is an online Mathematics reference work created and largely written by Eric W 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.

1 Recurrence relations
2 Extension to negative parameters
3 Sums of terms
4 Other identities
5 Binet-like formula
6 Combinatorial interpretations
7 Generating function
8 Generalizations
9 Padovan prime
10 Padovan L-system
11 Padovan Cuboid Spiral
12 External links

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) = 2 P (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) = 4 P (n - 5) + P (n - 14).

The Perrin sequence satisfies the same recurrence relations as the Padovan sequence, although it has different initial values. In Mathematics, the Perrin numbers are defined by the Recurrence relation P (0 = 3 P (1 = 0 P (2 = 2

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 numbers to negative index values). In Mathematics, the Fibonacci numbers are a Sequence of numbers named after Leonardo of Pisa, known as Fibonacci 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, . . .

Sums 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 coefficients 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 2m + 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. In Mathematics, the binomial coefficient \tbinom nk is the Coefficient of the x k term in the Polynomial In math the plastic number (also known as the plastic constant) is the unique real solution of the equation x^3=x+1\ and has the value Given these three roots, the Padovan sequence analogue of the Fibonacci sequence Binet formula is

$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)}.$

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. In Mathematics, the Fibonacci numbers are a Sequence of numbers named after Leonardo of Pisa, known as Fibonacci For large n the formula reduces to

$P\left(n\right) \approx \frac {p^n} {\left(3p^2-1\right)} = \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 sequence and the Perrin sequence as the golden ratio does to the Fibonacci sequence. In Mathematics, the Perrin numbers are defined by the Recurrence relation P (0 = 3 P (1 = 0 P (2 = 2 In Mathematics and the Arts two quantities are in the Golden ratio if the Ratio between the sum of those quantities and the larger one is the

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). In Mathematics, a composition of a positive Integer n is a way of writing n as a Sum of Positive integers Two sums which 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(2n − 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 polynomials called the Fibonacci polynomials, the Padovan sequence numbers can be generalized to yield the Padovan polynomials. In Mathematics a generating function is a Formal power series whose coefficients encode information about a Sequence a n In Mathematics, the Fibonacci numbers are a Sequence of numbers named after Leonardo of Pisa, known as Fibonacci In Mathematics, the Fibonacci polynomials are a Polynomial sequence which can be considered as a generalisation of the Fibonacci numbers Definition In Mathematics, Padovan polynomials are a generalization of Padovan sequence numbers

Padovan prime

A Padovan prime is P(n) that is prime. In Mathematics, a prime number (or a prime) is a Natural number which has exactly two distinct natural number Divisors 1 The first few Padovan primes 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 . An L-system or Lindenmayer system is a parallel rewriting system, namely a variant of a Formal grammar (a set of rules and symbols most famously used . .

Also, if you count the number of As, Bs and Cs in each string, then for the nth string, you have P(n − 5) As, P(n − 3) Bs and P(n − 4) Cs. 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. In Mathematics the Padovan cuboid spiral is the Spiral created by joining the diagonals of faces of successive Cuboids added to a unit cube Successive sides of this spiral have lengths that are the Padovan sequence numbers multiplied by the square root of 2.

External links

Padovan sequence (sequence A000931) in OEIS
Eric W. Weisstein, Padovan Sequence at MathWorld. The On-Line Encyclopedia of Integer Sequences ( OEIS) also cited simply as Sloane's, is an extensive searchable Database of Integer sequences Eric W Weisstein (born March 18, 1969, in Bloomington Indiana) is an Encyclopedist who created and maintains MathWorld MathWorld is an online Mathematics reference work created and largely written by Eric W
Dom Hans Van Der Laan And The Plastic Number by Richard Padovan
Tales of a Neglected Number by Ian Stewart
A Padovan Sequence Calculator can be found here.

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents