# 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)?

-
I think your first sentence should be "height of $n$ and length of $n$". –  Zev Chonoles Jun 13 '11 at 20:00
@muffel: Agree with Zev in that something is missing from the problem statement. Pray, tell us what is $n$? @Zev: I don't think that your interpretation is quite right. How do you build a wall of an odd area using these bricks? –  Jyrki Lahtonen Jun 13 '11 at 20:41
@Jyrki: Good point! Perhaps it is supposed to be $2n$. Hopefully muffel will clarify. –  Zev Chonoles Jun 13 '11 at 20:45
It seems to me that the recurrence relation hold could be true, if the wall is $2\times n$. Muffel, can you verify/check this? Also, shouldn't it be $c_0=1$? –  Jyrki Lahtonen Jun 13 '11 at 20:48
Why are we asked for a concrete formula, when it's a brick wall? –  Gerry Myerson Jun 13 '11 at 23:50

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$$

-
greath and comprehendible answer, thank you! –  muffel Jun 14 '11 at 7:21