# Difference equation

• Jan 9th 2011, 09:15 AM
Gibo
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?
• Jan 9th 2011, 09:33 AM
snowtea
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}$
• Jan 9th 2011, 09:57 AM
Gibo
Thanks, this bit I understand, but have you got idea for further steps?
• Jan 9th 2011, 10:04 AM
snowtea
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?
• Jan 9th 2011, 10:47 AM
Gibo
Well, does it mean that the generating function is of the form $\sum_{i=0}a_{i}x^i$ ?
• Jan 9th 2011, 10:53 AM
snowtea
Quote:

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
• Jan 9th 2011, 12:54 PM
Gibo
Ok, thanks, and just the last thing. What about the initial conditions? $a_{0}=1, a_{2}=2$ ? Am I right
• Jan 9th 2011, 03:37 PM
snowtea
Quote:

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$.
• Jan 10th 2011, 02:42 AM
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?
• Jan 10th 2011, 04:03 AM
snowtea
Quote:

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?

• Jan 10th 2011, 04:47 AM
Gibo
I hope now I understand $a_{0}=1, a_{1}=2$, hence $a_{2}=7$. Is that correct?
• Jan 10th 2011, 05:00 AM
snowtea
Quote:

Originally Posted by Gibo
I hope now I understand $a_{0}=1, a_{1}=2$, hence $a_{2}=7$. Is that correct?

Yup
• Jan 10th 2011, 05:06 AM
Gibo
Thanks a lot for being so patient. Regards Gibo