5
$\begingroup$

The Tribonacci sequence satisfies

$$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}$ by ruby.

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))]
  }
}

Output

[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]
$\endgroup$
9
+50
$\begingroup$

I'll show that $2^{n+1}\mid\mid T_{2^n}$ for all $n\ge 5$. Together with casework for $n<5$ this gives a proof of your claim.

Lemma: For all integers $n,m\ge 1$ we have $$T_{n+m}=T_{m}T_{n-1}+T_{m-1}T_{n}+T_{m}T_{n}+T_{m+1}T_{n+1}.$$ Proof: Straightforward induction on $m$. $\square$

Proposition: For all integers $n\ge 5$: $$T_{2^n}\equiv 2^{n+1}\pmod{2^{n+2}}.$$ Proof: We shall use induction on $n$ to prove simultaneously the following congruences for $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}$$ This is true for $n=5$. Assume it to be true for some $n\ge 5$. Then by the lemma, $$\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}$$ For $T_{2^{n+1}-1}$ and $T_{2^{n+1}+1}$ we use something similar, so I let that to you. Finally, $T_{2^{n+1}-2}$ and $T_{2^{n+1}+2}$ are found using the recursion formula. This completes induction. $\square$

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ It'd be nice to interpret this in matrix form as in math.stackexchange.com/questions/1827074/…. However, the powers of the corresponding matrix are not so immediate because they mix two Tribonacci sequence with different starting values. $\endgroup$ – lhf Jun 21 '16 at 13:27
  • $\begingroup$ $$\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+2}}\\&\equiv?\pmod{2^{n+3}}\end{align}$$ $\endgroup$ – TOM Jun 25 '16 at 22:18
  • $\begingroup$ @Manyama We can take the congruences mod $2^{n+3}$ because every term is divisible by 2: if $a\equiv b \pmod{2^n}$ then $2a\equiv 2b\pmod{2^{n+1}}$. $\endgroup$ – ArtW Jun 27 '16 at 23:12
  • $\begingroup$ Is the following OK? \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+2}}\\&\equiv2\cdot(2^{n-1}+1)2^{n+1}-2\cdot 5\cdot2^{n-1}+2\cdot (2^{n-1}+1)\cdot 5\cdot 2^{n-1}+2\cdot 2^{n+1}(2^n+1)\pmod{2^{n+3}}\\&\equiv0\pmod{2^{n+3}}\\&\end{align} $\endgroup$ – TOM Jun 28 '16 at 10:01
  • $\begingroup$ no, you should factor out a 2 instead of adding a factor! $\endgroup$ – ArtW Jun 28 '16 at 11:49
2
$\begingroup$

A solution by matrix form (as suggested by Ihf): We can write:

$\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)$

So if $M$ is the matrix of multiplication, we can write $(T_n,T_{n+1},T_{n+2})^t=M^n\cdot(0,0,1)^t$.

In particular $T_n$ is the value in the right-top corner of the matrix $M^n$, so we have to show that for $n>2$ the righ-top corner of the matrix $M^{2^n}$ is divisible by $2^n$. Let's do it by recursion: let $n$ be an integer such that we can write the matrix $M^{2^n} \pmod{2^n}$ in the following form (for example $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)$

Now we lift it to a matrix $\pmod{2^{n+1}}$, clearly we have more possibilities, so we will write it in the following form:

$\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)$

where $\delta_i=0,1$.

If we calculate the square of the matrix (always mod $2^{n+1}$) we found a matrix in the same form of the case $2^n$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.