Sucesión de Jacobsthal

 Esta entrada constituye nuestra participación en la Edición4.1231056256 del Carnaval de Matemáticas.

Iniciamos ahora un repaso de sucesiones definidas mediante una recurrencia lineal de segundo orden

 (ver definición y propiedades en una entrada anterior
 http://hojaynumeros.blogspot.com.es/2014/01/recurrencias-lineales-de-segundo-orden.html
Es muy aconsejable su lectura previa a la de la actual. Si no, puede que no entiendas algunos comceptos).

Unas son muy populares, como la de Fibonacci, otras menos, y podrán constituir un descubrimiento y, por último, algunas serán inéditas o poco estudiadas. Cuando una requiera más estudio le dedicaremos una entrada completa. Hay que destacar que el estudio de una sucesión puede tener el aliciente añadido del repaso de cuestiones diversas que no tienen nada que ver con la recurrencia. Esto último es nuestro principal objetivo.

Sucesión de Jacobsthal

Probemos con algunos valores de los coeficientes y valores iniciales de la recurrencia de segundo orden. Imagina que hacemos A=1, B=2, X₀=0, X₁=1 (Horadam(0,1,2,1). Acudimos a nuestra herramienta en hoja de cálculo

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

y obtenemos:

Esta sucesión, llamada de Jacobsthal, la tienes en http://oeis.org/A001045
0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691,…

Si visitas la página indicada te abrumará la cantidad de propiedades e interpretaciones que presenta esta sucesión.

Con la resolución de la ecuación característica, e interpretándola correctamente, obtendrás la expresión del término general

Por ejemplo, el término décimo será (2^10-1)/3=1023/3=341, como puedes observar en la tabla. A partir de esta expresión es fácil entender que el cociente X(n+1)/X(n) tiende a 2 al crecer n.

En binario puedes representarte mejor esta relación. El numerador tendrá la expresión 10000….001 para n par y 111…111 para n impar (sería un repunit). Al dividir entre 3, las expresiones que resultan para los términos de la sucesión estarán formadas por unos alternados con ceros, salvo si acaso el primero. Por tanto, todos equivaldrán a sumas de potencias alternas de 2 terminando al final en 1. Por ejemplo, 85=2⁶+2⁴+2²+1.

Puedes sumar mentalmente en binario dos términos consecutivos y observarás que te van saliendo ceros hasta llegar a un último 1 a la izquierda. Más claro:

La suma de dos términos consecutivos X(n)+X(n+1) equivale a 2ⁿ

Basta estudiar un poco esta expresión para darnos cuenta de que cada término se aproxima al doble del anterior, una vez por la izquierda y la siguiente por la derecha, acercándose al límite del doble exacto. Lo puedes comprobar en esta tabla de cocientes:

Podemos concretar más:

Cada término se diferencia en una unidad con el doble del anterior.

X(n+1)=2X(n)+(-1)ⁿ

En efecto:

X(n+1)-2X(n)= (2^(n+1)-(-1)^(n+1))/3 - (2^(n+1)-2*(-1)^n)/3 = (2*(-1)^n-(-1)^(n+1))/3 =(2*(-1)^n+(-1)^n)/3 = (-1)^n, luego la diferencia es 1 en valor absoluto.

Esta es otra forma de demostrar que el cociente X(n+1)/X(n) tiende a 2 al crecer n.

Algunas propiedades

-El que la diferencia entre 3X(n) y 2ⁿ sea sólo la unidad, nos vale para descomponer una fila del triángulo de Pascal en tres sumandos, dos de ellos X(n) y el otro una unidad mayor o menor. Por ejemplo, la fila 1, 7, 21, 35, 35, 21, 7, 1 se puede descomponer usando x(7)=43:

1+7+21+35+35+21+7+1=(1+7+35)+(35+7+1)+(21+21)=43+43+42

- El producto de dos términos consecutivos es un número triangular:

Si X(n+1)=2X(n)+(-1)ⁿ,el producto X(n)*X(n+1)=2X(n)*(2X(n)+(-1)^n)/2 tendrá la forma de la mitad del producto de dos números consecutivos, que es la definición de un número triangular.

Quizás lo entiendas mejor con un ejemplo: 43691*87381 es un producto de ese tipo y lo podemos escribir como 87381*87382/2

- El término X(n) con n>1 equivale al número de teselaciones de un rectángulo de 3 por n-1 con baldosas de 1 por 1 y 2 por 2.

Lo podemos demostrar por inducción.

Para n=2 X(2)=1 y coincide con la única forma de teselar así un rectángulo de 3 por 1, ya que sólo se podrían emplear teselas 1 por 1 y no hay otra posibilidad.

Para n=3, X(3)=3, que cuenta las posibles teselaciones de un rectángulo de 2 por 3. Efectivamente, serían 3 las posibilidades con baldosas de 1 por 1 y de 2 por 2:

Procedamos a la inducción. Imaginemos que X(n-1) representa las teselaciones de este tipo en un rectángulo de 3 por n-2. Al añadirle una columna más al rectángulo sólo hay tres posibilidades:

En la primera los tres cuadrados no pueden completar una baldosa de 2 por 2, luego no añaden ni quitan posibilidades, es decir, que el número de teselaciones de este tipo coincidirá con X(n-1).

En las otras dos posiciones es obligado completar a 2 por 2, y de una forma única, luego el número total será X(n-2). Como hay dos posiciones, el número total será X(n)=X(n-1)+2X(n-2), que es precisamente l definición de la sucesión. La propiedad es cierta.

Dejamos como ejercicio demostrar una variante: X(n) es el número de teselaciones del rectángulo de 2 por n-1 mediante fichas de dominó de 1 por 2 y cuadrados de 2 por 2.

- Suma de la sucesión

 La suma de los n primeros términos de la sucesión equivale al valor de X(n+1) si n es par y a X(n+1)-1 si es impar, es decir S(n)=X(n+1)+(-1)^{n mod 2}. Observando la tabla se comprueba esta propiedad para los primeros términos:

Sólo nos quedaría completar la inducción:

Si S(n)=X(n+1)+(-1)^{n mod 2}, al sumarle un nuevo término X(n+1) nos daría S(n+1)=2*X(n+1)+(-1)^{n mod 2}= X(n+2)+(-1)^{n+1 mod 2}.

Omitimos los detalles del encaje exacto de la paridad de n en la demostración.

- La función generatriz de esta sucesión es  x/(1-x-2*x^2), como puedes comprobar con este desarrollo en PARI

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

x + x^2 + 3*x^3 + 5*x^4 + 11*x^5 + 21*x^6 + 43*x^7 + 85*x^8 + 171*x^9 + 341*x^10 + 683*x^11 + 1365*x^12 + 2731*x^13 + 5461*x^14 + 10923*x^15 + 21845*x^16 + 43691*x^17 + 87381*x^18 + 174763*x^19 + O(x^20)

Según la teoría explicada en la entrada citada, basta aplicar la fórmula general:

Y sigue sorprendiéndonos

La imagen que adjuntamos contiene una propiedad nueva de esta sucesión: Hemos tomado el término 3 y en la tercera columna lo hemos ido multiplicando por las distintas potencias de 2, con lo que obtenemos la suma de un término más avanzado con el correspondiente a la potencia. Se ha destacado que 3*2^3=24=21+3=X(7)+X(4).

Sigue bajando por la tabla y descubrirás nuevas sumas de este tipo. Ahora, haz lo mismo con el 5 o con el 11 y resultarán relaciones nuevas. Todas ellas se resumen en esta:

X(n)+X(n+2k+1)=X(2k+2)*2^(n-1)

(Se supone que al primer término lo consideramos X(1) y no X(0))

Por ejemplo, en la de la figura: X(4)+X(7)=X(4)*2^3=3+21=24. Otra: X(5)+X(10)=X(6)*2^4=5+171=176=11*16

Esta propiedad, expresada con otros índices, ha sido propuesta por Paul Curtz en http://oeis.org/A001045