How can interpolation be used to find a polynomial formula for G(n)?

[KLscilevothma]

Find a formula to calculate G(n) and it should be a polynomial of degree 4.

G(n) = 1/6(0)(0-1)(0-2) + 1/6(1)(1-1)(1-2)+...+1/6(n-1)(n-2)(n-3)

I know
G(0)=G(1)=G(2)=G(3)=0
G(4)=1
G(5)=1+3
G(6)=1+3+6
G(7)=1+2+3+10
G(8)=1+3+6+10+15 (sum of triangle numbers)

What should I do to find out the forumla? I think it is some kind of interpolation formula.

 

[suffian]

G(n) = SUM[ (1/6)(k-1)(k-2)(k-3) , k=1..n] ..rewrite function
G(n) = (1/6) SUM[ (k-1)(k-2)(k-3) , k=1..n] ..extract constant
G(n) = (1/6) SUM[ (k³-6k²+11k-6) , k=1..n] ..expand the general term on inside
G(n) = (1/6)( SUM[k³, k=1..n] - SUM[6k², k=1..n] + SUM[11k, k=1..n] - SUM[6, k=1..n] ) ..add sums separately
G(n) = (1/6)( n²(n+1)²/4 - 6n(n+1)(2n+1)/6 +11n(n+1)/2 -6n ) ..rewrite sums
G(n) = (1/24)n⁴ - (1/4)n³ + (11/24)n² - (1/4)n ..expand

Your G(n) values do not agree for n > 4. Take for instance G(5) = (1/6)(4-1)(4-2)(4-3) + (1/6)(5-1)(5-2)(5-3) = 1 + 4 = 5

 

[KLscilevothma]

Originally posted by suffian
G(n) = SUM[ (1/6)(k-1)(k-2)(k-3) , k=1..n] ..rewrite function
G(n) = (1/6) SUM[ (k-1)(k-2)(k-3) , k=1..n] ..extract constant
G(n) = (1/6) SUM[ (k³-6k²+11k-6) , k=1..n] ..expand the general term on inside
G(n) = (1/6)( SUM[k³, k=1..n] - SUM[6k², k=1..n] + SUM[11k, k=1..n] - SUM[6, k=1..n] ) ..add sums separately
G(n) = (1/6)( n²(n+1)²/4 - 6n(n+1)(2n+1)/6 +11n(n+1)/2 -6n ) ..rewrite sums
G(n) = (1/24)n⁴ - (1/4)n³ + (11/24)n² - (1/4)n ..expand

Thank you. I think this is one of the ways to tackle this problem. After reading my notes carefully, I think we can do the question by using "interpolation" method as follows:
G(1)=G(2)=G(3)=0
G(4)=1
G(5)=5
Since G(1)=G(2)=G(3)=0, (x-1), (x-2) and (x-3) are factors of G(n). Since the formula that we need to find is of degree 4, therefore G(n)=(an+b)(n-1)(n-2)(n-3). By using G(4)=1 and G(5)=5, we know G(n)=1/24n(n-1)(n-2)(n-3), which is exactly the answer that you get.

Your G(n) values do not agree for n > 4. Take for instance G(5) = (1/6)(4-1)(4-2)(4-3) + (1/6)(5-1)(5-2)(5-3) = 1 + 4 = 5

Usually I can't do simple arithmatic correctly.