In how many ways can we paint 16 seats in a row, each red or green, in such a way that the number of consecutive seats painted in the same colour is always odd?

Answer: 1974.
Let $g_{k}, r_{k}$ be the numbers of possible odd paintings of $k$ seats such that the first seat is painted green or red, respectively. Obviously, $g_{k}=r_{k}$ for any $k$. Note that $g_{k}=r_{k-1}+g_{k-2}=g_{k-1}+g_{k-2}$, since $r_{k-1}$ is the number of odd paintings with first seat green and second seat red and $g_{k-2}$ is the number of odd paintings with first and second seats green. Moreover, $g_{1}=g_{2}=1$, so $g_{k}$ is the $k$ th element of the Fibonacci sequence. Hence, the number of ways to paint $n$ seats in a row is $g_{n}+r_{n}=2 f_{n}$. Inserting $n=16$ we obtain $2 f_{16}=2 \cdot 987=1974$.

#