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

  • 1
    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.2010-12-27
  • 1
    The $f_n$ are Fibonacci numbers, or something else?2010-12-27
  • 0
    @J.M.: yes $f_{n} = F_{n+1}$.2010-12-27
  • 1
    Why not the rest of the questions? What is an $n$-board? What are your tiling pieces?2010-12-27

1 Answers 1

2

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