Ivars Peterson's MathTrek
May 3, 2004
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 = Fn1 + Fn2.
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||Possible Tilings||No. Tilings|
|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 the 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.
Copyright © 2004 by Ivars Peterson
Benjamin, A.T. 2004. Counting on Fibonacci numbers. Gathering for Gardner (G4G6). March 26. Atlanta, Ga.
Benjamin, A.T., and J.J. Quinn. 2003. Proofs That Really Count: The Art of Combinatorial Proof. Washington, D.C.: Mathematical Association of America.
Peterson, I. 2002. A Fibonacci fountain. MAA Online (Oct. 21).
______. 2002. Stepping beyond Fibonacci numbers. MAA Online (Sept. 30).
You can learn more of the amazing properties of Fibonacci numbers at http://mathworld.wolfram.com/FibonacciNumber.html.
Comments are welcome. Please send messages to Ivars Peterson at firstname.lastname@example.org.
A collection of Ivars Peterson's early MathTrek articles, updated and illustrated, is now available as the Mathematical Association of America (MAA) book Mathematical Treks: From Surreal Numbers to Magic Circles. See http://www.maa.org/pubs/books/mtr.html.