Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I would appreciate if somebody could help me with the following problem

Q: Show that (for $k,n\in \mathbb{N}$), if $f_1=f_2=1$, $f_{n+2}=f_{n+1}+f_n$, then $$f_{2k-1}f_{4k}=f_{2k}+f_{2k}f_{4k-1}.$$

share|improve this question
add comment

1 Answer

$F_n$ is the number of ways to tile a $1\times(n-1)$ board using only $1\times 1$ and $1\times 2$ tiles (squares and dominoes, respectively). Thus, $F_{2k-1}F_{4k}$ is the number of ways to tile a $1\times(2k-2)$ and a $1\times(4k-1)$ board independently. Similarly, $F_{2k}F_{4k-1}$ is the number of ways independently to tile a $1\times(2k-1)$ and a $1\times(4k-2)$ board.

I will use an argument similar to the one used here to prove the related Cassini’s identity, and I will use the same terminology. Start with a $1\times(4k-1)$ board and a $1\times(2k-2)$ board. Place the shorter board below the longer one in such a way that its first cell is immediately below the second cell of the longer board; its last cell is below the $(2k-1)$-st cell of the longer board. If there is a fault line (see the link for this terminology) after any of the first $2k-1$ cells of the longer board, find the last (rightmost) one, and interchange the parts of the top and bottom boards that are to the left of the fault line. After this interchange, the top board will be $1\times(4k-2)$, the bottom board will be $1\times(2k-1)$, and both boards will be properly tiled. Thus, each tiling of the $1\times(4k-1)$ and $1\times(2k-2)$ boards that has a fault line gives rise to a unique tiling of the $1\times(4k-2)$ and $1\times(2k-1)$ boards, also with a fault line.

Clearly this correspondence is reversible: each tiling of the $1\times(4k-2)$ and $1\times(2k-1)$ boards that has a fault line gives rise to a unique tiling of the $1\times(4k-1)$ and $1\times(2k-2)$ boards, also with a fault line. I claim that every tiling of the $1\times(4k-2)$ and $1\times(2k-1)$ boards has a fault line. Suppose that a tiling of these boards has no fault line strictly to the left of the righthand end of the lower ($1\times(2k-1)$) board. Then the first tile of the lower board must be a domino. Working across from left to right, we see that the first $k-1$ tiles of the lower board and the first $k-1$ tiles of the upper board must all be dominoes. But then the last tile of the lower board must be a square, and there is a fault line at the righthand end of the lower board. Thus, each of the $F_{2k}F_{4k-1}$ tilings of the $1\times(4k-2)$ and $1\times(2k-1)$ boards has a fault line, and there are therefore $F_{2k}F_{4k-1}$ tilings of the $1\times(4k-1)$ and $1\times(2k-2)$ boards that have a fault line.

Finally, suppose that we have a tiling of the $1\times(4k-1)$ and $1\times(2k-2)$ boards that does not have a fault line. This is possible only if the first $k$ tiles of the longer board and all $k-1$ tiles of the shorter board are dominoes. The last (leftmost) $2k-1$ cells of the longer board can be tiled in $F_{2k}$ ways, so there are $F_{2k}$ of these tilings that have no fault line.

Combining results, we see that on the one hand there are $F_{2k-1}F_{4k}$ tilings of the $1\times(4k-1)$ and $1\times(2k-2)$ boards, and on the other hand there are $F_{2k}F_{4k-1}$ tilings of them with and $F_{2k}$ without fault lines, so $F_{2k-1}F_{4k}=F_{2k}F_{4k-1}+F_{2k}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.