How Is the Sum of Squares Formula Derived Using Induction?

[rsala004]

this is to figure out formula for how many squares you can find in a nxn box.

1²+2²+3²+...+N²

Can someone show steps to how a simplified formula can be found? ( i only know the concept of induction, not how to do it really..)

it is (n)(n+1)(2n+1)/6 , but how is this accomplished

thanks a lot, would be great if some work was shown.

 

[berkeman]

this is to figure out formula for how many squares you can find in a nxn box.

1²+2²+3²+...+N²

Can someone show steps to how a simplified formula can be found? ( i only know the concept of induction, not how to do it really..)

it is (n)(n+1)(2n+1)/6 , but how is this accomplished

thanks a lot, would be great if some work was shown.

What is the context of the question? Is this for school work?

 

[rsala004]

http://www.spoj.pl/problems/SAMER08F/

 

[rasmhop]

First show the base case:
1^2 = 1
Then assume:
$$1^2+2^2+\cdots+n^2 = \frac{n(n+1)(2n+1)}{6}$$
Now add $(n+1)^2$ to get:
$$1^2+2^2+\cdots+n^2+(n+1)^2 = \frac{n(n+1)(2n+1)}{6}+(n+1)^2$$
Now your task is do manipulate the right hand side to get:
$$\frac{n(n+1)(2n+1)}{6}+(n+1)^2 = \frac{(n+1)(n+2)(2n+3)}{6}$$
which would prove the induction hypothesis that if the formula is true for n, then it's true for n+1.

If you do this you show the theorem true for n=1 and therefore also by n=2, and therefore also for n=3, and therefore also for n=4, ... So by induction you have shown it true for all positive n.