\problemdata                                                             
        {Counting Dominoes} % latex-friendly label for the prob.
        {Recurrences, Counting} % The topic(s) of the problem content.  
        { Knuth, Concrete Mathematics, Chapter 7.} % Source (if known)                                          
        {S01 Tutorial 9, 2} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
How many ways are there to completely cover a $2 \cross n$ rectangle with 
(indistinguishable) $2 \cross 1$ dominoes? 

\solution{
Let $T(n)$ be the number of tilings for a $2 \cross n$ rectangle.  Clearly,
$T(0) = T(1) = 1$ .  There are two possibilities for tiling the left edge of
the rectangle --- we put either a vertical domino or two horizontal dominoes
there.  If we choose a vertical one, the remaining $2 \cross (n-1)$ rectangle
can be covered in $T(n-1)$ ways.  If we choose two horizontals, the rectangle
can be completed in $T(n-2)$ ways.  Thus, $T(n) = T(n-1) + T(n-2)$.  This is
just the Fibonacci sequence shifted up one place:
\[T(n) = F_{n+1}\ \mathrm{for}\ n \geq 0.\]
}
\end{problem}
                                 