Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

The Sum of the First N Squares


Date: 02/20/98 at 14:22:23
From: Rob Agosto
Subject: Algorithms

I don't know where to begin.

I have to formulate a formula for the sum of the first N squares
(i.e. 1^2 + 2^2 + 3^2+.....+N^2) by mathematical induction.


Date: 03/12/98 at 15:19:17
From: Doctor Sonya
Subject: Re: Algorithms

Hi, Rob:

I'm not quite sure what exactly you are supposed to do in this 
problem. To "formulate" means to find a formula. You never use 
mathematical induction to find a formula, only to prove whether or not 
a formula you've found is actually true. Therefore I'll assume that 
you want to find a formula for the sum of the first n squares, and 
then prove that the formula is right using mathematical induction.

First, let me give you a brief account of how a "mathematical 
induction" works. 

  a) When do we use "mathematical induction"? 

     Well, we sometimes encounter such problems where the behavior of  
     a series of numbers or expressions SEEMS to change in a fixed  
     manner.  Here, I emphasize "SEEMS" because we do not know for  
     sure if a certain formula works or not.  

     For example, after looking at some numbers, I might guess that   
     the sum of the first n squares can be found by the formula:

         (1/2)(n^2 +14). 

     However, I cannot say that this formula works for every n,  
     because I really didn't try it with EVERY n, just with some of  
     them. In such cases that involve natural numbers (1,2,3...),  
     mathematical induction is a way to find a proof without having to  
     spend eternity plugging values of n into the formula. 

  b) What are the steps of a typical "mathematical induction"?
     1) To show that when n = 1, the formula is true.
     2) Assuming that the formula is true when n = k.  
     3) Then show that when n = k+1, the formula is also true.

     According to the previous two steps, we can say that for all n  
     greater than or equal to 1, the formula has been proven true. 

Now, you may find the above explanation too abstract. So, let's 
just take your question as an example.

We want to find the formula for 1^2+2^2+3^2+...+n^2.  Now, I'm going 
to assume that you have already thought a lot about this problem, and 
you have a pretty good guess that the sum of the first n squares is:

    n (n + 1) (2*n + 1)
    ------------------
           6            (N.B. 2*n means "2 times n")

However, we still don't know if this formula is true for all n, 
because we never tried it with n = 1,235,822 or n = 677,331 or 
millions of others.  That's where proof by induction comes in: it will 
allow us to say that this formula it true for ALL n without having to 
test them all.

Now, we're ready for the three steps.

1. When n = 1, the sum of the first n squares is 1^2 = 1.  Using the  
   formula we've guessed at, we can plug in n = 1 and get: 

     1 (1+1) (2*1+1)/6 = 1

   So, when n = 1, the formula is true.

2. Now we'll assume that when n = k (for some k that's greater than or  
   equal to 1), the formula is also true.  What this means is that
   we're just going to declare that our formula is true for k.
 
   1^2+2^2+3^2+...+k^2 = k (k+1) (2*k+1)/6 
   
3. Now we're going to try to prove, using the assumption from step 2,  
   that the formula is true for n = k + 1.

   The series we need to compute is 

   1^2+2^2+3^2+...+k^2+(k+1)^2.

   Since we already made an assumption about the sum of the first n 
   squares (step 2), we can replace the part before 
  
   (k+1)^2 by k*(k+1)*(2*k+1), and get the following:

   1^2+2^2+3^2+...+k^2+(k+1)^2 = k (k+1) (2*k+1)/6 + (k+1)^2
   
   Now we work on the right part of the equation to try to make it   
   into our formula for n = k+1.  

   I would like to leave this part of the work to you.  Just remember   
   that our formula says that the sum of the first k+1 squares is:

   (k+1)*((k+1)+1)*(2*(k+1)+1)/6)

4. Now, say what you've proved.
    
Okay, that's quite enough. Good luck finishing the proof! :)
If you still have questions, don't hesitate to write again.

Also, I suggest you take a look at the following page in our archives: 

  http://mathforum.org/dr.math/problems/chessboard.html   

I'm sure you'll find it helpful!

-Doctors Sonya and Elizabeth,  The Math Forum
 Check out our Web site http://mathforum.org/dr.math/   
    
Associated Topics:
High School Basic Algebra

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/