Sum of squares

[gholizad]

I know the formula for sum of squares:

1^2+2^2+3^2+...+n^2=n(n+1)(2n+1)/6

but I have no idea how to prove it other than induction. I know there is usually a little trick to manipulate these kind of series to find the sum. Does anyone know how to do it for this case?

[blah_blah]

What are you really asking? Do you want a proof besides induction, or a way to find the result? By considering successive differences, we can find that p(n) = \sum_{1\leq i\leq n} i^2 is a polynomial of degree 3 and the coefficients of said polynomial.

If you just want to make the guess that p(n) is a polynomial of degree 3 (for example, by comparison to a riemann sum), then you can use Lagrange interpolation to find the unique polynomial of degree 3 with

p(0)=0
p(1)=1
p(2)=5
p(3)=14

or you can set up a system of equations to find the unique third degree polynomial p which satisfies p(n+1)=p(n)+(n+1)^2 for all positive integers n. There are many other proofs (combinatorial, geometric) but these seem the most natural to me.

[borisp]

One general trick for sums is "summation by parts." Essentially, it is the discrete version of integration by parts. Suppose you have finite sequences a_1,...,a_n and b_1,...,b_n. Then the following holds:

a_2 (b_2 - b_1) + a_3 (b_3 - b_2) + ... + a_n (b_n - b_(n-1)) = (a_n b_n - a_1 b_1) - (b_1 (a_2 - a_1) + ... + b_(n-1) (a_n - a_(n-1))

The trick here is to let a_n = n, and "find" b_n so that b_n - b_(n-1) = n. But presumably you already did that! (since that is simply the exponent 1 ie baby Gauss solution case). So let b_n = n(n+1)/2 = n^2/2 + n/2. The LHS is one less than what you want, call it P(n)-1, and notice the RHS is

n(n)(n+1)/2 - 1 - (P(n)/2 - n^2/2) - n(n-1)/4

using that we already "know" the sums of n^2/2 and n/2, and correcting for the indexing. Now just solve for P(n):

3P(n)/2 = (n^3 + n^2)/2 + n^2/4 +n/4

P(n) = n^3/3 + n^2/2 + n/6 = what you want.

This isn't easier necessarily, but it is a general technique that can tackle these summation problems.