You may also like

Doodles

Draw a 'doodle' - a closed intersecting curve drawn without taking pencil from paper. What can you prove about the intersections?

Russian Cubes

I want some cubes painted with three blue faces and three red faces. How many different cubes can be painted like that?

Picture Story

Can you see how this picture illustrates the formula for the sum of the first six cube numbers?

Ordered Sums

Age 14 to 16 Challenge Level:

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.