A challenge

Let a(n) be defined in the following manner. Write n as an ordered sum of positive integers in all possible ways. (The number of such expressions is 2n−1; showing this is a pleasant exercise, but it is not relevant for what follows.) For each expression, multiply the summands together; then add the resulting products. So, for example,

3 = 2+1 = 1+2 = 1+1+1,

so

a(3) = 3+2.1+1.2+1.1.1 = 8.

Now the values a(1) = 1, a(2) = 3, a(3) = 8, … are alternate Fibonacci numbers.

This is an exercise, not a research problem. Try it for yourself before reading on. [According to Donald Knuth, Richard Bellman included a section called “Exercises and Research Problems” at the end of some chapters of his book Dynamic Programming. When asked how you tell the difference, he replied, “If you can solve it, it is an exercise; otherwise it’s a research problem.”]

I give a proof below, using formal power series. The challenge is to find a more direct proof. This would preferably consist of matching up the values with some known description of Fibonacci numbers (such as the number of binary sequences of length n without consecutive ones, or of expressions for n as a sum of ones and twos). Failing that, proving directly that the numbers a(n) satisfy the same recurrence relation as the alternate Fibonacci numbers (see below).

Here is the proof. It uses an auxiliary power series

F(x) = x+2x2+3x3+…

(the general term is nxn). Using the Binomial Theorem, or by any of various direct arguments, show that F(x) = x/(1−x)2.

The coefficient of xn in F(x) is n, which corresponds to our prescription for a(n) but with just one term in the sum.

Now the coefficient of xn in F(x)2 is the sum of all products kl, where k and l are positive integers summing to n; in other words, our prescription for a(n) but with just two terms in the sum. Similarly the coefficient of xn in F(x)3 corresponds to taking three terms in the sum, and so on.

So, if A(x) is the generating function for the sequence (a(n)), then we have

A(x) = F(x)+F(x)2+F(x)3+… = F(x)/(1−F(x)).

Substituting in our formula for F(x), we find that

A(x) = x/(1−3x+x2).

This shows that the sequence (a(n)) satisfies the recurrence

a(n) = 3a(n−1)-a(n−2),

which is the same as the recurrence for alternate Fibonacci numbers. Using the initial values, it is now immediate to get the result.

This post is the result of my having set this problem to my students, and then realising that I had forgotten how to do it myself.

I count all the things that need to be counted.
This entry was posted in exposition and tagged , . Bookmark the permalink.

11 Responses to A challenge

1. Olly Johnson says:

One idea is to split the partitions by the first term, so (with a(0) = 1)
a(n) = 1*a(n-1) + 2*a(n-2) + 3 a(n-3) + …
(since for example a partition that starts with a 3 contributes 3 to the product, and so on).

If this is right, it ought to be that this is the same as your 3-term recurrence relation, but I can’t see why immediately. It seems to work numerically though.

• I almost see the argument. Inductively we have
a(n-1)=1.a(n-2)+2.a(n-3)+…, so
a(n)-a(n-1)=a(n-1)+a(n-2)+…. Then
a(n-1)-a(n-2)=a(n-2)+…, so
a(n)-2a(n-1)+a(n-2)=a(n-1). But I think you need to be careful about “end effects”.

• Olly Johnson says:

Ok, that makes a lot of sense, thanks. I *think* end effects are fine, because it’s really a finite sum (with the final term always corresponding to a(0), and so like is being compared with like), but I’m not a pure mathematician, so may be being more casual than you’d prefer.

2. Jon Awbrey says:

The last time I played with partitions, a very large number of interesting problems fell under the heading of q-analogues of integration by parts. Don’t know if there’s an approach from that direction here.

3. Will Orrick says:

Let n = 2k – 1 and consider the monomer-dimer problem on n sites, with the sites numbered 1, 2, 3, …, n. There are k – 1 even numbered sites and k odd numbered sites. Classify monomer-dimer configurations according to which even-numbered sites are covered by monomers. Since each even-numbered site may be covered either by a monomer or by a dimer, this classification partitions the set of configurations into 2^(k – 1) classes. To simplify the discussion, place monomers at the two fictitious even-numbered sites 0 and n+1. Now between two consecutive monomer-occupied even sites there will be exactly one monomer, which will occupy an odd site; everything else must be covered by dimers. The total of the number of dimers and the number of odd-site monomers is k, and the placement of the even-site monomers creates an ordered partition of k. For each such ordered partition, the number of ways of placing the odd-site monomers is the product of its parts.

• Will Orrick says:

Incidentally, for the monomer-dimer problem on n = 2k sites you have to sum the product of the parts of every ordered partition of all numbers less than or equal to k (including the empty product you get from the empty ordered partition of 0). This is because you can have a string of up to k dimers after the last monomer-occupied even site. So for six sites you get (3 + 2*1+1*2+1*1*1) + (2 + 1*1) + (1) + 1 = 13. The last +1 is for the empty partition.

• Another way of getting the other Fibonacci numbers is to multiply, not the summands themselves, but their images under the map taking 1 to 1 and n to 2^(n-2) for n>1. The power series proof does this with almost exactly the same argument, taking F to be the generating function for these numbers. I suppose there is a way to see why this is the same…

4. Will Orrick says:

