2
$\begingroup$

Show that $f_{n-1} + L_n = 2f_{n}$.

So we need to find a $2$ to $1$ correspondence.

Set 1: Tilings an $n$-board.

Set 2: Tiling of an $n-1$-board or tiling of an $n$-bracelet.

So we need to decompose a tiling of an $n$-board to a tiling of an $n-1$-board or a tiling of an $n-1$-bracelet?

Source: Proofs that Really Count by Art Benjamin and Jennifer Quinn

$\endgroup$
  • 1
    $\begingroup$ Clarifications: What is a $n$-board? Is it a $n \times 2$ board? What are your tiling pieces? Are they dominoes and $2 \times 2$ squares? What is $f_n$? The number of ways to tile a $n \times 2$ board with dominoes and squares? A previous question you asked leads me to believe this. These clarifications may allow more people to answer your question. $\endgroup$ – TNi Dec 27 '10 at 16:14
  • 1
    $\begingroup$ The $f_n$ are Fibonacci numbers, or something else? $\endgroup$ – J. M. is a poor mathematician Dec 27 '10 at 16:28
  • $\begingroup$ @J.M.: yes $f_{n} = F_{n+1}$. $\endgroup$ – PrimeNumber Dec 27 '10 at 16:32
  • 1
    $\begingroup$ Why not the rest of the questions? What is an $n$-board? What are your tiling pieces? $\endgroup$ – Arturo Magidin Dec 27 '10 at 23:06
2
$\begingroup$

I think I'll first add the missing context from the book Proofs that Really Count by Arthur T. Benjamin, Jennifer J. Quinn.

$f_n$ denotes number of tilings of the $n\times 1$ board by $2\times 1$ and $1\times 1$ pieces.

$l_n$ is almost the same thing, but the ends of the board is joined so that they form a kind of "bracelet" (i.e., one domino can cover the first and the last position; since they are adjacent now.) Also it should be mentioned that the position where the ends are glued together is fixed. (By this I mean that if one tiling is obtained from another one by rotation, they are not necessary considered equal.)

(These are not exact quotes from the book, but I hope that I explained this clearly enough.)

The above gives a combinatorial interpretation of Fibonacci and Lucas numbers, since $f_n=F_{n+1}$ and $l_n=L_n$.


Your identity is equivalent to $L_n=2f_n-f_{n-1}=f_n+f_{n-2}$ (using $f_n-f_{n-1}=f_{n-2}$). A combinatorial proof of this identity is easy (and it is given in the book you quote as identity 32).

Basically the same proof, just formulated another way, is rewriting the identity as $f_n-f_{n-1}=L_n-f_n$ and to check that both expressions are equal to the number of tilings of $(n-2)$-board.

But I guess this is not what you're looking for, since this proof is essentially the same as the proof given in the book you mention in your question

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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