Solution Notes
The answer is 0. I received only a few comments and solutions. Thanks to Michael Elgersma for a comprehensive discussion. His notes are linked to below. Witold Jarnicki (Krakow, Poland) got the Grobner basis (using WolframAlpha.com) for the four polynomials; the first entry gives a recursion for getting the sum of any powers. This is a fine approach, but it will be slower in general than working out the recurrence in other ways. You can see exactly how he did it at:
http://tinyurl.com/l4arey5
In Mathematica it is just:
GroebnerBasis[{a+b+c+d-1,a2+b2+c2+d2,a3+b3+c3+d3-1,a4+b4+c4+d4},{a,b,c,d}]
The first polynomial of the output is
3-4 d+4 d2-8 d3+8 d4
which corresponds to the recurrence that can be obtained by other means (see below).
I received one solution that solved the system numerically to conclude that the answer was likely 0. I received one incorrect solution.
Yan Chen (Undergraduate in Guanghua School of Management, China) sent me a handwritten solution within about two hours of the posting of the problem, and it was perfectly correct, working out the recursion by hand. And a nicely written up and perfect solution was also submitted by Zhu Jiaxin, of the same school in China).
The key is the Newton identities (see http://en.wikipedia.org/wiki/Newton's_identities). Michael Elgersma has written up some brief notes explaining the ideas. View the PDF:
click on image to view PDF
The main idea is that any initial segment of power sums of n variables, such as the ones in the problem, leads, in an efficient manner, to a recurrence that quickly generates as many of the higher powers as one wants. This was how I found the cute sequence (x, 0, y, 0), for which the infinite sequence of power sums always has a 0 in the 10th position, regardless of the values of x and y.
This recurrence yields the sequence of all power sums:
(b(1), b(2), b(3), b(4)) = {1, 0, 1, 0}
b(m+4)= b(m+3) - (1/2) b(m+2) + (1/2) b(m+1) -3/8 b(m)
For the problem posed, and using arbitrary values in place of the two 1s, this leads to the following for the first 10 values:
{x, 0, y, 0, (-3x - 4y)/8,
(-3x)/8, (-3x - 2y)/16, (-3(x + 2y))/16, (-9x - 8y)/64, 0}
Here is complete Mathematica code to generate as many terms of the sequence as one likes, for any initial segment that consists of numbers or symbols. Again, the details of the method are in the linked pdf.
RecurrenceCoeffs[b_] := With[{n = Length[b]},
Reverse[LinearSolve[Transpose[
Table[PadLeft[Prepend[Take[b, n - i], i], n], {i, n}]], b]]];
PowerSequence[b_, M_] := Module[
{n = Length[b], s = PadRight[b, M], c = RecurrenceCoeffs[b]},
Do[s[[i]] = c . Take[s, {i - n, i - 1}], {i, n + 1, M}];
s];
PowerSequence[{1, 0, 1, 0}, 10][[10]]
0
Here is the general formula for the 10th term starting with any four values.
PowerSequence[{x, y, z, w}, 10][[10]] // Simplify
(180 w^2 (2 x^2 + y) - 20 w (x^6 - 12 x^4 y + 9 x^2 y^2 + 16 x^3 z - 24 x y z -
8 z^2) - y (5 x^8 - 40 x^6 y + 30 x^4 y^2 + 9 y^4 + 80 x^5 z -
160 x^3 y z + 240 x y^2 z + 320 x^2 z^2 - 160 y z^2))/576
Here is the 200th term of the sequence that begins 1,2,3,...,19
PowerSequence[Range[19], 20][[20]]
2205128748183225281/121645100408832000
The Lucas numbers are interesting. The numbers are formed by starting with 1, 3 and using the Fibonacci sum rule.
LucasL[Range[10]]
{1, 3, 4, 7, 11, 18, 29, 47, 76, 123}
The power recurrence turns out to be the standard Fibonacci recurrence.
RecurrenceCoeffs[LucasL[Range[10]]]
{0, 0, 0, 0, 0, 0, 0, 0, 1, 1}
It follows that the power sequence starting with (1,3) yields the full Lucas sequence
PowerSequence[{1, 3}, 10]
{1, 3, 4, 7, 11, 18, 29, 47, 76, 123}
We can get the recurrence coefficients symbolically!
RecurrenceCoeffs[{x, y}]
{(y-x^2)/2, x}
So if x and y have the same parity, we can start with (x, y) and get a sequence of integers.
PowerSequence[{3, 7}, 10]
{3, 7, 18, 47, 123, 322, 843, 2207, 5778, 15127}
[Back to Problem 1182]
© Copyright 2014 Stan Wagon. Reproduced with permission.