Sucesión de Padovan

En una entrada anterior estudiamos la sucesión de Perrin

(http://hojaynumeros.blogspot.com.es/2014/11/sucesion-de-perrin.html).

La de hoy, de Padovan, es muy parecida, por lo que se recomienda leer antes la entrada enlazada. Recordamos:

La sucesión de Perrin es recursiva de tercer orden homogénea, por lo que necesita tres valores iniciales y que X(n) dependa de los tres valores anteriores X(n-1), X(n-2) y X(n-3) mediante la relación

X_n= A*X_n-1+B*X_n-2+C*X_n-3

En este caso particular sólo depende de los dos últimos, y no de X(n-1). Concretando:

Condiciones iniciales: X₀=3   X₁=0  X₂=2 Ecuación de recurrencia: X_n= X_n-2+X_n-3

Pues bien, la sucesión de Padovan es similar, pero con distintos valores iniciales:

X₀=1   X₁=1  X₂=1

Como con la anterior, podemos construirla con nuestra herramienta de hoja de cálculo adaptada a las sucesiones recurrentes de tercer orden.

(http://hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#recurre2)

Escribimos los coeficientes 0, 1,1 y los valores iniciales 1, 1, 1:

Y obtenemos:

Son los números espirales de Padovan contenidos en http://oeis.org/A134816. Existen otras variantes de esta sucesión, pero nos dedicaremos en esta entrada a la que comienza con 1, 1, 1. Por el carácter de este blog, omitiremos propiedades gráficas, como la espiral de triángulos, que puedes consultar en otras páginas.

Relaciones recurrentes

Para abreviar a los términos de esta sucesión los identificaremos como P(n).

En muchas páginas web podrás encontrar otras relaciones recurrentes además de la de la definición, P(n)=P(n-2)+P(n-3). Aquí sólo comentaremos alguna dejando como ejercicio el análisis de las demás.

(1)  P(n)=P(n-1)+P(n-5)

Se puede verificar por inducción: Se cumple en los primeros términos, como puedes comprobar con la misma hoja de cálculo:

Extensión a P(n+1)

P(n+1)=P(n-1)+P(n-2)=P(n-2)+P(n-6)+P(n-3)+P(n-7)=P(n)+P(n-4), luego se cumple la inducción completa.

(2) P(n)= P(n-2)+P(n-4)+P(n-8)

Sólo veremos los primeros términos con hoja de cálculo y dejaremos la demostración por inducción como ejercicio.

Hay más relaciones de este tipo. Las tienes en

http://es.wikipedia.org/wiki/Sucesi%C3%B3n_de_Padovan

Una interesante es la que relaciona la sucesión de Perrin con la de Padovan:

Perrin(n)=P(n+1)+P(n-10)

Con nuestra hoja hemos construido este esquema para que compruebes que se cumple para los primeros términos. El justificarlo por inducción es fácil por compartir ambas sucesiones la misma fórmula de recurrencia.

Ecuación característica

La ecuación característica correspondiente será x³-x-1=0, es decir, la misma que para la sucesión de Perrin. Con el botón Resolver de esa hoja obtienes las tres soluciones de la ecuación, una real y dos complejas

La solución real 1,32471… es el número plástico y,  que ya presentamos en el estudio de la sucesión de Perrin. También la sucesión de Padovan se acerca progresivamente a las potencias de este número, como puedes ver en este cálculo realizado con nuestra hoja:

Función generatriz

Usando procedimientos similares a los que explicamos para las recurrentes de segundo orden, se puede demostrar que la función generatriz es

Puedes comprobar que esta es la F.G. adecuada efectuando este desarrollo en PARI

write("sucesion.txt",taylor((3-x^2)/(1-x^2-x^3),x,20))

Crea un archivo de texto “sucesión.txt” en la misma carpeta de PARI y verás cómo te reproduce la sucesión:

x + x^2 + x^3 + 2*x^4 + 2*x^5 + 3*x^6 + 4*x^7 + 5*x^8 + 7*x^9 + 9*x^10 + 12*x^11 + 16*x^12 + 21*x^13 + 28*x^14 + 37*x^15 + 49*x^16 + 65*x^17 + 86*x^18 + 114*x^19 + O(x^20)

Los coeficientes del polinomio reproducen la sucesión de Padovan, con el índice desfasado en 1 porque hemos comenzado con el valor 0.

Relación con cuestiones combinatorias

Todas las sucesiones recurrentes suelen tener relación con particiones y composiciones (particiones con orden), porque su generación a partir de elementos anteriores puede coincidir. En el caso de la sucesión de Padovan también existen esas relaciones. Veamos:

P(n) coincide con las composiciones de n+2 en sumandos 2 y 3

En efecto, P(0)=P(1)=P(2) valen 1, que son las formas de descomponer 2, 3 y 4 en sumandos ordenados 2 y 2. P(3)=2 porque 5=2+3=3+2. P(4)=2, ya que 6=3+3=2+2+2.

Con nuestra hoja Cartesius (aún no publicada) se pueden comprobar estos desarrollos. Por ejemplo, para el caso de 8, plantearíamos:

Aunque no conozcas su sintaxis, basta explicarte que hemos pedido que desde 1 hasta 8, usando el conjunto {2,3} busque todas las sumas iguales a 8 con repetición.

Efectivamente, resultan 4=P(6)

En general, cualquier suma correspondiente a N resultará de añadir un 2 a las composiciones de N-2 y un 3 a las de N-3, por lo que su generación es idéntica a la de la sucesión de Padovan. Tal como nos ocurrió con la sucesión de Narayana (http://hojaynumeros.blogspot.com.es/2015/01/sucesion-de-las-vacas-de-narayana.html), esta descomposición da lugar a la expresión de los números de Padovan como suma de números combinatorios. En http://en.wikipedia.org/wiki/Padovan_sequence tienes uno de ellos:

Así, por ejemplo, en el desarrollo para k=11 con Cartesius vemos clara la descomposición en números combinatorios (recuerda que las permutaciones con repetición y dos elementos equivalen a esos números)

Para quienes apreciáis las técnicas de programación, insertamos esta función por si queréis implementarla en vuestra hoja de cálculo:

Public Function padovan(n)
Dim p, q, t, s, i, nn

 nn = n + 2: p = Int(nn / 2): q = nn - 2 * p: t = 0

While p >= q
s = 1: For i = 0 To q - 1: s = s * (p - i) / (q - i): Next i 'Calcula el número combinatorio
t = t + s 'Suma los números combinatorios
p = p - 1: q = q + 2
Wend
padovan = t
End Function