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
Hello, xcluded!
Are you sure he derived it himself?
It takes quite a bit of work . . .
We have: .
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: .
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!