P4.11.9 Following Exercise 4.11.7, we can consider the number f(n) of perfect matchings in a 3 x 2n grid graph, which is the same as the number of ways to tile a 3 x 2n rectangle with 1 x 2 dominoes. (a) Prove that f(0) = 1, f(1) = 3, and that for positive n, f(n) = 3f(n 1) +2f(n 2) + ... +2f(0) ). (b) Prove (probably using the formula in (a)) that for n > 1, f(n) = 4f(n-1) - f(n-2). (c) Prove by induction (probably using the formula in (b)) that for all naturals n, f(n) = ((1+1/V3)(2+ V3") + (1 - 1/V3)(2 - V3)"))/2. (d) Using any of these formulas, find f(n) for all n with n