08-05-2019, 12:21 AM
Spring 2017 ARML Power Contest, Problems and Solutions.
Example, find s6(n) = Σ(x^6, x = 0 to n-1)
Convert x^6 to falling factorial form, where xn = product(x-k, k = 0 .. n-1)
Note: synthetic divide by (x-0) step skipped, since x^6 = (x-0)*x^5 + 0
x^6 = x6 + 15 x5 + 65 x4 + 90 x3 + 31 x2 + x1
From problem 12, Σ(xm, x=0 to n-1) = nm+1 / (m+1)
s6(n) = n7/7 + 15 n6/6 + 65 n5/5 + 90 n4/4 + 31 n3/3 + n2/2
After simplify, s6(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.
Example, find s6(n) = Σ(x^6, x = 0 to n-1)
Convert x^6 to falling factorial form, where xn = 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
x^6 = x6 + 15 x5 + 65 x4 + 90 x3 + 31 x2 + x1
From problem 12, Σ(xm, x=0 to n-1) = nm+1 / (m+1)
s6(n) = n7/7 + 15 n6/6 + 65 n5/5 + 90 n4/4 + 31 n3/3 + n2/2
After simplify, s6(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.