ISL 1988 Problem 50

Prove that the numbers $A,B$ and $C$ are equal, where:

• $A=$ number of ways that we can cover a $2 \times n$ rectangle with $2 \times 1$ retangles.

• $B=$ number of sequences of ones and twos that add up to $n$

• $C= \sum^m_{k=0} \binom{m + k}{2 \cdot k}$ if $n = 2 \cdot m,$ and

• $C= \sum^m_{k=0} \binom{m + k + 1}{2 \cdot k + 1}$ if $n = 2 \cdot m + 1.$