Algorithms for 2-colouring a 2 x N matrix

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?

One can view this problem as a dynamic programming problem with $3N$ subproblems.

Let $RR(N)$ be the number of solutions for a $2\times N$ matrix where the first row is colored with red-red, $RB(N)$ the number of solutions where the top cell is red and the bottom one blue, and $BR(N)$ the number of solutions where the top cell is blue and the bottom one red. By symmetry $RB(N)=BR(N)$.

We thus get the recurrences:

$$RR(N)=RR(N-1)+2BR(N-1)$$

$$BR(N)=RR(N-1)+BR(N-1)$$

Note that the total number of solutions for a $2\times N$ matrix is equal to $RR(N+1)$.

If one enters the first few terms (1, 3, 7, 17, 41, 99, 239, 577, 1393, 3363,...) of this recurrence in OEIS one finds that it is A078057:

Expansion of $(1+x)/(1-2*x-x^2)$.

[...]

Number of length-$n$ strings of 3 letters $\{0,1,2\}$ with no two adjacent nonzero letters identical. The general case (strings of $L$ letters) is the sequence with g.f. $(1+x)/(1-(L-1)*x-x^2)$. - Joerg Arndt, Oct 11 2012

An algorithm which computes $RR(N)$ by evaluating the recurrence above can do so with $O(N)$ additions. The numbers can get as large as $\Omega(N)$-bit, so the complexity is $O(N^2)$.

StackExchange Computer Science Q#108899, answer score: 4