Give a rectangle of width W and height 2*H-1.How many ways we can fill the rectangle with 1 x H tiles?

How to find reccurence relation for this type of problems.(This problems is from Topcoder TCO 2014)

Example :H=2 W=4 Ans=11

Give a rectangle of width W and height 2*H-1.How many ways we can fill the rectangle with 1 x H tiles?

How to find reccurence relation for this type of problems.(This problems is from Topcoder TCO 2014)

Example :H=2 W=4 Ans=11

W must be multiple of H else the answer is 0.

consider the 2*H-1 dimension as line:

- size of a domino tile in that one line is either 1 or H
- there can fit only one H sized piece in that line
- next (H-1) lines must have 1s on the exact places as this line

Can you piece it together now or should I go on?