recursive relation for putting signs in 2*n table

Question

Consider we have a $2\times n$ table and we want to put a sign in some of the cells, and we don't put signs in both adjacent cells give a recursive phrase that shows that how many ways we can do that?

Answer 1

Hint: Let $A(n)$ be the number of $2 \times n$ boards filled as you say with the bottom row empty, $B(n)$ with a sign on the left, $C(n)$ with a sign on the right. You can pu an empty row below anything, so $A(n)=A(n-1)+B(n-1)+C(n-1)$ Write the other two recurrences. Note that $B(n)=C(n)$ and you should be able to find a recurrence just for $A(n)$