# Running the Fibonacci recurrence backward

When you run the Fibonacci recurrence backward, you get Fibonacci numbers again, some with minus signs:

...,-8,5,-3,2,-1,1,0,1,1,2,3,5,8,..

(This symmetry is called the reciprocity property of the Fibonacci sequence.)

Why should this property hold?

One good answer to this question comes from using a COMBINATORIAL INTERPRETATION of the Fibonacci numbers. Specifically, the nth term of the sequence 1,2,3,5,8,... is the number of "perfect matchings" (see below) of the "2-by-n grid-graph" (shown in Figure 1 in the case n=5). The 10 o's are called VERTICES and the 13 line segments that connect them are called EDGES. Vertices that share an edge are ADJACENT.

```                          o----o----o----o----o
|    |    |    |    |
|    |    |    |    |
o----o----o----o----o

Figure 1: The 2-by-5 grid
```
A perfect matching of a graph is a way of pairing up each vertex with an adjacent vertex so that each vertex gets paired up with exactly one of its neighbors. Equivalently, a perfect matching of a graph is a subset of the set of edges of the graph with the property that every vertex of the graph belongs to one and only one of the chosen edges. Figure 2 shows one of the 8 perfect matchings of the 2-by-5 square grid.
```                          o    o----o    o    o
|              |    |
|              |    |
o    o----o    o    o

Figure 2: A perfect matching of the 2-by-5 grid
```
Let M(n) denote the number of perfect matchings of the 2-by-n grid. (From now on, we'll leave out the word "perfect" and just call them "matchings".) The numbers M(n) satisfy the recurrence relation
M(n) = M(n-1)+M(n-2)
on account of the fact that the matchings of the 2-by-n grid can be divided into two nonoverlapping classes --- those that contain the rightmost vertical edge and those that don't --- and that the matchings in the first class are just matchings of the 2-by-(n-1) grid (with an extra vertical edge added on the right) while the matchings in the second class are just matchings of the 2-by-(n-2) grid (with two extra horizontal edge added on the right).

It turns out that this relationship between Fibonacci numbers and matchings of 2-by-n grid-graphs can be extended to the case when n is negative, and this is the key to understanding the reciprocity phenomenon.

But what does it mean to speak of a 2-by-n grid when n is negative?

The meta-strategy to use here is the same one that leads one to reinvent the definition of 0! as 1, or a^(-3) as 1/a^3: "To define f(0), f(-1), f(-2), etc., figure out a rule for getting from f(n) to f(n-1), and then iterate it as many times as you can."

In our situation, note that the 2-by-n grid (with vertices at (i,j) for i=1 to n and j=1 to 2) can be reduced to the 2-by-(n-1) grid by removing two vertices ((n,1) and (n,2)) and three edges (the vertical edge (n,1)<->(n,2) and the horizontal edges (n,1)<->(n-1,1) and (n,2)<->(n-1,2)). At least, this works when n is 2 or greater. But when n is 1, the prescription asks us to remove edges that aren't there! More specifically, we get a bogus graph with horizontal "anti-edges" (1,1)<->(0,1) and (1,2)<->(0,2) and no vertices at all!

But it turns out that there is a very natural way to extend the theory of matchings of graphs into this enlarged universe of graphs with anti-vertices and anti-edges, and that in this new setting, one can say that (for instance) the 2-by-(-7) grid has -8 matchings. Or rather, the 2-by-(-7) grid has 8 matchings, each of which counts as an "anti-matching".

A typical anti-matching of the 2-by-(-7) grid is shown in Figure 3.

```                 ****x    x    x****x    x    x    x****
*              *    *
*              *    *
****x    x    x****x    x    x    x****

Figure 2: A anti-matching of the 2-by-(-7) grid
```
Note that this is just the matching of the 2-by-5 graph that was shown in Figure 2, with some extra horizontal edges added at the left and right sides. (Vertices have been replaced by anti-vertices, marked with an x, and edges have been replaced by anti-edges, marked with *'s.)

This is true quite generally: For any positive integer n, the matchings of the 2-by-(-n) grid (if we ignore the issue of whether they count as "plus" matchings or "minus" matchings) are in one-to-one correspondence with the (ordinary) matchings of the 2-by-(n-2) grid. And this (when all the details are filled in) gives us a satisfying way to understand the reciprocity property of the Fibonacci sequence.

For more of the nitty-gritty details, see my recent article A reciprocity theorem for domino tilings.

On the other hand, to get behind those nitty-gritty details to see what's REALLY going on, click here.