# Calculating complexity for recursive algorithm with codependent relations

I wrote a program recently which was based on a recursive algorithm, solving for the number of ways to tile a 3xn board with 2x1 dominoes:

F(n) = F(n-2) + 2*G(n-1)

G(n) = G(n-2) + F(n-1)

F(0) = 1, F(1) = 0, G(0) = 0, G(1) = 1

I tried to calculate the complexity using methods I know such as recursion tree and expansion, but none resulted in any answer. Actually I had never come across such a recursion, where the relations are codependent.

Am I using the wrong methods, or maybe using the methods in a wrong way? And if so, can anyone offer a solution?

Let us note that $$F(n) = G(n+1) - G(n-1)$$. Therefore $$G(n+1)-G(n-1) = G(n-1) - G(n-3) + 2G(n-1),$$ implying that $$G(n+1) = 4G(n-1) - G(n-3).$$
Similarly, $$G(n) = (F(n+1)-F(n-1))/2$$, and so $$(F(n+1)-F(n-1))/2 = (F(n-1)-F(n-3))/2 + F(n-1),$$ implying that $$F(n+1) = 4F(n-1) - F(n-3).$$ These are exactly the same recurrences, though with different initial values.
A simple induction shows that $$F(n) = 0$$ for odd $$n$$ while $$G(n) = 0$$ for even $$n$$ (this also follows from their semantic meaning).
Using the recurrence, we easily get that for even $$n$$, $$F(n) = (1/2 + 1/2\sqrt{3})(2 + \sqrt{3})^{n/2} + (1/2 - 1/2\sqrt{3})(2 - \sqrt{3})^{n/2}.$$ Let us comment that this sequence is A001835.
Similarly, for odd $$n$$, $$G(n) = (1/2 + 1/\sqrt{3})(2 + \sqrt{3})^{(n-1)/2} + (1/2 - 1/\sqrt{3})(2 - \sqrt{3})^{(n-1)/2}.$$ This sequence is A001353.
Alternatively, we can notice that $$\begin{pmatrix} F(n) \\ G(n+1) \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 1 & 3 \end{pmatrix} \begin{pmatrix} F(n-2) \\ G(n-1) \end{pmatrix}$$ It follows that $$\begin{pmatrix} F(2m) \\ G(2m+1) \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 1 & 3 \end{pmatrix}^m \begin{pmatrix} 1 \\ 1 \end{pmatrix}$$ The eigenvalues of the matrix are $$2 \pm \sqrt{3}$$, and so we are led to formulas as stated above.