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.