# Prove relation between Lucas and Fibonacci numbers using tilings

I struggle a lot with combinatorial proofs and was hoping for some help. I need to prove by strong induction that $L_n = F_{n-2} + F_n$ and how this shows that $L_n$ counts the tilings of the circular $n$-board with $1$- and $2$-tiles

EDIT ANSWER: Source is Proofs that Really Count: The Art of Combinatorial Proof By Arthur T. Benjamin, Jennifer J. Quinn

Lucas Numbers

• What have you tried? What recursion holds for $L_n$? Andwhat for $F_n$? Does the claim hold for a few small $n$? – Hagen von Eitzen May 5 '13 at 16:38
• I guess I could fumble my way through a proof of Ln holding true I guess I can't really wrap my head around what that has to do with tiles on a circular board. – Atom May 5 '13 at 16:43
• Some proofs write themselves. Suppose we know that for a specific $k$, we know that $L_k=F_k+E_{k-2}$ and $L_{k+1}=F_{k+1}+F_{k-1}$. What can we conclude about $L_{k+2}$? – André Nicolas May 5 '13 at 16:43
• Ah, it would be Lk = Fk+2 + Fk, i'm also guessing the + 2 accounts for the 2 tilings and the k for the regular tilings? – Atom May 5 '13 at 16:46
• About tiles on a circular board, have you done, in class or as part of earlier homework, a problem about expressing $n$ as a sum of $1$'s and/or $2$'s? Or something similar? Fibonacci numbers come up. And yes, you "add" the two equations I gave, then it is one sentence more. – André Nicolas May 5 '13 at 16:50

The induction argument is very straightforward. For the combinatorial part, label the cells of the circular $n$-board $1,2,\dots,n$, and consider any tiling of that board. There are two possibilities: there is a tile occupying cells $n$ and $1$, or there is no such tile. If there is no such tile, you can break the tiling open between cells $n$ and $1$ to get a tiling of an $n$-strip. If there is such a tile, break the tiling open between cells $n-1$ and $n$ and between $1$ and $2$ to get a tiling of the $(n-2)$-strip.