Q:

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

A:

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.

