Hitskin.com

موضوع: Solving a Sequence الإثنين 01 سبتمبر 2008, 11:55 pm

First of all, you should be aware that these problems of determining
formulas for sequences are not well-formed. For example, what's the
next number in this sequence:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
28 29 30 31 ?

You probably think it's 32, but it could be 1. The numbers could be
the days of the year, and after January 31 comes February 1.

So you're really looking, in a sense, for the "simplest" formula for the
sequence, and "simplest" can be a matter of opinion.

In your example, the numbers go up by 6, then 9, then 12, then 15, so
I'll assume the numbers that follow go up by three more each time --
by 18, 21, 24, 27, and so on.

I find it easiest to approach such sequences as follows:

List your numbers (I'll add a few to your sequence to show the pattern
better). Then, on the line below, list the differences of those
numbers. On the next line, list the differences of the differences, and
so on:

n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8
3 9 18 30 45 63 84 108 ...
6 9 12 15 18 21 24 ...
3 3 3 3 3 3 ...
0 0 0 0 0 ...

If you eventually come to a row of zeroes, you can write the answer in
the form of a "polynomial".

If the first row of differences is all zeroes, then all your numbers are
the same, and the answer is just a constant. The answer looks like
this:

A, where "A" is the constant.

If the second row of differences is all zeroes, then the answer has the
form:

A + B*n, where "A" and "B" are constants.

If the third row of differences is all zeroes, the answer will be:

A + B*n + C*n^2, where "A", "B", and "C" are constants.

And so on. We just have to figure out what A, B, and C are.

In cases like this, it is easier to start with n=0, and we can "work
backward" to see that the zeroth term would be 0. (The difference
between it and the case where n=1 would be 3.)

Now just plug in the first three values:

If n=0, A + B*0 + C*0^2 = 0.
If n=1, A + B*1 + C*1^2 = 3.
If n=2, A + B*2 + C*2^2 = 9.

From the first row, A + 0 = 0, so A=0.

Using the fact that A = 0, the second row gives:

B + C = 3.

The third row gives:

2B + 4C = 9.

Multiply the equation "B+C=3" by 2 to get:

2B + 2C = 6.

Subtract it from "2B+4C=9" to get:

2C = 3.

So C = 3/2, and therefore B = 3/2.

The equation is:

(3n + 3n^2)
-----------
2

Test it:

n=0 ==> 0
n=1 ==> 3
n=2 ==> (6+12)/2 = 9
n=3 ==> (9+27)/2 = 18
n=4 ==> (12+4/2 = 30
n=5 ==> (15+75)/2 = 45

and you can try your own numbers.

It's too bad that you really need some algebra to solve such problems
easily, but the nice thing is that this method will work for any such
sequence problem where some row of differences is all zeroes.

As a great example, you might want to try to do the same thing to find a
formula for:

0 + 1 + 2 + 3 + ... + n

The sequence (and the differences) are just:

0 1 3 6 10 15 21 28 ...
1 2 3 4 5 6 7 ...
1 1 1 1 1 1 ...
0 0 0 0 0 ...

A + B*0 + C*0 = 0
A + B*1 + C*1 = 1
A + B*2 + C*4 = 3

If you work it out, A = 0, B = 1/2, C = 1/2, so the formula to add up
all the numbers from 0 to n is just:

(n + n^2)
---------
2

Hitskin.com

Solving a Sequence