# Difference equation

• Jan 9th 2011, 08: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, 08: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.

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

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

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

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?

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

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

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