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