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?

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
---|---|---|---|---|---|---|---|---|---|

a(n) | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 |

b(n) | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 |

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.