Funny Factorials and Slick Sums

[Albert Chan]

Spring 2017 ARML Power Contest, Problems and Solutions.

Example, find s₆(n) = Σ(x^6, x = 0 to n-1)

Convert x^6 to falling factorial form, where xⁿ = product(x-k, k = 0 .. n-1)

Code:

Synthetic Division, polynomial to falling factorial form:
   1  0  0  0  0  0  0  // x^6
1> 1  1  1  1  1  1     // = (x-1)(x^5 + x^4 + x^3 + x^2 + 1) + 1
2> 1  3  7 15 31
3> 1  6 25 90
4> 1 10 65
5> 1 15

Note: synthetic divide by (x-0) step skipped, since x^6 = (x-0)*x^5 + 0

x^6 = x⁶ + 15 x⁵ + 65 x⁴ + 90 x³ + 31 x² + x¹

From problem 12, Σ(x^m, x=0 to n-1) = n^m+1 / (m+1)

s₆(n) = n⁷/7 + 15 n⁶/6 + 65 n⁵/5 + 90 n⁴/4 + 31 n³/3 + n²/2

After simplify, s₆(n) = n^7/7 - n^6/2 + n^5/2 - n^3/6 + n/42

http://www.arml.com/ had more contests. 2009-2014 contests book is free to download.

[Albert Chan]

(08-05-2019 12:21 AM)Albert Chan Wrote:  s₆(n) = n⁷/7 + 15 n⁶/6 + 65 n⁵/5 + 90 n⁴/4 + 31 n³/3 + n²/2

After simplify, s₆(n) = n^7/7 - n^6/2 + n^5/2 - n^3/6 + n/42

We can automate the process of simplifying.

For s₆(n), polynomial linear coefficent = limit(s₆(n)/n, n=0):

(-1)⁶/7 + 15 (-1)⁵/6 + 65 (-1)⁴/5 + 90 (-1)³/4 + 31 (-1)²/3 + (-1)¹/2
= -1*(1/2 - 2*(31/3 - 3*(90/4 - 4*(65/5 - 5*(15/6 - 6*(1/7))))))
= -1*(1/2 - 2*(31/3 - 3*(90/4 - 4*(65/5 - 5*(23/14)))))
= -1*(1/2 - 2*(31/3 - 3*(90/4 - 4*(67/14))))
= -1*(1/2 - 2*(31/3 - 3*(47/14)))
= -1*(1/2 - 2*(11/42))
= -1*(-1/42)
= 1/42

→ s₆(n) / n = (1/7) n⁶ + (23/14) n⁵ + (67/14) n⁴ + (47/14) n³ + (11/42) n² + (-1/42) n¹ + 1/42

We divide n repeatedly, collecting remainder terms, until quotient is linear, since a n¹ + b n⁰ = a n + b

Code:

Synthetic Division, falling factorial form to polynomial
      6 105 546 945 434  21   0   0  // 42*s6, falling factorial coefficients
-6 0> 6  69 201 141  11  -1   1      // -6*6+105=69, -5*69+546=201 ...
-5 0> 6  39  45   6  -1   0          // -5*6+69=39, -4*39+201=45 ...
-4 0> 6  15   0   6  -7
-3 0> 6  -3   6   0
-2 0> 6 -15  21
-1 0> 6 -21

Note: 0> signalled first column numbers treated as stack, "popped" when used.

→ s₆(n) = (6 n^7 - 21 n^6 + 21 n^5 - 7 n^3 + n) / 42

see threads: Bernoulli Numbers, Sum of Powers

[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)

[pier4r]

I love this.

Quote:WARNING! In several of the problems, you may be tempted touse an ellipsis (“. . . ”) to shorten arguments or to indicate that apattern continues. DO NOT do this. All proofs must be complete.Ellipsis probably means you need to use induction or recursion

[Albert Chan]

(08-05-2019 12:21 AM)Albert Chan Wrote:  From problem 12, Σ(x^m, x=0 to n-1) = n^m+1 / (m+1)

We can extend this to negative integer powers (but, m≠-1)
Note that x^m = perm(x,m) = x / (x-m)!       (*)

Cas> lfac(x,m) := factor(simplify(x!/(x-m)!))
Cas> lfac(x,3)       → x*(x-1)*(x-2)
Cas> ifac(x,0)       → 1
Cas> ifac(x,-3)      → 1/((x+1)*(x+2)*(x+3))

Issues to watch out for.

1). just like ∫(1/x,x=1..n) = ln(n), quoted formula does not work for m == -1
Note: Psi(n+1) = 1/n + Psi(n) = H_n + Psi(1) = H_n - euler_gamma

Cas> sum(lfac(x,-1), x=0..n-1)       → Psi(n+1) + euler_gamma

2). Other negative integer powers, we have to evaluate for lower limit.
Note: "!" has higher precedence than unary minus, parentheses necessary.

m<-1 : 0 ^m+1 / (m+1) = 1/(-(m+1))!/(m+1)

Example:

Cas> m := -3
Cas> s1 := sum(lfac(x,m), x=0..n-1)

1/4 + 1/(2*n+2) + 1/(2*n+4) + 1/(-n-1)

Cas> s2 := lfac(n,m+1)/(m+1) - 1/(-(m+1))!/(m+1)

1/4 − 1/2/((n+1)*(n+2))

Cas> simplify(s1-s2)

0

(*) not quite. Numerical version for negative m not yet implemented.

Cas> perm(x,-3)       → x!/(x+3)!
Cas> perm(0,-3)       → 0 // should be 1/6