Finding the Fibonacci sequence in 1s and 2s

Number patterns like the Fibonacci sequence are famous because they pop up in so many unexpected places. The usual way to construct the Fibonacci sequence is by adding the two previous terms to get the next, starting with 1 and 1 (or 0 and 1 if you prefer):

\(1, 1, 2, 3, 5, 8, 13, 21, 34, ...\)

Although simple to construct, the Fibonacci sequence turns up in the natural world, for instance in the spiral patterns of sunflowers and pinecones, and also in the world of mathematics, including Pascal's triangle and the well-known golden ratio.

Today we will look at an intriguing combinatorics problem where the Fibonacci sequence makes a surprise appearance.

How many ways are there to arrange copies of 1 and 2 so that they sum to a particular integer? For example, there is only 1 way to get 1, and that’s by writing a lone number 1:

\(1 = 1\)

However, there are 2 ways to get 2. By writing a lone 2, and by writing 1 + 1:

\(\begin{align} 2 &= 2 \\ 2 &= 1 + 1 \end{align}\)

There are 3 ways to arrive at 3:

\(\begin{align} 3 &= 2 + 1 \\ 3 &= 1 + 2 \\ 3 &= 1 + 1 + 1 \end{align}\)

Notice that the order of the terms matters. We are counting 1 + 2 and 2 + 1 as two different sums. If we continue on, there are 5 ways to get 4:

\(\begin{align} 4 &= 2 + 2 \\ 4 &= 1 + 1 + 2 \\ 4 &= 1 + 2 + 1\\ 4 &= 2 + 1 + 1\\ 4 &= 1 + 1 + 1 + 1 \end{align}\)

8 ways to get 5:

\(\begin{align} 5 &= 1 + 2 + 2 \\ 5 &= 2 + 2 + 1 \\ 5 &= 2 + 1 + 2\\ 5 &= 2 + 1 + 1 + 1\\ 5 &= 1 + 2 + 1 + 1\\ 5 &= 1 + 1 + 2 + 1\\ 5 &= 1 + 1 + 1 + 2\\ 5 &= 1 + 1 + 1 + 1 + 1\\ \end{align}\)

And so on. Counting the number of ways to write each successive integer using only 1s and 2s follows the Fibonacci pattern 2, 3, 5, 8, …

To see why this is true, let’s consider the 8 ways of writing 5. Each sum must start with either a 1 or a 2. If it starts with a 1, then the remaining numbers must sum to 4. If it starts with a 2, then the remaining numbers must sum to 3:

\(\begin{align} 5 &= 1 + (\text{sum of 1s and 2s that add to 4})\\ 5 &= 2 + (\text{sum of 1s and 2s that add to 3}) \end{align}\)

But we already know how many sums of 1s and 2s add to 4. There are 5 of them. Likewise, we already know how many sums of 1s and 2s add to 3. There are 3 of them. So there must be 5 + 3 = 8 ways to get 5 as a sum of 1s and 2s.

This is the same logic used to build the Fibonacci sequence! To get the next term, we add the previous two terms together. This logic extends to any integer written as a sum of 1s and 2s.

From the outset, it's not obvious that this problem would have any connection to Fibonacci, but mathematics is the science of patterns, and this particular pattern is found in many unexpected places.