This is very interesting. Not surprisingly it can also be understood as a combinatorial solution to the monomer-dimer problem. Let n be even and again place fictitious monomers just outside the interval of interest at sites 0 and n + 1 in order to simplify the discussion. Any monomer-dimer configuration may be partitioned by placing a separator between sites 2j – 1 and 2j whenever both are covered by monomers. (The lengths of the resulting parts divided by 2 form an ordered integer partition of n / 2 + 1.) Between the separators, each part will consist of an even-site monomer followed by a sequence of dimers and monomers followed by an odd-site monomer, the only restriction being that at no point within the part is an odd-site monomer to be followed by an even-site monomer. For a part consisting of the 2w sites 2k, 2k + 1, 2k + 2, …, 2(k + w) – 1, this condition along with the data indicating whether a dimer spans the sites 2j, 2j + 1 for each j in {k+1, k+2, … k+w-2}, which can be decided independently for each j, completely determines the configuration. When w = 1 or w = 2, there is only one possibility: EO for w = 1 and EDO for w = 2, where E represents even-site monomer, D represents dimer, and O represents odd-site monomer. In general, however, there are 2^(w-2) possibilities. For example, when w = 5, we have EDDDDO, EDDOdEO, EDOdEDO, EDOddEO, EOdEDDO, EOdEOdEO, EOddEDO, EOdddEO, where lowercase d represents a dimer spanning an even followed by an odd site and uppercase D represents a dimer spanning an odd followed by an even site.

The configurations, with separator marks, and corresponding counting formulas for n = 4 are
EO.EO.EO (1*1*1)
EO.EDO (1*1)
EDO.EO (1*1)
EDDO, EOdEO (2),
for a total of five configurations. The initial E and the final O are the fictitious monomers.

• Will Orrick says:

A slight elaboration on the statement, “For a part consisting of the 2w sites 2k, 2k + 1, 2k + 2, …, 2(k + w) – 1, this condition along with the data indicating whether a dimer spans the sites 2j, 2j + 1 for each j in {k+1, k+2, … k+w-2}, which can be decided independently for each j, completely determines the configuration.”

Start with EO EO EO … EO (the number of EO units is w) and replace some pairs of adjacent monomers with dimers so as to eliminate all occurrences of the pattern OE. The initial E and the final O must remain since they help define the partition. Of the w-2 EO units in the middle, we arbitrarily replace some with dimers, d. There are 2^(w-2) ways to do this. Then to ensure that the pattern OE does not occur, we replace any occurrences of that pattern that remain with a dimer D.

So, for example, the third of the eight configurations listed in the previous comment for w=5 is obtained from EO EO EO EO EO by replacing the third pair with d: EO EO d EO EO. Then the remaining occurrences of OE are eliminated by replacing them with D: EDOdEDO. Similarly, the fifth configuration on the list is obtained from EO EO EO EO EO by replacing the second and fourth pairs with d: EO d EO d EO. No occurrence of the pattern OE remains, so nothing more needs to be done.

A final comment: we may use the same method for enumerating monomer-dimer configurations in the n odd case, but at the cost of including additional terms in the sum. So let n = 2k+1. Instead of adding a fictitious monomer at site 2k+2, we have the following series of possibilities: (1) put a monomer at site 2k+1, which will be an O. The rest is then an enumeration problem for the even length 2k. (2) Put a dimer at sites 2k, 2k+1 and a monomer at site 2k-1 (which will be an O). The rest is now an enumeration problem for the even length 2k-2. (3) Put dimers at 2k, 2k+1 and at 2k-2, 2k-1 and a monomer at 2k-3, leaving an enumeration problem for the length 2k-4. (4) An so on, including all even-length enumeration problems down to length 0, This is analogous to what we had to do using the earlier enumeration method when we wanted to handle the n even case.

5. jbritnell2013 says:

Let $b(n)$ be defined as $a(n)$, except that the sum is taken only over partitions whose first term is not 1. Let $c(n)$ be defined similarly, but with the sum restricted to partitions such that neither of the first two terms is 1.

It’s easy to show (for $n>1$) that $a(n) = b(n) + a(n-1)$, and similarly that $b(n) = b(n-1) + c(n)$. If we can show that $c(n)=a(n-1)$, then it will follow that the sequence created by interleaving $(b(n))$ and $(a(n))$ satisfies the Fibonacci recurrence (and checking the early terms shows that it is the actual Fibonacci sequence).

So we need to show that $c(n)= a(n-1)$. Let $s=(s_1,\dots,s_k)$ be a partition of $n$, such that $s_1,s_2 \ne 1$ (or such that $k=1$). I define two partitions $f(s)$ and $g(s)$ of $n-1$, as follows:

* The rule for defining $f(s)$ is: replace $s(1)$ with $1^{s(1)-1}$. (So $(4,2,3)$ becomes $(1,1,1,2,3)$.

* The rule for defining $g(s)$ is: if $s(1)>2$ then simply reduce $s(1)$ by 1. If $g(2)=2$ then replace $(s(1),s(2))$ with $(s(2), 1)$.

We note that $f(s)$ has first part 1 and $g(s)$ does not, that every partition of $n-1$ appears as $f(s)$ or $g(s)$ for exactly one $s$, and that the product of parts of $s$ is equal to the sum of those for $f(s)$ and $g(s)$.

If you believe this slightly sketchy argument, then we’re done.

6. igessel says:

A combinatorial proof can be found in Richard Stanley’s Enumerative Combinatorics, Volume 1 (2nd edition), problem 35f, page 109; solution, page 152. A comprehensive account of similar identities can be found in my paper with Ji Li, Compositions and Fibonacci Identities, Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.5, https://cs.uwaterloo.ca/journals/JIS/VOL16/Gessel/gessel6.html .

This site uses Akismet to reduce spam. Learn how your comment data is processed.