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!

  • 1
    I think your first sentence should be "height of $n$ and length of $n$".2011-06-13
  • 1
    @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?2011-06-13
  • 1
    @Jyrki: Good point! Perhaps it is supposed to be $2n$. Hopefully muffel will clarify.2011-06-13
  • 1
    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$?2011-06-13
  • 4
    Why are we asked for a concrete formula, when it's a brick wall?2011-06-13
  • 0
    Gerry, you never feel like you're just another brick in the wall?2011-06-14
  • 0
    @Zev-Chonoles @Jyrki No, it's height of 2 and length of n. @Gerry-Myerson A formula that calculates the amount of possibilities by building a brick wall with the length of n and the height of 2 by a given $n \geq 0$2011-06-14
  • 0
    @muffel: Please edit the question to read that the wall is 2 x n as opposed to 2 x 2 as it is now written.2011-06-14
  • 0
    @Jyrki-Lahtonen Sorry, I forgot that. It is now corrected2011-06-14
  • 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