CGMO 2014 Problem 4

For an integer $m\geq 4,$ let $T_{m}$ denote the number of sequences $a_{1},\dots,a_{m}$ such that the following conditions hold: (1) For all $i=1,2,\dots,m$ we have $a_{i}\in \{1,2,3,4\}$ (2) $a_{1} = a_{m} = 1$ and $a_{2}\neq 1$ (3) For all $i=3,4\cdots, m, a_{i}\neq a_{i-1}, a_{i}\neq a_{i-2}.$ Prove that there exists a geometric sequence of positive integers $\{g_{n}\}$ such that for $n\geq 4$ we have that $$g_{n} - 2\sqrt{g_{n}} < T_{n} < g_{n} + 2\sqrt{g_{n}}.$$