# Another Bijective proof for Fibonacci Identities

I'm going through a past exam, and this question popped up:

Prove:

$3P_n = P_{n-2} + P_{n+2},\,n>2$

Where $\tilde{P}_j = \{\textrm{monomer-dimer pavings on a } 1\times j \textrm{ board}\}$ and $|\tilde{P}_{j}| = P_{j} = F_{j+1}$. My problem is: What set (call it $A$ such that $|A|=3$) do I use, such that:

$|A\times\tilde{P}_{n}| = |A||\tilde{P}_{n}| = 3P_n$? I could use [3], but a Bijection is far from obvious!

-
Is [3] a reference you forgot to copy? –  Hendrik Jan Nov 8 '12 at 21:57
@Hendrik: No, $[n]$ is a common notation for $\{1,\dots,n\}$ in combinatorial contexts. –  Brian M. Scott Nov 8 '12 at 22:48
You are right. Silly me. I understand $[n]$ that way, with variable $n$, but automatically read $[3]$ in a totally different way. Thanks. –  Hendrik Jan Nov 8 '12 at 23:15
It seems curious to ask for a combinatorial proof of this relation, which is not obvious at all. However it follows easily from the recurrence: $$P_{n+2}+P_{n-2}=P_{n+1}+P_n+P_{n-2}=(P_n+P_{n-1})+P_n+P_{n-2} = 3 P_n.$$ You can turn this into a bijection, but it is a bit artificial. Given a paving of either $1\times(n+2)$ or of $1\times(n-2)$, find a paving of $1\times n$ and a number $i\in\{1,2,3\}$ as follows. If the paving was of $1\times(n+2)$, and the last two squares form a sub-paving, then we get a paving of $1\times n$ by removing them, and set $i$ to the number of tiles ($1$ or $2$) used for the final two squares. We are left with the cases of a paving of $1\times(n+2)$ that ends with $(2,1)$ or any paving of $1\times(n-2)$; we set $i=3$ for those cases, and pave $1\times n$ by replacing the $(2,1)$ by $(1)$ in the former case or by adding a dimer $(2)$ in the latter case. One checks that for any given paving of $1\times n$ and $i\in\{1,2,3\}$ one uniquely reconstructs a paving of either $1\times(n+2)$ or of $1\times(n-2)$.