# Counting on Fibonacci

Fibonacci numbers have all sorts of amazing properties and links to many different kinds of mathematics. They start off with 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, and continue on from there.

Given the first two numbers of the sequence, 0 and 1, each succeeding number is simply the sum of the previous two numbers.

Technically, you can describe the sequence in the following way:

F0 = 0, F1 = 1, and for n greater than 1, Fn = Fn–1 + Fn–2.

It’s possible to interpret Fibonacci numbers in combinatorial terms; in effect, by counting certain tilings. It turns out that a Fibonnaci number corresponds to the number of different ways in which you can tile a board of a given length and unit width with squares and dominoes.

For example, the number 4 can be expressed in terms of 1s and 2s in five ways: 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1, and 2 + 2.

This can be visualized as different square and domino tilings of a board 4 units long:

Here’s a table showing the number of different square and domino tilings possible for the first few positive integers.

 Integer PossibleTilings No.Tilings 1 1 1 2 11, 2 2 3 111, 12, 21 3 4 1111, 112, 121, 211,22 5 5 11111, 1112, 1121,1211, 122, 2111, 212, 221 8 6 111111, 111112, 11121, 11211, 1122, 12111, 1212, 1221, 21111, 2112, 2121, 2211, 222 13

Notice that the number of tilings for a given integer, n, is the Fibonacci number Fn+1.

In their book Proofs That Really Count, Arthur T. Benjamin of Harvey Mudd College and Jennifer J. Quinn of Occidental College use this link between Fibonacci numbers and tilings to provide ingenious combinatorial proofs of a wide variety of relationships involving Fibonacci numbers.

“Mathematics is the science of patterns,” Benjamin and Quinn write. “. . . the Fibonacci numbers exhibit many beautiful and surprising relationships.”

For example, suppose you sum the Fibonacci numbers. The first sum is 0 + 1 = 1. Then, 1 + 1 = 2, 2 + 2 = 4, 4 + 3 = 7, 7 + 5 = 12, 12 + 8 = 20, 20 + 13 = 33, and so on. Each successive sum is one less than a Fibonacci number.

It’s possible to use square and domino tilings to prove combinatorially that the sum of the first n Fibonacci numbers equals Fn+2 – 1.

Visualization and counting can play an important role in gaining insights into many aspects of mathematics. “Just count in the right way to get the proofs you need,” Benjamin says.