3
$\begingroup$

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!

  • 0
    @Jyrki, sometimes I feel like I'm banging my head against a brick wall, but I appreciate the Pink Floyd reference.2011-06-15

1 Answers 1

5

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$

  • 0
    greath and comprehendible answer, thank you!2011-06-14