we can consider the number f(n) of perfect matchings in a 3 2n grid graph, which...

 

Transcribed Image Text:

we can consider the number f(n) of perfect matchings in a 3 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, (1) = 3, and that for positive n, f(n) = 3f(n 1) + 2 (n 2) + + 2 f (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/3)(2 + 3) + (1 1/3)(2-3)n 2 we can consider the number f(n) of perfect matchings in a 3 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, (1) = 3, and that for positive n, f(n) = 3f(n 1) + 2 (n 2) + + 2 f (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/3)(2 + 3) + (1 1/3)(2-3)n 2