"Counting in their heads" - 1895 oil painting

[Albert Chan]

There is also the Faulhaber polynomials, with sum-of-powers formula as function of triangular number.

Let \(\large t = \binom{x}{2},\;{s_{2m} \over (2x-1)t}\) and \(\large {s_{2m+1} \over t^2}\) are polynomial of t, degree m-1

Example, get s4(x) and s5(x) in terms of t, using divided difference.
Note: we start from x=2, instead of 0, to avoid divide-by-zero issue.

Code:

x   s4(x)    | t    s4/(2xt-t)  divided-diff
2   0+1^4=1  | 1    1/3
3   1+2^4=17 | 3    17/15       (17/15-1/3)/(3-1) = 2/5

--> s4(x) = (2xt-t) * (1/3 + (t-1)*2/5) = (2x-1)*(6t^2-t)/15

x   s5(x)    | t    s5/t^2      divided-diff
2   0+1^5=1  | 1    1
3   1+2^5=33 | 3    11/3        (11/3-1)/(3-1) = 4/3

--> s5(x) = t^2 * (1 + (t-1)*4/3) = (4t^3-t^2)/3

Redo previous example, using horners rule for the difference.

Code:

lua> a,b = 50, 151      -- next line replaced with t's
lua> a,b = a*(a-1)/2, b*(b-1)/2
lua> d = b-a            -- = 10100
lua> d2 = b+a           -- = (b^2-a^2)/d = 12550
lua> d3 = d2*b+a^2      -- = (b^3-a^3)/d = 143629375
lua> (4*d3 - d2)*d / 3  -- = 50^5 + 51^5 + ... + 150^5
1934166665000