There is a rectangular plot of size 1×n. This has to be covered by three types of tiles - red, blue and black. The red tiles are of size 1×1, the blue tiles are of size 1×1 and the black tiles are of size 1×2. Let tn denote the number of ways this can be done. For example, clearly t1=2 because we can have either a red or a blue tile. Also t2=5 since we could have tiled the plot as: two red tiles, two blue tiles, a red tile on the left and a blue tile on the right, a blue tile on the left and a red tile on the right, or a single black tile.
[*]Prove that t2n+1=tn(tn−1+tn+1) for all n>1.[*]Prove that tn=∑d≥0(dn−d)2n−2d for all n>0.Here,
(rm)=⎩⎨⎧r!(m−r)!m!,0, if 0≤r≤m, otherwise
for integers m,r. combinatoricsgridsbinomial coefficientsinduction