First homework
--------------
A matching of a graph is a (possibly empty) set of disjoint edges in the graph 
(i.e., no two edges in the set share a vertex).

There are 22 matchings of the 2-by-3 grid (including the empty matching):

o  o  o    o  o  o    o--o  o    o  o--o    o  o  o    o  o--o
                                 |          |  |       |
o  o  o    o  o--o    o--o  o    o  o  o    o  o  o    o  o--o


o--o  o    o  o  o    o--o  o    o  o  o    o  o  o    o  o  o
           |                     |          |     |    |  |  |
o  o  o    o  o  o    o  o--o    o  o--o    o  o  o    o  o  o


o  o--o    o  o  o    o  o--o    o--o  o    o  o  o
              |                        |       |  |
o  o  o    o  o  o    o--o  o    o  o  o    o  o  o


o  o  o    o  o  o    o  o--o    o  o  o    o--o  o
                 |                     |          |
o--o  o    o  o  o    o  o--o    o--o  o    o--o  o

Show that if we let a(n) denote the number of matchings of the 2-by-n grid,
the terms a(n) satisfy the recurrence
        a(n) = 3a(n-1) + a(n-2) - a(n-3)
or equivalently, show that the generating function sum_{n=0}^{infinity} a(n) t^n 
is the power series for the rational function (1-t)/(1-3t-t^2+t^3).