MathDB

There is a rectangular plot of size

1 \times n

. This has to be covered by three types of tiles - red, blue and black. The red tiles are of size

1 \times 1

, the blue tiles are of size

1 \times 1

and the black tiles are of size

1 \times 2

. Let

t_n

denote the number of ways this can be done. For example, clearly

t_1 = 2

because we can have either a red or a blue tile. Also

t_2 = 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

t_{2n+1} = t_n(t_{n-1} + t_{n+1})

for all

n > 1

.
[*]Prove that

t_n = \sum_{d \ge 0} \binom{n-d}{d}2^{n-2d}

for all

n >0

.
Here,

\binom{m}{r} = \begin{cases} \dfrac{m!}{r!(m-r)!}, &\text{ if $0 \le r \le m$,} \\ 0, &\text{ otherwise} \end{cases}

for integers

m,r

Problem Statement