Discrete Math - Proof by Strong Induction

[2] Tiling Recall the Fibonacci numbers defined in Lecture If we instead define 91 = 1, 92 = 1 and In = 9n-1 + 29n-2 for n 2 3 we will get a different sequence of numbers (due to the different recurrence.) What's neat about this new sequence of numbers is that it can be used to "count" different tilings of a 2-by-n grid. Let me explain further. Suppose you are given a 2-by-n grid that you must tile, using either 1-by-2 dominoes or 2-by-2 squares. The dominoes can be arranged either vertically or horizontally, but they may not overlap, they may not "hang off the board, and they must cover every square of the grid. (See Figure below.) 00 (b) The five ways to tile the n =4 grid using dominoes. 00 (a) The empty 2-by-n grid, plus the 1-by-2 domino (in both orientations) (c) The six additional tilings for the n = 4 grid when we and the 2-by-2 square. also allow the use of the square tiles. Prove by strong induction on n that the number of different ways of tiling the 2-by-n grid for any n 2 1 is precisely gn+1. (Be careful: it's easy to accidentally count some configurations twice for example, make sure that you count only once the tiling of a 2-by-3 grid that uses three horizontal dominoes.) Hint: Try out some examples before trying to prove the result. Look at the figure above. Hint: Use the 7-step process used in Lectures (for strong induction)