Probar o refutar divide $2^n$ $T_{2^n}$ $n > 2$.

Question

Cumple con la secuencia de Tribonacci

$$T_0 = T_1 = 0, T_2 = 1,$$

$$T_n = T_{n-1} + T_{n-2} + T_{n-3}.$$

Prove or disprove that $2 ^ n $ divides $ T_ {2 ^ n} $ for $n > 2 $.

(I think $2 ^ n $ divides $ T_ {2 ^ n} $.)

P.S.

To confirm the ArtW's proposition, I calculate $ T_ {2 ^ n + l} $ mod $2 ^ {n + 2} $ por rubí.

require 'matrix'

def power(a, n, mod)
  return Matrix.I(a.row_size) if n == 0
  m = power(a, n >> 1, mod)
  m = (m * m).map{|i| i % mod}
  return m if n & 1 == 0
  (m * a).map{|i| i % mod}
end

def f(m, n, mod)
  ary0 = Array.new(m, 0)
  ary0[0] = 1
  v = Vector.elements(ary0)
  ary1 = [Array.new(m, 1)]
  (0..m - 2).each{|i|
    ary2 = Array.new(m, 0)
    ary2[i] = 1
    ary1 << ary2
  }
  a = Matrix[*ary1]
  (power(a, n, mod) * v)[m - 1]
end

[-2, -1, 0, 1, 2].each{|l|
  (1..20).each{|i|
    j = 2 ** i + l
    # T_j % (2 ** (i + 2))
    p [j, f(3, j, 2 ** (i + 2))]
  }
}

Salida

[0, 0]
[2, 1]
[6, 7]
[14, 31]
[30, 127]
[62, 255]
[126, 511]
[254, 1023]
[510, 2047]
[1022, 4095]
[2046, 8191]
[4094, 16383]
[8190, 32767]
[16382, 65535]
[32766, 131071]
[65534, 262143]
[131070, 524287]
[262142, 1048575]
[524286, 2097151]
[1048574, 4194303]
[1, 0]
[3, 1]
[7, 13]
[15, 41]
[31, 17]
[63, 33]
[127, 65]
[255, 129]
[511, 257]
[1023, 513]
[2047, 1025]
[4095, 2049]
[8191, 4097]
[16383, 8193]
[32767, 16385]
[65535, 32769]
[131071, 65537]
[262143, 131073]
[524287, 262145]
[1048575, 524289]
[2, 1]
[4, 2]
[8, 24]
[16, 0]
[32, 64]
[64, 128]
[128, 256]
[256, 512]
[512, 1024]
[1024, 2048]
[2048, 4096]
[4096, 8192]
[8192, 16384]
[16384, 32768]
[32768, 65536]
[65536, 131072]
[131072, 262144]
[262144, 524288]
[524288, 1048576]
[1048576, 2097152]
[3, 1]
[5, 4]
[9, 12]
[17, 8]
[33, 80]
[65, 160]
[129, 320]
[257, 640]
[513, 1280]
[1025, 2560]
[2049, 5120]
[4097, 10240]
[8193, 20480]
[16385, 40960]
[32769, 81920]
[65537, 163840]
[131073, 327680]
[262145, 655360]
[524289, 1310720]
[1048577, 2621440]
[4, 2]
[6, 7]
[10, 17]
[18, 49]
[34, 33]
[66, 65]
[130, 129]
[258, 257]
[514, 513]
[1026, 1025]
[2050, 2049]
[4098, 4097]
[8194, 8193]
[16386, 16385]
[32770, 32769]
[65538, 65537]
[131074, 131073]
[262146, 262145]
[524290, 524289]
[1048578, 1048577]

Answer 1

Te voy a mostrar que $2^{n+1}\mid\mid T_{2^n}$ todos los $n\ge 5$. Junto con el trabajo de casos para $n<5$ esto da una prueba de su reclamación.

Lema: Para todos los enteros $n,m\ge 1$ tenemos $$T_{n+m}=T_{m}T_{n-1}+T_{m-1}T_{n}+T_{m}T_{n}+T_{m+1}T_{n+1}.$$ Prueba: Sencillo de inducción en $m$. $\square$

