Possibilities of building a brick wall Let $c_n$ be the amount of possibilities of building a brick wall with the height of 2 and the length of n containing of the following three bricks (length x height):
Brick 1: 2x2 (square)
Brick 2: 1x2
Brick 3: 2x1
a) Prove that for $n\geq 0: c_{n+2} - c_{n+1} - 2 c_n = 0$
b) Identify a concrete formula for $c_n, n \geq 0$

a) 
For each block of 2x2 there are three possibilities (1 x Brick 1, 2x Brick 2 or 2x Brick 3). For each block of 1x2 there is only one: 1x Brick 2.
For $c_{n+2}$ there should therefore be $c_n \cdot 3$ possibilities, for $c_{n+1}$ only $c_n$, because this can only be reached by using Brick 2. 
This is where I became stuck. Might my approach be wrong?
b)
$c_0 = 0, c_1 = 1, c_2 = 3, c_4 = 9, \cdots$. I'm not quite sure if I handled Brick 2 correctly (see a)). How do I put this into a formula (hint was: formal power series)?
Thank you in advance! 
 A: Part a: (under the assumtion that the wall is $2 \times n$)
Consider a wall of length $n$. It can be constructed in $c_n$ ways.
It can be constructed by using a vertical piece at the end, and then there is $c_{n-1}$ choices for the remaining part of the wall (since what remains is $n-1$ long), or it can be constructed by using a 2x2 piece at the end giving $c_{n-2}$ choices for the rest. At last, it can be constructed by using 2 horizontal pieces at the end, leaving $c_{n-2}$ choices for the rest. This gives in total $c_n = c_{n-1} + 2c_{n-2} \Rightarrow c_{n+2}-c_{n+1}-2c_n = 0$.
Part b:
Guess for $c_n = \alpha^n$, to obtain $\alpha^n - \alpha^{n-1} - 2 \alpha^{n-2} = 0$. Divide by $\alpha^{n-2}$ to get
$$\alpha^2 - \alpha - 2 = 0$$
This has roots $-1$ and $2$. So the general solution is on the form
$$c_n = A \cdot (-1)^n + B \cdot (2)^n$$
Now use your initial conditions $c_1,c_2$ to find $A = \frac{1}{3}$ and $B=\frac{2}{3}$. This gives the following closed formula for $c_n$.
$$c_n = \frac{1}{3}(-1)^n + \frac{2}{3}2^n$$
