HP Forums

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.

(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

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)

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

Albert Chan

Albert Chan

pier4r