Recurrence Relations

karkar athlete

Hi everyone,

Hope somebody can give me some pointers, I have a question on recurrence relations hence the title!!

Say you have 1x2 black and 1x2 white tiles. How many ways an nx2 floor can be tiled.
(a) Find the values of A2 and A3.
(b) Hence find a recurrence relation for An.

for A2 I got 8 ways then 24 ways for A3. I couldn't see a relation for them so I tried A4 and got 80 ways. I still cannot find a relation for them.

Thanks for any help what so ever

Brussels Sprout

A1: 2 ways, agreed
A2: 8 ways, also agreed

A3: A3 is basically a combination of A1 and A2. Any way that you tile it in this way will simply be a 2x2 adjacent to a 1x2.

The number of combos here will be:

number of permutations of A2*number of combinations of A1

and we'll need to multiply by 2 since there are two starting locations for A2

(2*8)+(2*8)=32

However we end up double counting here due to the instances when all of the tiles are vertical, e.g. BB B=B BB
This will happen once per combo where they are all vertical which is 2^3 = 8 times.

So A3=32-8=24, Agreed

A4: A4 is a combo of A3 and A1 so using the same equation as last time:

(2*24)+(2*24)=96

and once again we need to subtract for the double counting when the tiles are all vertical. We need to subtract 2^4=16

96-16=80

An: Extrapolating using this pattern gives the recursive relation: An = 4*A(n-1) - 2^n, for n>=3

karkar athlete

Thank you so much, but how did you come to think to use combinations and permutations I didn’t put it in on this but we are asked to draw all possible combinations for A2 and A3, and from that find a recurrence relation. But I couldn't see one so I went on and drew A4 painstakingly .
Also for the recurrence relation why does n>= 3??? Is it because we don't get duplicates early on??
Lastly I am wondering how you came to the conslusion that it is -2^n, like I understand what you did but I just cant see how you got 2^n. Sorry and thanks a million

Brussels Sprout

Ok firstly when you mentioned recurrence in the problem I immediately started thinking in terms of subsets, so like each answer is like a previous answer with something extra done to it (because that's basically what recurrence relations are).

Apologies if this is hard to follow. I worked this out visually so it sounds a bit funny in words.

Looking at a 2x2 grid it's easy to say that this is a combination of two 1x2 grids placed side by side.

going from n=1 to n=2 is a unique transition in this problem though as n=2 is the first time that we can stack tiles horizontally. Therefore it opens up a whole new list of combinations.


So instead let's look at how a 3x2 is a combination of a 2x2 and a 1x2.

So it's a 2x2 grid AND a 1x2 grid

In probability when we use the AND relation like this we must multiply the individual permutations.

So that gives 8*2=16

The thing is though that a 3x2 grid is also a combination of a 1x2 and a 2x2 (so the 1x2 to the left of the 2x2, not the other way around).

So if you think of it visually we can have the square 2x2 piece (SS) first and the rectangular single tile (T) second or the other way around

i.e. SST or TSS

Now we've calculated already that there are 16 permutations for SST

Well there are also 16 for TSS since it's basically the same thing but just mirrored.

So that gives a total number of permutations of 16 + 16 = 32

However there's duplication in there if we think about it.

The SS tiles will either consist of two vertical tiles or two horizontal tiles.

When it consists of the two vertical tiles, well then our total floor (SST) will now be three vertical tiles. So imagine when we have 3 black vertical tiles.

In that case the SST and the TSS will be the same BB B = B BB

it'll also we the same when we have 1 black followed by 2 whites

e.g. BW B = B WB


In fact it'll be the same for all permutations where we have 3 vertical tiles

So, how many ways is that. Well since there are three tiles and each of them can be one of either 2 colours then the total number of permutations is equal to 2*2*2=8

this can also be written as 2^3=8
in this case you can see that the n was 3 so it's actually 2^n for this particular arrangement.

This numnber is subtracted from the total number of permutations.

Going from n=2 to n=3 is the first time that we can use the general rule and hence that's why the recurrance relation starts here. That's why the relation holds from n>=3

Hope that makes some sense


by the way, what's this for? Seems pretty challenging for secondary shool

karkar athlete

Brussels Sprout thanks a million, I kinda got it the first time there was just certain aspects I was unsure of, and thanks for the long a detailed answer very much appreciated.
Orginally I had 4(An-1) as my recurrence relation but I had worked out that it was wrong and all it was was the extra bit!!! :rolleyes: thats why I couldn't realise where the 2^n bit came from!
It is for college graded work we have to do .