Arranging $1,2$ and $3$ into $n$ places. 
There are $n$ places to arrange the numbers $1,2$ and $3$. The rules are

*

*Same numbers are not adjacent.

*$2$ is always between $1$ and $3$

*We can use as many number as we want. For example, it can be all $1$'s through places.

In how many ways, we can do this arrangement?

For $n = 3$, we have $123, 321, 131, 313$. I've also checked for more values of $n$ and it feels like the answer should be $2F_n$ where $F_n$ is the $n^\text{th}$ Fibonacci's number. I am not sure, though.
 A: You are correct. Given a selection of the positions for the number twos such that no twos are adjacent and the first and last positions are not two there are exactly $2$ sequences that satisfy this condition. To see this notice after fixing if the first position is $1$ or $3$ everything else gets forced.
The number of ways to select the positions where the twos can go is $F_n$ (because it is basically a sequence of length $n-2$ with symbols $x$ and $2$ that cannot contain consecutive twos).
We now want to prove the number of sequences of length $n$ with symbols $x$ and $2$ that do not contain consecutive twos is $F_{n+2}$.
It is easy to prove it for $n=1,2$ and we now find a recursive relation for the number of sequences of this kind. We are going to count the sequences of length $n$ by splitting them into two groups. How many sequences end with $2$? Exactly as many as the number of sequences of length $n-2$ (because the second to last entry must be $x$. How many sequences end with $x$? Exactly as many as the number of sequences of length $n-1$. So the number of such sequences coincides with the fibonacci sequence in the first two values and also satifies the same recurrence.
