Build a recurrence relation for the number of ways to tile a

Build a recurrence relation for the number of ways to tile a 2 times n board with vertical and horizontal dominoes. Explain how you came up with your recurrence. (Don\'t forget your initial conditions!)

Solution

Let a_n denote the number of ways to tile a 2xn board with vertical and horizontal dominoes

For a 2x1 tile we can only use a vertical domino

Hence,a_1=1

For 2x2 we can use 2 vertical domino or 2 horizontal domino,so 2 ways

Hence, a_2=2

For n>=2 ie 2xn board the number of ways is a_n

So now 2 ways to build a_n+1

Add a vertical tile to 2xn board which can be done at start or end ie 2 ways

Add two horizontal tiles to 2xn-1 board which is done at start or end in 2 ways

So recurrence relation is

a_{n+1}=2a_n+2a_{n-1}