MA375: Solution to a homework problem from this week or last week's homework
Spring 2009, Prof. Walther
7.1
42. How many ways can a 2 x n board be filled by tiles two squares in size?
a) To solve this problem, divide how you can place the upper right dominoe into two cases
Case 1: Vertical-if you place a vertical tile in the upper right of the board, you can only place another vertical tile on the left to fill up the open space. After doing this, you have a 2 x (n-2) space to fill. (a_n-2)
Case 2: Horizontal-if you place a horizontal tile at the top of the board, you are left with a 2 x (n-1) space to fill. (a_n-1)
Adding these two cases, we find: a_n = a_n-1 + a_n-2
b) There is one way to fill a 2 x 1 board with a 2 square tile, so a1 = 1. A 2 x 2 board can be filled with two horizontal tiles or two vertical tiles, so a2 = 2.
c) To find a17 just repeat the recursion, starting with the initial conditions, until a17 = a16 + a15 is reached.
