Tiling a One-Dimensional Rectangle

The number of ways of tiling rectangle with and tiles is for the Fibonacci Sequence. This has generating function

and

Proof

First bit by having the same recurrence relation. Note that is the generating function for tiling with precisely tiles So:

Thus the generating function is:

Theorem

Proof

Count tillings with tiles.