It is often said that mathematics is universal; one of my greatest joys, both as a parent and as a professor, is finding interesting and novel ways to illustrate various concepts. Over the past few years I’ve been fortunate to work with many great SMALL students on projects related to Zeckendorf’s theorem, which says that if we define the Fibonacci numbers by F_1 = 1, F_2 = 2 and F_{n+1} = F_n + F_{n-1} then every positive integer can be written uniquely as a sum of non-adjacent integers. The standard proof is through the greedy algorithm, though my students and I have had enormous success with a more combinatorial approach. It turns out that this is the first of many **equivalent** definitions of the Fibonacci numbers; we’ll see another one shortly.

Studying this and related problems has led me to examining many properties of the Fibonaccis. The following result is well-known, but I hope you’ll enjoy the method of proof. Annoyingly, for this result we must set f_1 = 1, f_2 = 1 and f_{n+1} = f_n + f_{n-1} (if we had two 1’s we of course could not have a unique decomposition for all numbers).

**Theorem: The sum of the squares of the first n Fibonacci numbers is the product of the n-th and (n+1)-st Fibonacci numbers. In other words, f_1^2 + … + f_n^2 = f_n * f_{n+1}.**

A beautiful way to prove this is through the Fibonacci spiral, which provides our **third** equivalent definition for the Fibonaccis. We start with a 1×1 square. We place another 1×1 square along a side, forming a 2×1 rectangle. We now place a 2×2 square next to that, forming a 3×2 rectangle. We now add a 3×3 square, giving us a 5×3 rectangle. The pattern continues. Notice that at each stage our next choice is forced upon us, and they’re the Fibonacci numbers.

We can now prove the theorem by using one of the most powerful proof techniques in combinatorics: calculate something two different ways. Let’s say we’ve spiraled out and included the first n Fibonacci numbers. We obtain a rectangle of dimensions F_{n+1} x F_n; thus the area of this rectangle is F_{n+1} * F_n. We can, however, calculate the area another way. We built it by adding squares whose side lengths were F_1, F_2, …, F_n, and thus the area is also equal to F_1^2 + F_2^2 + … + F_n^2, which completes the proof!

I built this out of fuse beads with my daughter Kayla and my son Cameron. It was a lot of fun, and led to a nice visual proof that I can pack up and take with me to classes and schools.

For more reading / viewing, here are some clickable links:

- Professor Arthur Benjamin talks about the Fibonacci numbers (and gives this proof of the above theorem).
- Kologlu, Kopp, Miller and Wang’s paper on Fibonacci numbers and Zeckendorf decompositions.
- Survey article on Zeckendorf decompositions and the power of the combinatorial perspective (Miller and Wang).
- Talk by Miller on the Fibonacci numbers and Zeckendorf’s theorem (and generalizations).
- Perler fuse beads (note it took us four BIG baseboards to do this!).

## Recent Comments