I need to to define difference equation for following problem and solve that equation using generating function.
Border of length 10cm is made of small bricks (10cm long) and large bricks (20cm long). Small bricks come in 2 colours and large bricks in 3 colours. How many different borders of length 10n cm can be made.
I'm having problems defining difference equation for this. I've computed:
$u_{1} = 2$
$u_{2} = 5$
$u_n$ should be the number of ways to make a border of length $n$. We have $u_0=1$ as a starting value because there is one way to make a border of length $0$. $u_1=2$ is not correct because there is no way to make a border of length $1$. $u_2=2$ because there are $2$ ways to make a border of length $2$-you start with a border of length $0$ and have $2$ choices of a brick of length $2$. In general, the way to make a border of length $n$ is to start with a border of length $n-2$ and add a length $2$ block (which you can do in $2$ ways) or start with a border of length $n-5$ and add a length $5$ block (which you can do in $3$ ways). The result is $$u_n=2u_{n-2}+3u_{n-5}$$