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

  • $\begingroup$ What have you tried? What recursion holds for $L_n$? Andwhat for $F_n$? Does the claim hold for a few small $n$? $\endgroup$ May 5 '13 at 16:38
  • $\begingroup$ 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. $\endgroup$
    – Atom
    May 5 '13 at 16:43
  • $\begingroup$ 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}$? $\endgroup$ May 5 '13 at 16:43
  • $\begingroup$ 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? $\endgroup$
    – Atom
    May 5 '13 at 16:46
  • $\begingroup$ 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. $\endgroup$ 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.


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.