vitalik.eth@VitalikButerin
Proof:
[Lemma] sum(i=1..x) [degree n-1 polynomial] = [degree n polynomial]
Proof of lemma:
* Notice that x^n - (x-1)^n = x^n - x^n + nx^(n-1) - ... +- 1 = [degree n-1 polynomial, call it C(x)]
* Hence by telescoping sums, sum(i=1..x) C(i) = x^n
* Given any specific degree n-1 polynomial D(x), re-express it as D(x) = some k * C(x) + [deg <= n-2 stuff]. By induction on n, and by linearity, sum(1..x)D(i) = k * x^n + [deg <= n-1 stuff].
Therefore, sum(i=1...x) i^3 is degree 4, and (sum(i=1...x) i)^2 is degree 2*2 = 4.
Now, explicitly evaluate (sum(i=1...x) i)^2 and sum(i=1...x) i^3 on x=1...5, answers are: 1, 9, 36, 100, 225 in both cases
The two deg-4 polynomials are the same on five points, therefore they are equal
Therefore sqrt(sum(i=1...x) i^3) = sum(i=1...x)
