Multiple choice exam where no three consecutive answers are the same 
A multiple choice test consists of 60 questions, with 4 possible answers for each question. How many multiple choice exams can we create where no three consecutive answers are the same?

I tried 


*

*reducing the problem into two consecutive like problem (for 1, 2,3  to be same, 1-2 and 2-3 must be the same simultaneously);

*checking triples (1, 2, 3), (2, 3, 4), and so on (there are 58 of them).
Unfortunately, I did not arrive at the answer given in the book, which is $3 \times2^{60}.$
 A: Let $T_n$ be the number of "good" tests of length $n$.  We note that $T_1=4,T_2=16$.  There is a simple recursion for $n≥3$, namely $$T_n=3T_{n-1}+3T_{n-2}$$  To see this, simply remark that every good test either ends with $\dots YX$ or $\dots YXX$ for answers $Y\neq X$.  There are $3T_{n-1}$ of the first sort and $3T_{n-2}$ of the second.
That recursion has a closed form, though it isn't especially pleasant.  The characteristic equation is $$\lambda^2=3\lambda+3\implies \lambda = \frac 12\left(3\pm\sqrt {21}\right)$$  Some unpleasant but straightforward algebra then gives $$T_n=\frac 2{21}\left(7+\sqrt {21}\right)\lambda_+^n+\frac 2{21}\left(7-\sqrt {21}\right)\lambda_-^n$$
Where $\lambda_\pm$ denotes the root with the appropriate sign.  Note that $$T_{60}\approx 1.1\times (3.79)^{60}$$ is a lot higher than the number your answer proposes.
Note:  to simplify the calculation it's easier to extend your series down to $T_0=\frac 43$.  That value doesn't make physical sense in your test designing context, but it does mean that $T_2=3\times\left(T_1+T_0\right)$ so it makes sense in the recursion.
