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}}.\]
Problem
Source:
Tags: algebra, polynomial, geometric sequence, algebra unsolved
SCP
24.08.2014 18:40
We claim that $T_n= 3*2^{n-4} + 1.5 (\frac{-1+\sqrt7*i}{2})^{n-4} +1.5(\frac{-1-\sqrt7*i}{2})^{n-4} $. We prove that $g_n=3*2^{n-4}$ works. It works as $|1.5 (\frac{-1+\sqrt7*i}{2})^{n-4} +1.5(\frac{-1-\sqrt7*i}{2})^{n-4} )| $ $\le 3|(\frac{-1+\sqrt7*i}{2})^{n-4} | = 3 \sqrt{2}^{n-4} < 2 \sqrt{3*2^{n-4}} $. Hence $|T_n-g_n| < 2 \sqrt{g_n}$ Proof claim: We can easily see that $T_4=T_5=T_6=6$. Next $T_n=4*(T_4+T_5+...+T_{n-3})+6=T_{n-1}+4*T_{n-3}$, the characteristic polynomial $x^3-x^2-4=0$ has roots $2,\frac{-1+\sqrt7*i}{2},\frac{-1-\sqrt7*i}{2}$. By using the first values, we can find the expression. $T_n=4*(T_4+T_5+...+T_{n-3})+6$: Look to the last occurence of $1$ for this at place $i<m$, if it is at the first place: there only $6$ ways. Otherwise we can end with $4$ possibilities and before, there are $T_i$ ways.
YanYau
22.03.2016 08:57
I'm a bit confused as to why this recurrence is true: $T_n=4*(T_4+T_5+...+T_{n-3})+6=T_{n-1}+4*T_{n-3}$ Could someone enlighten me?
mathaddiction
15.09.2021 15:20
We call a sequence good if $a_1=1$, $a_2\neq 1$, $a_i\neq a_{i-1}$ and $a_i\neq a_{i-2}$. Obviously there are $3\cdot 2^{n-3}$ good sequence with length $n$. Now notice that if the $n-2$ and $n-1$ digit of a good sequence with length $n-1$ are both not equal to $1$ then defining $1$ to be its $n^{th}$ digit we got a sequence satisfying the condition. Conversely, the first $n-1$ terms of a sequence satisfying the condition is a good sequence with length $n-1$. Now, there are totally $2T_{n-2}+T_{n-1}$ good sequences whose $(n-2)^{th}$ or $(n-1)^{th}$ is $1$, hence $$2T_{n-2}+T_{n-1}+T_n=3\cdot 2^{n-2}$$Now $$4T_{n-2}+2T_{n-1}+2T_n=2T_{n-1}+T_{n}+T_{n+1}$$Hence $$4T_{n-2}+T_n=T_{n+1}$$The characteristic equation of this recurrence relation is $\lambda^3=\lambda^2+4$, which factorizes to $$(\lambda-2)(\lambda^2+\lambda+2)=0$$Therefore, there exists constants $A,B,C$ such that $$T_n=A\cdot 2^n+B\cdot\left(\frac{-1+\sqrt{-7}}{2}\right)^n+C\cdot\left(\frac{-1-\sqrt{-7}}{2}\right)^n$$We compute $T_0=0, T_1=1.5, T_2=0$. \begin{align*} A+B+C&=0\\ 2A-\frac{B+C}{2}+\frac{B-C}{2}\sqrt{-7}&=1.5\\ 4A-\frac{3(B+C)}{2}-(B-C)\left(\sqrt{\frac{-7}{4}}\right)&=0 \end{align*}Solving we have $$A=\frac{3}{16}, B=-\frac{3}{32}+\frac{15\sqrt{7}}{224}i,C=-\frac{3}{32}-\frac{15\sqrt{7}}{224}i$$Let $\alpha,\beta$ be the roots of $x^2+x+2=0$. Define $g_n=\frac{3}{16}\cdot 2^n$, then $$|T_n-g_n|=|B\alpha^n+C\beta^n|\leq |B||\alpha|^n+|C|\beta|^n=(|B|+|C|)(\sqrt{2})^n$$We compute that $$|B|=\frac{3}{\sqrt{224}}=|C|$$Therefore, $$(|B|+|C|)(\sqrt{2})^n=\frac{6}{\sqrt{224}}(\sqrt{2})^n\leq 2\sqrt{A\cdot 2^n}<2\sqrt{g_n}$$as desired.