Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
Thanks. I know what you mean about trying to form a combinatorial argument. –  user8603 Nov 8 '12 at 20:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.