MathDB

For any natural number

n

, consider a

1\times n

rectangular board made up of

n

unit squares. This is covered by

3

types of tiles :

1\times 1

red tile,

1\times 1

green tile and

1\times 2

domino. (For example, we can have

5

types of tiling when

n=2

: red-red ; red-green ; green-red ; green-green ; and blue.) Let

t_n

denote the number of ways of covering

1\times n

rectangular board by these

3

types of tiles. Prove that,

t_n

divides

t_{2n+1}

2