P4.11.9 (20 pts) Problem: 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