Find a recurrence word problem.

[charmedbeauty]

find a recurrence,,, word problem.

Homework Statement

A rectangular board 2cm wide and ncm long is to be covered with smaller tiles of size 2cmx2cm and 1cmx2cm. There is an unlimited supply of both types of tile.


For each n=1,2,... let a_n be the number of ways that a board of length n cm can be covered with the two types of tile.

a) find a recurrence relation for a_n , n>2.

b) find a₅

Homework Equations

The Attempt at a Solution

a) I am not really sure how these answers are meant to be set out... its something like a_n= a_n-1...

I imagine when n=3, there is a 2x3 board so it can be tiled with with 3(1x2) or 1(2x2)+1(1x2) tiles. so it can be done in two ways?

n=4 ... 2(2x2) or 4(1x2) or 1(2x2)+ 2(1x2) so 3 ways

n=5... 2(2x5)+1(1x2) or 1(2x2)+3(2x1) or 5(1x2) so 3 ways.

n=6 ... 3(2x2) or 2(2x2) +2(1x2) or 1(2x2) +4(1x2) or 6(1x2) so 4 ways.

am I meant to be seeing a pattern? maybe a_n is the same for (2n) and (2n+1)

all I can think of is that a 2cmx2cm = 2 (1cmx2cm) tiles.

I imagine that part b) has to do with part a) so I can't solve without a.

any help greatly appreciated.

Thanks

 

[Adrmay]

.a) The recurrence relation for an is an = an-1 + an-2. This recurrence relation takes into account the fact that when laying tiles on a board of length n, one can either add two 1x2 tiles (in which case you have a board of length n-2) or one 2x2 tile (in which case you have a board of length n-4). b) For a5, there are 8 ways to tile the board: 3(2x2), 2(2x2) + 2(1x2), 1(2x2) + 4(1x2), 8(1x2).