Yu Xiao

In the previous two articles, we’ve talked about how the Fibonacci numbers represent the number of ways to tile a board with squares and dominoes, and how we may explain interesting Fibonacci properties using visual proofs. In fact, there are many more sequences hidden in the patterns squares and dominoes, such as the Lucas numbers 2, 1, 3, 4, 7, …

Recall that we tile a straight board with squares and dominoes to get the Fibonacci numbers. What if instead we tile a circular bracelet with squares and dominoes that can be bent?

Let’s call a bracelet of length n an “n-bracelet.” There is still only 1 way to tile a 1-bracelet: with one square. However, there are 3 ways to tile a 2-bracelet. We may use two squares or one domino, but the domino can be placed in two different orientations, as shown in Figure 1.

Let l_n be the number of ways to tile an n-bracelet with squares (length 1) and dominoes (length 2). Then the first few values are l₁ = 1, l₂ = 3, l₃ = 4, l₄ = 7, as shown in the figure below. Note that in the l₃ row, even though the last three tilings are just rotations of each other, we still count them as three separate tilings. 

1, 3, 4, 7, … these are the Lucas numbers! How exciting that tilings with squares and dominoes coincide with two significant sequences – and just like the Fibonacci numbers, we obtain the next Lucas number from the sum of the previous two: L_n = L_n-1 + L_n-2. The difference is that Lucas numbers start with L₀ = 2 and L₁ = 1, whilst the Fibonacci numbers start with F₀ = 1 and F₁ = 1.

Like their more famous counterparts, the Lucas numbers also have many applications in nature. For example, the n^th Lucas number is the closest integer to the n^th power of the golden ratio Φ=1.618… Calculate some of the values for yourself and see if you agree!

Now that we have discovered such similarities between the Fibonacci and Lucas numbers, can we derive a formula linking them together? Let’s start by numbering the cells of an n-bracelet from 1 to n. We start from the top of the bracelet, and go in a clockwise direction, as shown in Figure 2. 

What makes an n-bracelet different from an n-board is that we may cover cell 1 and cell n of the bracelet with one domino. If we do, then the tiling is referred to as “out-of-phase.” Otherwise, if cell 1 and cell n are covered by different tiles, then the tiling is “in-phase,” as shown in Figure 3.

Let’s first carefully prove that the number of tilings of an n-bracelet is the n^th Lucas number. The proof will be very similar to the proof introduced in the first article “Maths Proofs without words”. Our main task is to prove the recursive formula l_n = l_n-1 + l_n-2 for bracelets. Then, with the same starting values and recursive formula, all following terms of l_n will give the Lucas numbers.

Here is the proof: given an n-bracelet, we remove the last tile to get a shorter bracelet. ‘Last tile’ here refers to the last tile that does not cover cell 1. For example, an out-of-phase domino that covers cell n and cell 1 is not the last tile, but the tile before it is (covers cell n-1). 

If the last tile is a square, we can remove the square to get an (n-1)-bracelet. If the last tile is a domino, we can remove the domino to get an (n-2)-bracelet. [NB: this is also true if the last tile of an out-of-phase tiling is a domino – we remove the domino covering positions n-2 and n-1 but what remains is still of total length n-2, as shown in figure 4]. Note that such operations do not change the “phase” of the bracelet, so we can create all (n-1)-bracelets and (n-2)-bracelets, both in-phase and out-of-phase ones, from all the n-bracelets.

We can go in the reverse direction as well, adding a square or a domino at the end to create an n-bracelet from an (n-2)-bracelet or an (n-1)-bracelet. In this way, we have established a one-to-one correspondence between the set of all n-bracelets, and the set of all (n-2)-bracelets and (n-1)-bracelets. Therefore, we have l_n = l_n-1 + l_n-2 and the proof is complete.

Last but not least, here is a visual proof that combines board and bracelet tilings: 

The formula relating the Lucas and fibonacci numbers we want to prove is l_n = f_n + f_n-2. As shown in Figure 5, we start with an n-bracelet. If it’s in-phase, then we can cut the bracelet at the top, and uncurl it into a straight n-board. Comparing the indices on the bracelet and the board reveals how the bracelet is uncurled into the board. Otherwise, if the n-bracelet is out-of-phase, then we know that there is a domino that covers cell n and cell 1. Remove the domino, and uncurl the remaining bracelet into an (n-2)-board.

Of course, we can reverse the operations. For an n-board, we can connect the first and the last cell to make an in-phase n-bracelet. For an (n-2)-board, we add an extra domino and turn it into an out-of-phase n-bracelet. In this way, we have established a one-to-one correspondence between the set of all n-bracelets and the set of all (n-2)-boards and n-boards. Therefore, we may conclude that l_n = f_n + f_n-2.

Since the Fibonacci numbers begin at F₀, but the number of ways to tile a board starts at F₁, we must shift the indices by 1 to obtain our final formula: L_n = F_n+1 + F_n-1. This beautiful formula connects the two significant sequences.

Once again, there are many more things we can do… what happens if we have different colours of squares and dominoes? What about if we use tri-ominoes (length 3) or even longer tiles? What happens if we break the bracelets into different pieces and then regroup them into many short bracelets? In my opinion, learning visual proofs is just like playing with Legos: we have various blocks in our hands, we can break, connect, rotate – basically do anything we want to the blocks, and each operation gives us insight into a mathematical formula. I strongly encourage you to play with the squares and dominoes by yourself to see what you can discover…