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 2ⁿ⁻¹; 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+2x²+3x³+…

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

The coefficient of xⁿ 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 xⁿ in F(x)² 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 xⁿ in F(x)³ 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)²+F(x)³+… = F(x)/(1−F(x)).

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

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

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.