1. ## Difference equation

Hi, I have a problem with below exercise:
Express the solution to each of the following counting problems in terms of a difference equation, then use a generating function to solve the difference equation to give an explicit solution.
I am making a border for the front of a garden bed out of small bricks that are 10 cm long and larger bricks that are 20 cm long. If the small bricks come in two colours, and the larger bricks come in three possible colours, how many different borders of length 10n cm can I make?

2. Here is how you would set up the recurrence:

To layout a garden with 10n cm, we can use any 2 of the 10 cm blocks, and layout the rest of the 10(n-1) cm.
Or we can use any 3 of the 20 cm blocks, and layout the rest of the 10(n-2) cm.

$\displaystyle a_n = 2a_{n-1} + 3a_{n-2}$

3. Thanks, this bit I understand, but have you got idea for further steps?

4. This is a standard linear recurrence.
You can rewrite it in this form: $\displaystyle a_n - 2a_{n-1} - 3a_{n-2} = 0$
Have you learned about generating functions in class?

5. Well, does it mean that the generating function is of the form $\displaystyle \sum_{i=0}a_{i}x^i$ ?

6. Originally Posted by Gibo
Well, does it mean that the generating function is of the form $\displaystyle \sum_{i=0}a_{i}x^i$ ?
Sure. Multiply the recurrence by $\displaystyle x^n$, then do a summation.

Also, this may help: http://brooks-pdx.pbworks.com/f/CS340-Section5.4.pdf

7. Ok, thanks, and just the last thing. What about the initial conditions? $\displaystyle a_{0}=1, a_{2}=2$ ? Am I right

8. Originally Posted by Gibo
Ok, thanks, and just the last thing. What about the initial conditions? $\displaystyle a_{0}=1, a_{2}=2$ ? Am I right
$\displaystyle a_0 =$ number of ways to tile 0 cm. This is 1, correct.
$\displaystyle a_2 =$ number of ways to tile 20 cm. Why is it 2?
Also, what happened to $\displaystyle a_1$?

You only need 2 initial conditions.
Either pick $\displaystyle a_0,a_1$ or $\displaystyle a_1,a_2$.

9. Well, $\displaystyle a_{2}=2$, because we can tile 20 cm in two different ways. We can use two 10cm bricks or one 20cm long. In that case $\displaystyle a_{1}=1$, is that correct?

10. Originally Posted by Gibo
Well, $\displaystyle a_{2}=2$, because we can tile 20 cm in two different ways. We can use two 10cm bricks or one 20cm long. In that case $\displaystyle a_{1}=1$, is that correct?
11. I hope now I understand $\displaystyle a_{0}=1, a_{1}=2$, hence $\displaystyle a_{2}=7$. Is that correct?
I hope now I understand $\displaystyle a_{0}=1, a_{1}=2$, hence $\displaystyle a_{2}=7$. Is that correct?