[Calculus?] "Stepwise integral" (or really accumulation function) of a discrete valued polynomial function f: N -> N.

That function F will always be a polynomial one degree higher than f. Here are a few ways to find F.

There are formulas for 1k+2k+....+tk

https://en.wikipedia.org/wiki/Faulhaber%27s_formula

and there are ways to compute the coefficients

https://en.wikipedia.org/wiki/Bernoulli_number


Or you can set up a linear system of equations in the coefficients. You want

F(t) - F(t-1) = f(t)

F(0) = 0

and if you let F(t) be a polynomial one degree higher, and treat its coefficients as variables, those give you a system of linear equations you can solve.


You can evaluate F(0), F(1), F(2), ..., F(m) where m = deg(f), then use one of the polynomial interpolation functions to find F.


You can start with a special case. If f(t) = C(t,k) where C is the binomial coefficient function, then for k > 0 you have

C(1,k) + C(2,k) + ... + C(t,k) = C(t+1,k+1)

as a combinatorial identity. So if you can express f(t) as a sum of C(t,k) for various k, you can apply that identity to express F(t) in terms of corresponding C(t+1,k+1).

Note that C(t,k) = t(t-1)(t-2)...(t-k+1). So given f(t), you use repeated polynomial division to express it as

f(t) = a0 + a1*(t + a2*((t-1) + a3*((t-2) + ... ak*(t-k+1))))

= a0 + a1*t + a2*t(t-1) + a3*t(t-1)(t-2) + ....

= a0 + a1*C(t,1) + a2*2!*C(t,2) + a3*3!*C(t,3) + ....

/r/learnmath Thread