Proposición: Para todos los números enteros $n\ge 5$: $$T_{2^n}\equiv 2^{n+1}\pmod{2^{n+2}}.$$ Prueba: vamos a utilizar la inducción en $n$ a probar simultáneamente las siguientes congruencias para $n\ge 5$: $$\begin{cases} T_{2^{n}-2}&\equiv -1&&\pmod{2^{n+2}}\\T_{2^{n}-1}&\equiv 2^{n-1}+1&&\pmod{2^{n+2}}\\T_{2^{n}}&\equiv 2^{n+1}&&\pmod{2^{n+2}}\\T_{2^{n}+1}&\equiv 5\cdot 2^{n-1}&&\pmod{2^{n+2}}\\T_{2^{n}+2}&\equiv 2^{n}+1&&\pmod{2^{n+2}}\end{cases}$$ Esto es cierto para $n=5$. Supongamos que es cierto para algunos $n\ge 5$. Entonces, por el lema, $$\begin{align}T_{2^{n+1}}&=T_{2^n-1}T_{2^n}+T_{2^n-2}T_{2^n+1}+T_{2^n-1}T_{2^n+1}+T_{2^n}T_{2^n+2}\\&\equiv(2^{n-1}+1)2^{n+1}-5\cdot2^{n-1}+(2^{n-1}+1)\cdot 5\cdot 2^{n-1}+2^{n+1}(2^n+1)\pmod{2^{n+3}}\\&\equiv2^{n+2}\pmod{2^{n+3}}\end{align}$$ Para $T_{2^{n+1}-1}$ $T_{2^{n+1}+1}$ algo similar, así que lo dejé. Finalmente, $T_{2^{n+1}-2}$ $T_{2^{n+1}+2}$ se encuentran el uso de la recursividad de la fórmula. Con esto se completa la inducción. $\square$

Answer 2

Una solución por la forma de la matriz (como se sugiere por la Ihf): Podemos escribir:

$\left(\begin{array}{c} T_{n+1}\\ T_{n+2}\\ T_{n+3} \end{array}\right)=\left(\begin{array}{ccc} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 1 & 1 \end{array}\right)\left(\begin{array}{c} T_{n}\\ T_{n+1}\\ T_{n+2} \end{array}\right)$

Así que si $M$ es la matriz de la multiplicación, podemos escribir $(T_n,T_{n+1},T_{n+2})^t=M^n\cdot(0,0,1)^t$.

En particular, $T_n$ es el valor en la parte superior derecha de la esquina de la matriz $M^n$, por lo que tenemos que mostrar que para $n>2$ la derecha-la esquina superior derecha de la matriz $M^{2^n}$ es divisible por $2^n$. Vamos a hacerlo por recursión: vamos a $n$ ser un entero tal que podemos escribir la matriz $M^{2^n} \pmod{2^n}$ en el siguiente formulario (por ejemplo,$n=3$):

$\left(\begin{array}{ccc} 2^{n-1}+1 & 2^{n-1} & 0\\ 0 & 2^{n-1}+1 & 2^{n-1}\\ 2^{n-1} & 2^{n-1} & 1 \end{array}\right)$

Ahora nos eleva a una matriz de $\pmod{2^{n+1}}$, claramente tenemos más posibilidades, así que vamos a escribir en la siguiente forma:

$\left(\begin{array}{ccc} 2^{n-1}+1+\delta_1\cdot2^n & 2^{n-1}+\delta_2\cdot2^n & \delta_3\cdot2^n\\ \delta_4\cdot2^n & 2^{n-1}+1+\delta_5\cdot2^n & 2^{n-1}+\delta_6\cdot2^n\\ 2^{n-1}+\delta_7\cdot2^n & 2^{n-1}+\delta_8\cdot2^n & 1+\delta_9\cdot2^n \end{array}\right)$

donde $\delta_i=0,1$.

Si queremos calcular el cuadrado de la matriz (siempre mod $2^{n+1}$) se encontró una matriz en la misma forma que en el caso de $2^n$.