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!
 A: 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)$.
