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)