Analytical Solution

Date: 12/01/97 at 17:54:17
From: Mamdouh Atia
Subject: Algebra

Dear Dr. Math,

Do you think you can give me an analytical solution of

(sum(from k=1 to N) of k^2) in terms of N?

Mamdouh

Date: 12/01/97 at 18:17:29
From: Doctor Pete
Subject: Re: Algebra

Hi,

Allow me to introduce some notation.  I will write

     Sum[F[n], {n,a,b}]

to mean the sum of a function F[n] from n = a to n = b. Now, what you 
wish to find is

     S[N] = Sum[k^2, {k,1,N}].

Theorem:  S[N] = N(N+1)(2N+1)/6.

Proof:  Consider the expression

     F[k] = (k+1)^3 - k^3
          = (k^3 + 3k^2 + 3k + 1) - k^3
          = 3k^2 + 3k + 1.

Then

     Sum[F[k], {k,1,N}] = Sum[(k+1)^3-k^3, {k,1,N}]
                        = (2^3-1^3) + (3^3-2^3) + ... + (N^3-(N-1)^3)
                            + ((N+1)^3-N^3)
                        = (N+1)^3 - 1^3
                        = N^3 + 3N^2 + 3N,

since this is clearly a telescoping series.  But we may also write

     Sum[F[k], {k,1,N}] = Sum[3k^2 + 3k + 1, {k,1,N}]
                        = 3 Sum[k^2, {k,1,N}] + 3 Sum[k, {k,1,N}]
                            + Sum[1, {k,1,N}]
                        = 3 Sum[k^2, {k,1,N}] + 3N(N+1)/2 + N
                        = 3 S[N] + 3N(N+1)/2 + N,

since Sum[k, {k,1,N}] = 1 + 2 + ... + N = N(N+1)/2.  So

     3 S[N] + 3N(N+1)/2 + N = N^3 + 3N^2 + 3N,

or

     S[N] = (N^3 + 3N^2 + 2N - (3/2)N^2 - (3/2)N)/3
          = (N^3 + (3/2)N^2 + (1/2)N)/3
          = N(2N^2 + 3N + 1)/6
          = N(N+1)(2N+1)/6,

which is what was to be proved.

Comments:  Notice that we used the fact that 1+2+...+N = N(N+1)/2; 
hopefully, you are familiar with this formula.  It follows easily by 
writing

     1  +  2  + ... + N-1 +  N
     N  + N-1 + ... +  2  +  1
    ---------------------------
    N+1 + N+1 + ... + N+1 + N+1

so twice this sum is equal to N(N+1), or the sum is half of this, 
which is N(N+1)/2.  Also, observe that we could use the same method to 
find

     Sum[k^3, {k,1,N}] = (N(N+1)/2)^2

by summing the expression (k+1)^4 - k^4 in two different ways.  
In fact, if we were to know S[p,N] = Sum[k^p, {k,1,N}], for 
p = 1, 2, 3, ..., P-1, then we can find S[P,N] by the same method.  
But this involves a lot of recursive computation, which is 
impractical. There is a general formula of S[p,N], which involves 
special numbers called Bernoulli numbers. The proof is not 
particularly difficult, but it does involve some more powerful 
number-theoretic tools.

Hope this answers your question,

-Doctor Pete,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/