You may also like

problem icon

Upsetting Pitagoras

Find the smallest integer solution to the equation 1/x^2 + 1/y^2 = 1/z^2

problem icon

Rudolff's Problem

A group of 20 people pay a total of £20 to see an exhibition. The admission price is £3 for men, £2 for women and 50p for children. How many men, women and children are there in the group?

problem icon

Euler's Squares

Euler found four whole numbers such that the sum of any two of the numbers is a perfect square...

Ordered Sums

Stage: 4 Challenge Level: Challenge Level:2 Challenge Level:2

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.