Discrete mathematics problem concerning tiling with 3 sub questions.

Question

4. Let Tn be the number of ways of tiling a 2 × n rectangle using tiles of dimensions 1 × 2 or 2 × 2.

For example, the picture below shows one of the tilings counted by T12.

(i) Find (and justify!) a recurrence relation and initial conditions that Tn satisfies.

(ii) Use your result from part

(i) to prove that Tn = 2 n+1 + (−1)n 3 for all n > 1.

(iii) What is the smallest n for which Tn > 1000?

Answer 1

The recurrence relationship is developed by noting that

T₁ = 1 (1 1x2 tile aligned vertically),

T₂ contains 2 vertically aligned 1x2 tiles, 2 horizontally aligned 1x2 tile, or a 2x2 tile, so T₂ = 3

For T_n, n >= 3, if the last tiling is a vertical tile, then the 2x n-1 area before it has T_n-1 arrangements.

If the last tiling is either 2 horizontal 1x2 tiles or a 2x2 tile, the area before it is 2 x n-2 and has T_n-2 arrangements. Noting that the last tiling has 2 possibilities (2 1x2 or a 2x2),

T_n = T_n-1 + 2T_n-2

ii) The formula actually works for n >= 1. I will write it as T_n = (2ⁿ⁺¹+(-1)ⁿ)/3

For n = 1, (2ⁿ⁺¹+(-1)ⁿ)/3 = (2¹⁺¹+(-1)¹)/3 = (2²+(-1)¹)/3 = (4 + -1)/3 = 3/3 = 1 This matches T₁

For n = 2, (2ⁿ⁺¹+(-1)ⁿ)/3 = (2²⁺¹+(-1)²)/3 = (2³+(-1)²)/3 = (8 + 1)/3 = 9/3 = 3 This is T₂ from above

We assume true the formula T_k = (2^k+1+(-1)^k)/3 is true for k = n-1 and k = n-2. (Since we proved for 2 consecutive values, we can do this.)

Note that (-1)*(-1) = 1, so we can always multiply by this.

Then, T_n = T_n-1 + 2T_n-2 = (2^n-1+1+(-1)^n-1)/3 + 2 * (2^n-2+1+(-1)^n-2)/3 =

(2^n-+(-1)^n-1 + 2*2^n-1 + 2*(-1)^n-2)/3 =

(2^n-+ 2^n-1+1 + (-1)*(-1)*(-1)^n-1 + 2*(-1)*(-1)*(-1)^n-2)/3 =

(2^n-+ 2ⁿ + (-1)*(-1)ⁿ + 2*(-1)ⁿ)/3 =

(2 * 2ⁿ + (-1+2)*(-1)ⁿ)/3 =

(2ⁿ⁺¹ + (-1)ⁿ)/3 This is what we are trying to prove.

As the second part of this equation is ± 1/3, we can determine n from the remainder of the equation and check that we aren't at the margin.

2ⁿ⁺¹ /3 > 1000

2ⁿ⁺¹ > 3000

n = ln(3000)/ln(2) - 1

n = 10.55

n = 11

Clearly, based upon how far n is from 10 and 11, the margin will not be an issue, but we verify.

T₁₁ = (2¹¹⁺¹ + (-1)¹¹)/3 = (2¹² + (-1)¹¹)/3 = (4096 - 1)/3 = 1365

T₁₀ = (2¹⁰⁺¹ + (-1)¹⁰)/3 = (2¹¹ + (-1)¹⁰)/3 = (2048 + 1)/3 = 683

n = 11