converting between sums

The number \(5\) can be written in eight ways as a sum of \(1\)s and \(2\)s (in which order matters): \[ 1+1+1+1+1,\; 1+1+1+2,\; 1+1+2+1,\; 1+2+1+1, \] \[ 2+1+1+1,\; 1+2+2,\; 2+1+2,\; 2+2+1. \] The number \(6\) can also be written in eight ways as a sum of odd numbers: \[ 1+1+1+1+1+1,\; 1+1+1+3,\; 1+1+3+1,\; 1+3+1+1, \] \[ 3+1+1+1,\; 1+5,\; 3+3,\; 5+1. \] Coincidence? No, and if you look carefully at the two lists of sums above, you might be able to guess how the rest of the post is going to go.

Let \(a(n)\) be the number of ways to write \(n\) as a sum of \(1\)s and \(2\), and let \(b(n)\) be the number of ways to write \(n\) as a sum of (positive) odd numbers. The overall goal of this essay is to show that \(b(n) = a(n-1)\), in two different ways.

As it turns out, \(a(n)\) and \(b(n)\) are both closely related to (or, depending on your perspective, the same as) the Fibonacci sequence \(f(n)\), defined recursively by \(f(1) = f(2) = 1\), and for \(n\geq3\) \[ f(n) = f(n-1) + f(n-2). \] The sequence \(f(n)\) begins, starting at \(n=1\), with the terms \(1, 1, 2, 3, 5, 8, 13, \dots\). The recursive formula for this sequence famously arises from the rabbit problem posed by Leonardo of Pisa: each month, Fibonacci’s Immortal Rabbits™ produce a new pair from each pair more than a month old. The number of pairs of rabbits in month \(n\) is therefore the sum of the number of pairs the previous month (all of them having stuck around), and the number of pairs from two months prior (all of these pairs having produced a new pair). Start with \(f(1)=1\) in the first month, and the Fibonacci sequence counts the number of pairs of rabbits you have in the \(n\)th month.

We can see that \(a(1) = 1\) and \(a(2) = 2\), because \(1\) can be written just as \(1\), and \(2\) can be written as \(2\) or as \(1+1\). For larger values of \(n\), the ways of writing \(n\) as a sum of \(1\)s and \(2\)s can be partitioned into the sums that start with \(1\) and those that start with \(2\). Therefore, \(a(n)\) can be expressed as \(a(n-1) + a(n-2)\) for \(n \ge 3\). The sequence \(a(n)\) begins \(1,2,3,5,8,13,21,\dots\). This is the Fibonacci sequence again, but shifted by one position: \(a(n) = f(n+1)\). It is perhaps more appropriately called the Virahanka sequence. What happened to the initial \(1\) in the Fibonacci sequence, though? It shifted to the 0th position: the empty sum, having no terms, is equal to 0 by definition, so \(a(0)=1\). Zero can be written as a sum of \(1\)s and \(2\) in one way, as the empty sum. (I have begun calling both \(f(n)\) and \(a(n)\) the Fibonacci–Virahanka sequence.)

Now let’s try to do something similiar for the sequence \(b(n)\). We can check by hand that \(b(1) = b(2) = 1\), because only the sum \(1+1\) is allowed for \(2\). Any sum of odd numbers could start with 1, or with 3, or with 5, and so on, which implies \[ b(n) = b(n-1) + b(n-3) + b(n-5) + b(n-7) + \cdots. \] While this looks potentially like an infinite sum, notice that for any particular \(n\), the number of nonzero terms is finite, because \(b(n) = 0\) when \(n < 0\). But notice what happens when we peel off the first term of this infinite sum: \[ \begin{array}{rl} b(n) &= b(n-1) + \big(b(n-3) + b(n-5) + b(n-7) + \cdots\big) \\ &= b(n-1) + \big(b((n-2)-1) + b((n-2)-3) + b((n-2)-5) + \cdots\big) \\ &= b(n-1) + b(n-2) \end{array} \] So \(b(n)\) satisfies the same recursive formula as \(f(n)\) and \(a(n)\)! Thus this sequence begins \(1,1,2,3,5,8,13,\dots\), which looks the same as the start of the sequence \(f(n)\). Well, almost. It’s not quite the same sequence as \(f(n)\), because \(b(0)\), like \(a(0)\), equals 1. So, starting at \(n=0\), the sequence \(b(n)\) begins \(1,1,1,2,3,5,8,\dots\). The “empty sum” convention is necessary for the recursive formula for \(b(n)\) to work in the case of both even and odd values of \(n\). However, in Fibonacci’s rabbit problem, the rabbit keeper has zero pairs of rabbits in month 0, so \(f(0)=0\ne b(0)\).

The conclusion of the preceding is that \(a(n)=b(n+1)\) when \(n\ge0\). Yet a second proof was promised. So consider a sum of \(1\)s and \(2\)s that is equal to \(n\). For example, if \(n=9\), we could write \[ 9 = 2 + 1 + 1 + 2 + 2 + 1. \] Now append a \(1\) to the beginning of the sum, then wherever a \(2\) appears, group it with the preceding terms, until a \(1\) is reached, to produce an odd number. For example, using the sum above that equals \(9\), we get \[ 10 = (1 + 2) + 1 + (1 + 2 + 2) + 1 = 3 + 1 + 5 + 1. \] This process can be reversed. Given a sum of odd numbers, convert each term to a sum of \(1\) followed by a sequence of \(2\)s, then remove the initial \(1\). For example, the sum \[16 = 1 + 3 + 5 + 7\] is converted to \[1 + (1 + 2) + (1 + 2 + 2) + (1 + 2 + 2 + 2),\] which corresponds to \[15 = 1 + 2 + 1 + 2 + 2 + 1 + 2 + 2 + 2.\] Thus we have found an explicit bijection between sums of \(1\)s and \(2\) equal to \(n\) and sums of odd numbers equal to \(n+1\). These sums are also called compositions. A comment on the OEIS entry for the Fibonacci sequence observes that, more generally, “the numbers of compositions [of \(n\)] using parts \(1\) and \(k\) is equivalent to the numbers of compositions of \((n+1)\) using parts \(1\) mod \(k\).” An exercise for the reader! Can you generalize further?