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
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.

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search