Our task is to color a given $2 \times N$ matrix with two colours red (R) and blue (B) such that no two adjacent cells are blue. For red, there are no restrictions.
An example of all possible solutions for $N = 2$ is as follows:
(R)---(R) (B)---(R) (R)---(B) (B)---(R) (R)---(B) (R)---(R) (R)---(R)
| | | | | | | | | | | | | |
| | | | | | | | | | | | | |
(R)---(R) (R)---(B) (B)---(R) (R)---(R) (R)---(R) (B)---(R) (R)---(B)
I don't need to list all solutions, but what's a good algorithm for counting all solutions? For example, can we do it in $O(n)$ time or better?