# Sequência de Padovan

Em teoria dos números, a sequência de Padovan é a sequência de inteiros P(n) definida pelos valores iniciais
    $P(0)=P(1)=P(2)=1,$
e a relação de recorrência
    $P(n)=P(n-2)+P(n-3).$
Os primeiros valores de P(n) são
    1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, ... (sequência A000931 na OEIS)
A sequência de Padovan é denominada em memória de Richard Padovan, que atribuiu sua descoberta ao arquiteto neerlandês Hans van der Laan em seu ensaio de 1994 Dom. Hans van der Laan : Modern Primitive. A sequência foi descrita por Ian Stewart em sua coluna na Scientific American Mathematical Recreations em junho de 1996. Ele também escreve sobre ela em um de seus livros, "Math Hysteria: Fun Games With Mathematics".
A definição acima é aquela dada por Ian Stewart e por MathWorld. Outras fontes podem começar a sequência com valores diferentes, e neste caso algumas das identidades neste artigo devem ser ajustadas com deslocamentos apropriados.

## Relações de recorrência

Na espiral, cada triângulo compartilha um lado com dois outros, dando uma prova visual de que a sequência de Padovan também satisfaz a relação de recorrência
    $P(n)=P(n-1)+P(n-5)$
A partir disso, a recorrência de definição e outras recorrências à medida que são descobertas, pode-se criar um número infinito de recorrências adicionais substituindo repetidamente $P(m)$ by $P(m-2)+P(m-3)$.
A sequência de Perrin satisfaz as mesmas relações de recorrência que a sequência de Padovan, embora tenha valores iniciais diferentes. Esta é uma propriedade das relações de recorrência.
A sequência de Perrin pode ser obtida da sequência de Padovan pela fórmula
    $\mathrm {Perrin} (n)=P(n+1)+P(n-10).\,$

## Extensão para parâmetros negativos

Como em qualquer sequência definida por uma relação de recorrência, os números de Padovan P(m) para m<0 podem ser definidos reescrevendo a relação de recorrência como
    $P(m)=P(m+3)-P(m+1),$
Começando com m = −1 e avançando no sentido negativo, estendemos P(m) para índices negativo:
    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}$ P$_0$ P$_1$ P$_2$ 7 −7 4 0 −3 4 −3 1 1 −2 2 −1 0 1 −1 1 0 0 1 0 1 1 1

## Soma de termos

A soma dos primeiros n termos da sequência de Padovan é 2 unidades menos que P(n + 5), isto é
    $\sum _{m=0}^{n}P(m)=P(n+5)-2.$
Somas de termos alternados, somas de todos os terceiros termos e somas de todos os quintos termos são também relacionadas com outros termos na sequência:
    $\sum _{m=0}^{n}P(2m)=P(2n+3)-1$ OEIS: A077855
    $\sum _{m=0}^{n}P(2m+1)=P(2n+4)-1$
    $\sum _{m=0}^{n}P(3m)=P(3n+2)$ OEIS: A034943
    $\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).$ OEIS: A012772
Somas envolvendo produtos de termos da sequência de Padovan satisfazem as seguintes identidades:
    $\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)^{2}P(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.$

## Outras identidades

A sequência de Padovan também satisfaz a identidade
    $P(n)^{2}-P(n+1)P(n-1)=P(-n-7).\,$
A sequência de Padovan é relacionada a somas dos coeficientes binomiais pela identidade
    $P(k-2)=\sum _{2m+n=k}{m \choose n}=\sum _{m=\lceil k/3\rceil }^{\lfloor k/2\rfloor }{m \choose k-2m}.$
Por exemplo, para k = 12, os valores para o par (m, n) com 2m + n = 12 que resultam em coeficientes binomiais não-nulos são (6, 0), (5, 2) e (4, 4), e:
    ${6 \choose 0}+{5 \choose 2}+{4 \choose 4}=1+10+1=12=P(10).\,$

## Fórmulas do tipo Binet

Os números da sequência de Padovan podem ser escritos em termos de potências das raízes da equação
    $x^{3}-x-1=0.\,$
Esta equação tem 3 raízes; uma raiz real p (conhecida como número plástico) e duas raízes complexas conjugadas q e r. dadas estas três raízes, a sequência de Padovan pode ser expressa por uma fórmula envolvendo p, q e r:
    $P\left(n\right)=ap^{n}+bq^{n}+cr^{n}$
onde a, b e c são constantes.
Como a magnitude das raízes complexas q e r são ambas menores que 1 (e portante p é um número de Pisot–Vijayaraghavan), as potências destas raízes convergem para 0 para grande n, e $P\left(n\right)-a{p^{n}}$ tende a zero.
Para todo $n\geq 0$, P(n) é o inteiro mais próximo de ${\frac {p^{n-1}}{s}}$, onde s = p/a = 1.0453567932525329623... é a única raiz real de s$^3$ − 2s$^2$ + 23s − 23 = 0. A razão de termos sucessivos na sequência de Padovan converge para p, que tem um valor de aproximadamente 1.324718. Esta constante apresenta a mesma relação com a sequência de Padovan e a sequência de Perrin como a proporção áurea tem com a sequência de Fibonacci.

## Triângulo de Pascal

Erv Wilson em seu artigo The Scales of Mt. Meru observou determinadas diagonais no triângulo de Pascal (ver diagrama) e marcou-os em papel em 1993. Os números de Padovan foram descobertos em 1994. Paul Barry (2004) mostrou que estas diagonais geram a sequência de Padovan somando os números diagonais.