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.

$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: $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 $\sum_{i=0}a_{i}x^i$ ?

6. Originally Posted by Gibo
Well, does it mean that the generating function is of the form $\sum_{i=0}a_{i}x^i$ ?
Sure. Multiply the recurrence by $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? $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? $a_{0}=1, a_{2}=2$ ? Am I right
$a_0 =$ number of ways to tile 0 cm. This is 1, correct.
$a_2 =$ number of ways to tile 20 cm. Why is it 2?
Also, what happened to $a_1$?

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

9. Well, $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 $a_{1}=1$, is that correct?

10. Originally Posted by Gibo
Well, $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 $a_{1}=1$, is that correct?
11. I hope now I understand $a_{0}=1, a_{1}=2$, hence $a_{2}=7$. Is that correct?
I hope now I understand $a_{0}=1, a_{1}=2$, hence $a_{2}=7$. Is that correct?