Thread: A Series ?

For a specific algorithm, I figured that in the algorithm, for:

n = 3, the answer is 1
n = 4, the answer is 4
n = 5, the answer is 10
n = 6, the answer is 20
n = 7, the answer is 35
n = 8, the answer is 56
n = 9, the answer is 84
n = 10, the answer is 84
n = 11, the answer is 120

And so forth.

I need the sum of all numbers in general, for n >= 3.

I can't quite see what the general formula would be. It initially appeared to be a geometric series.

So,

1 + 4 + 10 + 20 + 35 + 56 + 84 + 120...

It goes up in increments of: 3, 6, 10, 15, 21, 28, 36
Where:
3 to 6 --> 3
6 to 10 --> 4
10 to 15 --> 5
15 to 21 --> 6
x to y --> n + 1, where is n is the previous amount it went up by.

Anyone see the generic formula/series?

Thanks.

Originally Posted by AfterShock

For a specific algorithm, I figured that in the algorithm, for:

n = 3, the answer is 1
n = 4, the answer is 4
n = 5, the answer is 10
n = 6, the answer is 20
n = 7, the answer is 35
n = 8, the answer is 56
n = 9, the answer is 84
n = 10, the answer is 84
n = 11, the answer is 120

And so forth.

I need the sum of all numbers in general, for n >= 3.

I can't quite see what the general formula would be. It initially appeared to be a geometric series.

So,

1 + 4 + 10 + 20 + 35 + 56 + 84 + 120...

It goes up in increments of: 3, 6, 10, 15, 21, 28, 36
Where:
3 to 6 --> 3
6 to 10 --> 4
10 to 15 --> 5
15 to 21 --> 6
x to y --> n + 1, where is n is the previous amount it went up by.

Anyone see the generic formula/series?

Thanks.

Are you serious ( )?

Here is a hint. It is a cubic sequence (not series).
Thus,
a_n=An^3+Bn^2+Cn+D

You job is to find A,B,C,D.

Originally Posted by AfterShock

For a specific algorithm, I figured that in the algorithm, for:

n = 3, the answer is 1
n = 4, the answer is 4
n = 5, the answer is 10
n = 6, the answer is 20
n = 7, the answer is 35
n = 8, the answer is 56
n = 9, the answer is 84
n = 10, the answer is 84
n = 11, the answer is 120

And so forth.

Assume the duplicate 84 is a mistake.

Compute a diference table for this:

Code:

1   4  10  20  35  57  84  120
  3   6  10  15  21  28  36
    3  4   5   6   7   8
     1   1   1   1   1

That the n-th differences are a constant is a characteristic of
a n-th order polynomial, so here its the third differences are
constant so the original sequence is a cubic in n.

So fit a cubic to your original data to obtain the formula for the n-th
term (note this is a bit of a risk as in general there is no guarantee
that the data is produced this way, your really need to examine the
underlying process to check this).

RonL

A result I discovered about sequencial differeneces would help you find the main coefficient of that polynomial.

Since the number of terms until a trivial sequnce is 3 the polynomial is degree 3. Thus, the trivial sequcen (the last sequnce until a constant) must be 3!=6 but this is 1. Thus, you need it to be 1/6. So that when you multiply by the factorial of the degree it gives 1. That even further simplifies your problem.

Originally Posted by ThePerfectHacker

A result I discovered about sequencial differeneces would help you find the main coefficient of that polynomial.

Since the number of terms until a trivial sequnce is 3 the polynomial is degree 3. Thus, the trivial sequcen (the last sequnce until a constant) must be 3!=6 but this is 1. Thus, you need it to be 1/6. So that when you multiply by the factorial of the degree it gives 1. That even further simplifies your problem.

There is a procedure of Newton's that will give the polynomial from the
difference table - I beleive its in Actons "Numerical methods that Work".

RonL

Yes, Perfect, I was serious . Even Math Majors do forget some of the simple stuff. I think I got it, though.

C(n+3, 3) = (n + 1)(n + 2)(n + 3)/6

Meh, not quite. Since n starts with 3!

Originally Posted by Tetris Princess

Meh, not quite. Since n starts with 3!

Not sure what you are trying to say.
I mean that if you have a polynomial of degree 3 with no coefficient in front (except unity of course) the final difference is 3!
(This holds in general).

Thus, If you have Ax^3 then the final difference is A(3!)=1
Thus, A=1/6

Originally Posted by CaptainBlank

There is a procedure of Newton's that will give the polynomial from the
difference table - I beleive its in Actons "Numerical methods that Work".

Is not true that finding a result thyself if most satisfying?

So, you're saying in general, 1/6 is constant, where A alternates to
(n)(n+1)...(n+k)!

But for the algorithm the n starts at 3. It can't be less than 3 or it's undefined. I will half to incorporate a sigma then, for n to start at 3 and to still get the same results. And,

(1/6)*3! = 1
(1/6)*4! = 4
(1/6)*5! = 20

(Thereby already skipping n = 5 [10])

Originally Posted by ThePerfectHacker

Not sure what you are trying to say.
I mean that if you have a polynomial of degree 3 with no coefficient in front (except unity of course) the final difference is 3!
(This holds in general).

Thus, If you have Ax^3 then the final difference is A(3!)=1
Thus, A=1/6


Is not true that finding a result thyself if most satisfying?

Yes, but where do you start? (Note I did not recomend using it, just
observed that it exists - I would not use it to do this problem -- but
then I would not have found the op count formula by fitting to a table
of specific cases anyway, I would have worked from the algorithm
description and derived the formula directly (if at all possible)).

RonL

Originally Posted by CaptainBlack

Yes, but where do you start?

Start what?

Originally Posted by ThePerfectHacker

Start what?

In finding results for youself.

Do we start from discovering that 1+1=2, and proceed to deduce the
existance or rice pudding on our own?

RonL

Originally Posted by CaptainBlank

In finding results for youself.

Do we start from discovering that 1+1=2, and proceed to deduce the
existance or rice pudding on our own?

RonL

I still do not understand you?
---
Speaking more about sequencial differences is there a non-trivial answer to the problem,
d(a_n)=a_n
Where "d" is the derivative operator (i.e. subtraction).
Note the Fibonacci sequence, almost works.

It seems to be the fiboanny sequence plays the role of differencial equations for sequences (if there is such a thing) like the exponential function if differncial equaions.

And the cubic sequence is? Since apparently my combinatorics formula doesn't work?

Originally Posted by AfterShock

And the cubic sequence is? Since apparently my combinatorics formula doesn't work?

write the cubic as N(n)=a + b n + c n^2 + d n^3,

then using the data you gave:

n = 3, the answer is 1
n = 4, the answer is 4
n = 5, the answer is 10
n = 6, the answer is 20

we have a set of linear simultaneous equations:

a+3b+9c+27d=1
a+4b+16c+64d=4
a+5b+25c+125d=10
a+6b+36c+216d=20

which can be solved for a, b, c, d.

Now take these to QuickMath for solution and we get what is shown in the attachment

RonL