(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 gridA 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 gridLet 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

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) gridNote 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.