F(k) F(k-2) = F(k-1)^2 + (-1)^k ?
Let's start by giving combinatorial interpretations of F(k) F(k-2) and F(k-1)^2.
The factor F(k) on the left hand side counts all the perfect matchings of the 2-by-k grid-graph, while the factor F(k-2) counts all the perfect matchings of the 2-by-(k-2) grid-graph. Let's imagine that the 2-by-(k-2) grid-graph in question is just the 2-by-k grid-graph with its left and right vertices and edges chopped off. Then the product F(k) F(k-2) counts all the ways to choose red edges and blue edges in the 2-by-k grid-graph so that every vertex belongs to exactly one red edge (coming from a matching of the 2-by-k grid-graph) and every vertex EXCEPT the four outer vertices belongs to exactly one blue edge (coming from a matching of the concentric 2-by-(k-2) grid-graph).
The red and blue edes, taken together, form DOUBLED EDGES (where the same edge has been chosen twice), ALTERNATING CYCLES (where red and blue edges alternate in a closed loop), and ALTERNATING PATHS (where red and blue edges alternate in a path that joins one of the four outer vertices to another one of the four outer vertices). For instance, if we superimpose the red matching
o o----o o o
| | |
| | |
o o----o o o
of the 2-by-5 grid with the blue matching
o o o
| | |
| | |
o o o
of the 2-by-3 grid, we get
o o----o o o
| | | # |
| | | # |
o o----o o o
where "#" is used to represent a doubled edge.
If we are color-blind, we can reconstruct the coloring of the doubled edges and of the alternating paths, but NOT of the alternating cycles; each of them can be colored in two different ways. So for a color-blind person, an ambiguity factor of 2^c is introduced, where c is the number of cycles in the graph obtained by superimposing the two matchings. (In the above example, c=1.)
Likewise, F(k-1)^2 counts ways of superimposing matchings of two graphs: one of the graphs is obtained from the 2-by-k grid-graph by deleting the rightmost edge and its two vertices, and the other is obtained from the 2-by-k grid-graph by deleting the leftmost edge and its two vertices. For instance, if we superimpose the matching
o o----o o
| |
| |
o o----o o
of the (left-justified) 2-by-4 grid with the matching
o o o o
| | | |
| | | |
o o o o
of the (right-justified) 2-by-4 grid, we get
o o----o o o
| | | # |
| | | # |
o o----o o o .
Once again, if we are color-blind, we can reconstruct the coloring of the doubled edges and of the alternating paths, but NOT of the alternating cycles; each of them can be colored in two different ways. So for a color-blind person, an ambiguity factor of 2^c is introduced, as before.
In each case, the objects we get when we superimpose two matchings are graphs ("multigraphs", actually, since it's permitted for an edge to appear twice) in which each vertex in the interior gets paired up twice and each of the four outer vertices gets paired up once. And in both situations, the ambiguity factor (which measures how many different pairs of matchings give a particular multigraph with c cycles) is the same: 2^c.
Now, if everything I've just told you were strictly true, I would've proved that F(k) F(k-2) = F(k-1)^2. But I told a lie: The correspondence between the multigraphs and the pairs of matchings isn't exact (even when the ambiguity factor of 2^c is taken into account).
Note that when the matching
o----o o----o
o----o o----o
of the (left-justified) 2-by-4 grid is superimposed with the matching
o----o o----o
o----o o----o
of the (right-justified) 2-by-4 grid, we get
o----o----o----o----o
o----o----o----o----o
which cannot be split apart into a matching of the 2-by-5 grid-graph
and the 2-by-3 grid-graph. But (I leave it to you to verify this!)
the all-horizontal case is the ONLY exception to the claim I made
in the case n=5. That's why F(5) F(3) is equal to F(4)^2 - 1 ,
not F(4)^2.
More generally, whenver k is odd, F(k) F(k-2) = F(k-1)^2 - 1.
For a similar reason, whenver k is even, F(k) F(k-2) = F(k-1)^2 + 1.