Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
I think your first sentence should be "height of $n$ and length of $n$". –  Zev Chonoles Jun 13 '11 at 20:00
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? –  Jyrki Lahtonen Jun 13 '11 at 20:41
1  
@Jyrki: Good point! Perhaps it is supposed to be $2n$. Hopefully muffel will clarify. –  Zev Chonoles Jun 13 '11 at 20:45
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$? –  Jyrki Lahtonen Jun 13 '11 at 20:48
4  
Why are we asked for a concrete formula, when it's a brick wall? –  Gerry Myerson Jun 13 '11 at 23:50
show 5 more comments

1 Answer

up vote 5 down vote accepted

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

share|improve this answer
    
greath and comprehendible answer, thank you! –  muffel Jun 14 '11 at 7:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.