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 𝑛-bracelet. So we need to decompose a tiling of an 𝑛-board to a tiling of an n−1-board or a tiling of an n−1-bracelet?

omvamen71

omvamen71

Answered question

2022-10-02

Show that f n 1 + L n = 2 f 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 𝑛-bracelet.
So we need to decompose a tiling of an 𝑛-board to a tiling of an n 1-board or a tiling of an n 1-bracelet?

Answer & Explanation

Marshall Horne

Marshall Horne

Beginner2022-10-03Added 8 answers

f n denotes number of tilings of the n × 1 board by 2 × 1 and 1 × 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.
The above gives a combinatorial interpretation of Fibonacci and Lucas numbers, since f n = F n + 1 and l n = L n .
Domianpv

Domianpv

Beginner2022-10-04Added 2 answers

Your identity is equivalent to L n = 2 f 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.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?