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!