Mostrar código-fonte de Sequência de Padovan

Em [[teoria dos números]], a '''sequência de Padovan''' é a [[sequência]] de [[Número inteiro|inteiros]] ''P''(''n'') definida<ref name="ps">{{MathWorld|urlname=PadovanSequence|title=Padovan Sequence}}.</ref> pelos valores iniciais

:<math>P(0)=P(1)=P(2)=1,</math>

e a [[relação de recorrência]]

:<math>P(n)=P(n-2)+P(n-3).</math>

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, ... {{OEIS|id=A000931}}

[[Imagem:Padovan triangles (1).png|miniatura|350px|Espiral de triângulos equiláteros com comprimentos de lado seguindo a sequência de Padovan.]]
A sequência de Padovan é denominada em memória de [[Richard Padovan]], que atribuiu sua descoberta ao arquiteto [[Neerlandeses|neerlandês]] [[Hans van der Laan]] em seu ensaio de 1994 ''Dom. Hans van der Laan : Modern Primitive''.<ref name=dhdl>Richard Padovan. ''Dom Hans van der Laan: modern primitive'': Architectura & Natura Press, {{ISBN|9789071570407}}.</ref> A sequência foi descrita por [[Ian Stewart (matemático)|Ian Stewart]] em sua coluna na [[Scientific American]] ''Mathematical Recreations'' em junho de 1996.<ref>Ian Stewart, [https://web.archive.org/web/20060131123213/http://members.fortunecity.com/templarser/padovan.html ''Tales of a Neglected Number''], ''Scientific American'', No. 6, June 1996, pp. 92-93.</ref> Ele também escreve sobre ela em um de seus livros, "Math Hysteria: Fun Games With Mathematics".
<ref name=stewart>{{citation
 |author = Ian Stewart 
 |author-link = Ian Stewart (matemático)
 |isbn = 978-0-19-861336-7
 |page = 87
 |publisher = Oxford University Press
 |title = Math hysteria: fun and games with mathematics
 |year = 2004}}.</ref>

''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
:<math>P(n)=P(n-1)+P(n-5)</math>

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 <math>P(m)</math> by <math>P(m - 2) + P(m - 3)</math>.

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

:<math>\mathrm{Perrin}(n)=P(n+1)+P(n-10).\,</math>

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

:<math>P(m) = P(m+3) - P(m+1),</math>

Começando com ''m'' = −1 e avançando no sentido negativo, estendemos ''P''(''m'') para índices negativo:

:{| class="wikitable" style="text-align:right"
|-
| ''P''<sub>−20</sub>
| ''P''<sub>−19</sub>
| ''P''<sub>−18</sub>
| ''P''<sub>−17</sub>
| ''P''<sub>−16</sub> 
| ''P''<sub>−15</sub>
| ''P''<sub>−14</sub>
| ''P''<sub>−13</sub>
| ''P''<sub>−12</sub>
| ''P''<sub>−11</sub>
| ''P''<sub>−10</sub>
| ''P''<sub>−9</sub>
| ''P''<sub>−8</sub>
| ''P''<sub>−7</sub>
| ''P''<sub>−6</sub>
| ''P''<sub>−5</sub>
| ''P''<sub>−4</sub>
| ''P''<sub>−3</sub>
| ''P''<sub>−2</sub>
| ''P''<sub>−1</sub>
| ''P''<sub>0</sub>
| ''P''<sub>1</sub>
| ''P''<sub>2</sub>
|-
| 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''&nbsp;+&nbsp;5), isto é

:<math>\sum_{m=0}^n P(m)=P(n+5)-2.</math>

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:

:<math>\sum_{m=0}^n P(2m)=P(2n+3)-1</math> {{OEIS2C|A077855}}

:<math>\sum_{m=0}^n P(2m+1)=P(2n+4)-1</math>

:<math>\sum_{m=0}^n P(3m)=P(3n+2)</math> {{OEIS2C|A034943}}

:<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> {{OEIS2C|A012772}}

Somas envolvendo produtos de termos da sequência de Padovan satisfazem as seguintes identidades:

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

==Outras identidades==
A sequência de Padovan também satisfaz a identidade

:<math>P(n)^2-P(n+1)P(n-1)=P(-n-7).\,</math>

A sequência de Padovan é relacionada a somas dos [[Coeficiente binomial|coeficientes binomiais]] pela identidade

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

Por exemplo, para ''k'' = 12, os valores para o par (''m'',&nbsp;''n'') com 2''m''&nbsp;+&nbsp;''n'' = 12 que resultam em coeficientes binomiais não-nulos são (6,&nbsp;0), (5,&nbsp;2) e (4,&nbsp;4), e:

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

==Fórmulas do tipo Binet==
[[Imagem:Triangles in ratio of the plastic number in a three armed counter clockwise spiral.svg|miniatura|Triângulos com lados em relação de 1/{{math|''ρ''}} formam uma espiral fechada]]

Os números da sequência de Padovan podem ser escritos em termos de potências das raízes da equação<ref name="ps"/>

:<math> x^3 -x -1 = 0.\,</math>

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''.<ref>Richard Padovan, [http://www.nexusjournal.com/conferences/N2002-Padovan.html "Dom Hans Van Der Laan and the Plastic Number"], pp. 181-193 in Nexus IV: Architecture and Mathematics, eds. Kim Williams and Jose Francisco Rodrigues, Fucecchio (Florence): Kim Williams Books, 2002.</ref> dadas estas três raízes, a sequência de Padovan pode ser expressa por uma fórmula envolvendo ''p'', ''q'' e ''r'':

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

onde ''a'', ''b'' e ''c'' são constantes.<ref name="ps"/>

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 <math>P\left(n\right) - a {p^n}</math> tende a zero.

Para todo <math>n \ge 0</math>, P(n) é o inteiro mais próximo de <math>\frac {p^{n-1}} {s}</math>, onde ''s'' = ''p''/''a'' = 1.0453567932525329623... é a única raiz real de ''s''<sup>3</sup>&nbsp;&minus;&nbsp;2''s''<sup>2</sup>&nbsp;+&nbsp;23''s''&nbsp;&minus;&nbsp;23&nbsp;=&nbsp;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 [[Número de Perrin|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''<ref>Erv Wilson (1993), [http://www.anaphoria.com/meruone.pdf ''Scales of Mt. Meru'']</ref> 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.{{cn|date=March 2019}}

[[Imagem:Padovan Sequence 2.jpg|500x500px]]

{{Referências}}
*Ian Stewart, A Guide to Computer Dating (Feedback), Scientific American, Vol. 275, No. 5, novembro de 1996, p. 118.

==Ligações externas==
*[https://web.archive.org/web/20070216024906/http://www.plenilune.pwp.blueyonder.co.uk/fibonacci-calculator.asp A Padovan sequence calculator]

[[Categoria:Sequências de números inteiros]]
[[Categoria:Relações de recorrência]]