Confirming your payment

Skip to content

Practice Questions · Question 32 of 36

A garden path is 1 unit wide and n units long.

Question 325 marksMedium

A garden path is 1 unit wide and nn units long. It is covered with square tiles (1×11 \times 1) and rectangular tiles (1×21 \times 2). The square tiles are all grey; each rectangular tile can be red or blue. Let tnt_n be the number of different ways to cover a path of length nn. Then t1=1t_1 = 1 and t2=3t_2 = 3, as the figure shows for length 2.

A path of length 2 tiled in three ways: two square tiles; one red rectangular tile; one blue rectangular tile

(a) Explain why tn=tn−1+2tn−2t_n = t_{n-1} + 2t_{n-2} for n≥3n \ge 3.

(b) Find t3t_3, t4t_4, t5t_5, t6t_6 and t7t_7.

(c) Show that tn=2n+1+(−1)n3t_n = \frac{2^{n+1} + (-1)^n}{3} gives t1t_1 and t2t_2 and obeys the rule in (a).

(d) Find t10t_{10}.

(e) Show that tn+tn+1=2n+1t_n + t_{n+1} = 2^{n+1}. What kind of sequence do the sums t1+t2t_1 + t_2, t2+t3t_2 + t_3, t3+t4t_3 + t_4, … form?