Ordered Sums

Let a(n) be the number of ways of expressing the integer n as an ordered sum of 1's and 2's. (For example a(4) = 5 because 4 = 2+2 = 2+1+1 = 1+2+1 = 1+1+2 = 1+1+1+1). Let b(n) be the number of ways of expressing n as an ordered sum of integers greater than 1; for example 4 can be written as 4 or as 2+2 so b(4) = 2. As another example, 5 can be written as 5 or as 2+3 or as 3+2 so b(5)=3.

The values of a(n) and b(n) for n < 9 are given in the following table. What do you notice about these sequences?

These are Fibonacci sequences and a(n) = b( n+2) for n >= 1.

The proof follows. To count the number of ways to write n as an ordered sum of 1's and 2's notice that any ordered sum must end in a 1 or a 2. If it ends in a 1 then there are a( n-1) ways of writing the previous terms and if it ends in a 2 then there are a( n-2) ways of forming these ordered sums. Hence the total number a(n) is given by a( n-1) + a( n-2). This is the recurrence relation for the Fibonacci sequence so a(n) is a `Fib'.

For b(n), that is for representations of n as sums of integers greater than 1, we first suppose the last term is k. Then we have:

n = * + * + ... + k (with k >= 2) (1)

If k=2 then the terms that come before have to add up to ( n-2) and so there are b( n-2) possible initial decompositions into ordered sums of integers.

If k>=3 then we subtract 1 in equation (1) to give:

n - 1 = * + * + ... + ( k-1) (with k-1 >=2) (2)

This has reduced the remaining representations to the conditions of the original definition, thus there are b( n-1) such representations. Hence b(n) = b( n-1) + b( n-2) giving the Fibonacci seqence.

As b(3) = 1 = a(1) and b(4) = a(2), where a(n) and b(n) satisfy the same recurrence relation when n>=2, it follows that b( n+2) = a(n) for n>=2.