proving that: $(\frac{13}{4})^n\leq a(n)\leq (\frac{10}{3})^n$ Given $a(n)$ number of sequences of length $n$ that are formed by the digits: $0,1,2,3$
such that after the digit $0$ the digit $1$ must immediately follow.
Need to prove that $(\frac{13}{4})^n\leq a(n)\leq (\frac{10}{3})^n$
I  don't know how to start, i don't understand if the number of sequences of length $1$ is $4$ or $3$. 
Thnaks. 
 A: Using the "$1$ immediatelly after $0$" interpretation:
To contruct a sequence with $n$ symbols, we either take a sequence of $n-1$ symbols and place a $1$, $2$ or $3$ afterwards. Or we take a sequence with $n-2$ symbols and place a $01$. Therefore:
$$a(n) = 3a(n-1) + a(n-2)$$
Where $a(0) = 1$, $a(1) = 3$.
The inequalities are achieved for $n \geq 6$:
$a(6) = 1186$. Whereas $\displaystyle\left(\frac{10}{3}\right)^6 > 1371$ and $\displaystyle\left(\frac{13}{4}\right)^6 < 1179$.
Note that since $a(n) = 3a(n-1) + a(n-2) > 3a(n-1)$ therefore 
$$a(n-1) < \frac{1}{3}a(n)\tag{1}$$
On the other hand, $a(n-1) > a(n-2)$ so $a(n) = 3a(n-1) + a(n-2) < 4a(n-1)$ therefore 
$$a(n-1) > \frac{1}{4}a(n)\tag{2}$$
Let's asume that the inequalities are achieved for all $k$ between $6$ and $n$.
$$a(n+1) = 3a(n) + a(n-1) \stackrel{(1)}{<} 3a(n) + \frac{1}{3}a(n) = \\ = \frac{10}{3}a(n) \stackrel{*}{>} \frac{10}{3}·\left(\frac{10}{3}\right)^n = \left(\frac{10}{3}\right)^{n+1} \Longrightarrow \\ \Longrightarrow a(n+1) < \left(\frac{10}{3}\right)^{n+1}$$
And then:
$$a(n+1) = 3a(n) + a(n-1) \stackrel{(2)}{>} 3a(n) + \frac{1}{4}a(n) = \\ = \frac{13}{4}a(n) \stackrel{*}{>} \frac{13}{4}·\left(\frac{13}{4}\right)^n = \left(\frac{13}{4}\right)^{n+1} \Longrightarrow \\ \Longrightarrow a(n+1) > \left(\frac{13}{4}\right)^{n+1}$$
(Where $*$, the induction hypothesis is used).
As we wanted to prove.
