1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.