Hi , i'm not sure how my lecturer got this. may i know what he did in between to derive this ?

thanks :)

Printable View

- December 10th 2009, 01:28 AMxcludedArithmetic progression problem
Hi , i'm not sure how my lecturer got this. may i know what he did in between to derive this ?

thanks :) - December 10th 2009, 01:44 AMjanvdl
Prove by induction.

**For n = 1:**

true for

**Now let n = k:**

**We want to prove it for n = k + 1:**

We already have:

So:

Divide by and multiply by

true - December 10th 2009, 05:20 AMSoroban
Hello, xcluded!

Are you sure he derived it himself?

It takes quite a bit of work . . .

Quote:

The first few values: .

Take the differences of consecutive terms,

. . then take differences of the differences, etc.

. .

The*3rd*differences are constant.

Hence, the generating function is of the*3rd*degree . . . a cubic.

The general cubic is: .

To determine , we use the first four terms of the sequence

. . and construct a system of equations.

. . .

. .

. .

. .

Substitute into [8]: .

Substitute into [5]: .

Substitute into [1]: .

Hence: .

. . Therefore: .

- December 10th 2009, 05:35 AMHallsofIvy
janvdl

**proved**it. To derive it, you can use "Newton's divided difference formula". If You make a list of values a(n), then subtract each value from the next, (That's the "difference". The "divided" part would be dividing by the distance between succesive indices which, here, is 1.) Form the "second difference" by subtracting each difference from the next, . Form the "third difference" similarly, etc. If you stop with the "kth difference", then a(n) is approximated by . (That should remind you of the Taylor polynomials.)

If a(n) is a polynomial, that "kth difference" will eventually be all 0 and you get an exact polynomial expression for a(n).

For this problem, when n= 1, that sum is just , when n= 2, it is , when n= 3, it is , etc. I am going to add a(0)= 0 for simplicity. Taking differences, second differences, etc., we get

So we can see that a(0)= 0, , , and all succeeding differences are 0.

Now, Newton's divided difference formula becomes and all succeeding terms are 0. If we factor out a 1/6, that becomes

exactly the formula you give.

Blast! Soroban beat me again! - December 10th 2009, 06:41 AMflyingsquirrel