Funny Factorials and Slick Sums

[Albert Chan]

We can generalize falling factorial form polynomial and power form polynomial as Newton form polynomial.
For falling factorial form, offsets = 0,1,2,3, ...
For power form, offsets = 0,0,0,0, ...

Below is the synthetic division, that can convert from 1 set of offsets, to another.

Example: simplify this: S₄(n) = -17 + \(16\binom{n+3}{1}-15\binom{n+3}{2}+14 \binom{n+3}{3}-12\binom{n+3}{4}+24\binom{n+3}{5}\)

To setup synthetic division, negate the from-offsets, and put to first column, in reverse order.
For above S₄(n), negated from-offsets = 3,2,1,0,-1

Next, put to-offsets to second column.
Since S₄(-1) = S₄(0) = 0, we know S₄(n) has factor n*(n+1), thus to-offsets = -1,0,0,0,0

For each row, to-offset numbers is "locked". Negated from-offsets treated like a stack, "popped" when used.

Code:

        24  -12   14  -15   16  -17 // S4 in binomial form
         6  -15   70 -225  480 -510 // 30*S4 in falling factorial form
-1 -1>   6  -27   97 -225  255    0 // (-1-1)*6-15=-27, (0-1)*-27+70=97, (1-1)*97-225=-225 ...
 0  0>   6  -27   70  -85    0      // (0+0)*6-27=-27, (1+0)*-27+97=70, (2+0)*70-225=-85 ...
 1  0>   6  -21   28   -1
 2  0>   6   -9    1
 3  0>   6    9

6n³ + 9n² + n - 1 = (2n+1) (3n² + 3n - 1)

→ S₄(n) = (n)(n+1)(2n+1)(3n² + 3n - 1) / 30

source: "Fundamentals of Numerical Anaylsis" by Stephen G. Kellison, published in 1975
Appendix B: Transformation of polynomial forms. (modified to use only +* for synthetic division)