Welcome to NRICH.

 
1, 2 and 3
By Wadebridge School on February 2, 1998:

Year 8 in Wadebridge School, Cornwall need some help. The problem is that we are investigating in to the number of combinations 1, 2, and 3 can be added to make a number. For example, 5 can be made 13 times:

11111
1112
1121
1211
2111
122
212
221
113
131
311
32
23

a table for the number of combinations is as follows:
1 1
2 2
3 4
4 7
5 13
6 24
7 44
8 81

We have discovered that each number is the sum of the 3 that precede it.

What we would like to know a formula for this the relationship between the number and the number of combinations. Thanks very much.

By Anonymous on Friday, September 8, 2000 - 04:30 pm:

A really intriguing question! You have all done well to solve the problem to get the sequence:
1, 2, 4, 7, 13, 24, 44, 81 ...
where the nth term Un is the sum of the 3 terms that precede it, i.e. Un = Un-1 + Un-2 + Un-3

You ask about a formula for Un and sadly it is a very complicated matter to get it. When you do it seems unbelievable that it gives whole numbers (1, 2, 4, 7 etc.) but it does, maths is amazing!

To give you an idea, one bit of the formula involves
1/3 + 1/3[(19+3sqrt(33))1/3 + (19-3sqrt(33))1/3] or approximately 1.839 to 3 decimal places.

For large enough n you get pretty close to the correct value of Un by taking 0.619 times 1.839n.

This comes from solving a deceptively simple equation
x3- x2 - x - 1 = 0 but I would not bother about any of this for a few years to come.

Have you considered the simple case of your problem taking the number of combinations of just 1 and 2?

This gives the well known Fibonnaci sequence. When you ask YOUR QUESTION about a formula for Un finding the answer is a similar task (it involves sqrt(5) all over the place!).


Now I want to ask you a question. Have you got a really convincing explanation of why each term of the sequence, giving the number of combinations, is the sum of the 3 that precede it? Maybe you have written down all the patterns of 1's, 2's and 3's, counted them and spotted the pattern. The pattern might break down somewhere and I don't suppose you want to spend the rest of your lives checking it for larger and larger numbers. It can be proved quite easily that this always works. Can you justify or prove that it does?


Clearly you have already done some very good work on this and it would be nice to hear more from you.

Very best wishes

NRICH