Analytical SolutionDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/