#1
|
|||
|
|||
Sum of squares
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? |
#2
|
|||
|
|||
Re: Sum of squares
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. |
#3
|
|||
|
|||
Re: Sum of squares
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. |
|
|