[ 2 ] (16 pts.) Tiling Recall the Fibonacci numbers defined in Lecture 8. If we instead define 91 = 1,92 = 1 and In = 9n-1 + 2gn-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 00 0000 (b) The five ways to tile the n =4 grid using dominoes. 00 (a) The empty 2-by-# grid, plus the 1-by-2 domino (in both orientations) and the 2-by-2 square. (c) The six additional tilings for the n = 4 grid when we 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 ga+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 8, 10, and Tutorial 5 (for strong induction). There are also some Puzzlers relating to tiling that may or may not be helpful. Theorem 5.5 (Prime Factorization Theorem) strong Let n E Z21 be a positive integer. Then there exist k 2 0 prime numbers p1, P2. ..., PR such induction! that n = [1/ pi. Furthermore, up to reordering, the primes prop2.... PR are unique. ex. n=8 = 2-2-2-2 n=66 = 3-2 .11 Step 0: State the (infinite set of) statements you want to prove for all ne 1, we want to show that there exists ( 2 0 prime numbers P,, Py ..; P, such that n = II_ pStep 1: State your P(n) for any n 2 1 , let P(n) be the property that there exists ( 2 0 prime numbers ,, Py ."., P, such that n = II,_, P; WTS P(n) is true Vn z _1 by strong induction on n. Step 2: State & prove your base case. . As a base case, consider when n= _1 . We will show that P(_) is true. Step 3: State your induction hypothesis. . For the IH, suppose (hypothetically) that P(1), P(2), .., P(k) are true for some ka there exists ( 2 0 prime numbers p,, P2. .", P, such that k' = II,-1 Pi Step 4: State your inductive assertion. We want to prove P(k+1) is true, using the (hypothetical) induction assumptions, i.e. prove that: there exists ( 2 0 prime numbers p,, P2. .-, P, such that k+1 = II,] Step 5: Prove the inductive step. . The proof that P(k+1) is true is as follows: Step 6: Conclusion. . The steps above showed that for any k2_ if P(1), P(2), .., P(k) are true, then P(k+1) is also true. Combined with the BC, which shows P(_) is true, we've shown P(n) is true for all na_