ndatta's blog

By ndatta, history, 4 years ago, ,   Comments (2)
 » 4 years ago, # | ← Rev. 2 →   Here's my understanding of the solution provided in your link:A sufficiently 'nice' sum that depends only on N will be a polynomial on N. I don't have a definition of 'nice' or a proof that this sum is 'nice', but several examples should convince you of this — or or .Furthermore, the degree of the polynomial should be 10. We're multiplying five terms and summing over five variables. Again, take a look at the above examples — the third one should be a degree-three polynomial in N, as we are multiplying one term and summing over two variables.Unfortunately, we don't know the coefficients of this magical 10th degree polynomial. However, we can find them if we have 10 linear equations in terms of these coefficients. Let P(N) = c10x10 + ... + c1x + c0. Then our desired equations are P(Ni) = c10(Ni)10 + ... + c1Ni + c0 for 10 different Ni, where P(Ni) must be calculated manually or with a slow program.Finally, we put these equations into an augmented matrix and use Gaussian elimination to solve for the 'variables', which are the 10 coefficients ci. Now we simply evaluate P(N) for each given N.