How do I derive $1 + 4 + 9 + \cdots + n^2 = \frac{n (n + 1) (2n + 1)} 6$ 
Possible Duplicate:
Proof that $\sum\limits_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$? 

I am introducing my daughter to calculus/integration by approximating the area under y = f(x*x) by calculating small rectangles below the curve. 
This is very intuitive and I think she understands the concept however what I need now is an intuitive way to arrive at $\frac{n (n + 1) (2n + 1)} 6$ when I start from $1 + 4 + 9 + \cdots + n^2$. 
In other words, just how came the first ancient mathematician up with this formula - what were the first steps leading to this equation? That is what I am interested in, not the actual proof (that would be the second step).
 A: Same as you can prove sum of n = n(n+1)/2 by 
*oooo
**ooo
***oo
****o

you can prove $\frac{n (n + 1) (2n + 1)} 6$ by building a box out of 6 pyramids:



Sorry the diagram is not great (someone can edit if they know how to make a nicer one). If you just build 6 pyramids you can easily make the n x n+1 x 2n+1 box out of it.


*

*make 6 pyramids (1 pyramid = $1 + 2^2 + 3^2 + 4^2 + ...$ blocks)

*try to build a box out of them

*measure the lengths and count how many you used.. that gives you the formula


Using these (glued) 
A: HINT: Use the fact that $(k+1)^3=k^3+3k^2+3k+1$
A: There is a nice proof without words here : http://www.usamts.org/About/U_Gallery.php
Its a geometric proof of sorts which I guess could count as more intuitive than the somewhat contrived induction.
A: hint:let $a_n=1+2^2+...+(n)^2$ then $a_n-a_{n-1}=n^2-(n-1)^2$ then use recursive relation to prove $a_n= \frac{n (n + 1) (2n + 1)} {6}$  totally let $a_n=\sum_{j=1}^\infty c_ja_{n-j} +f(n) $ in your question $f(n)=An^k$ then compute $a_n^p$ and$a_n^g$ then $a_n=a_n^p+a_n^g$
A: Try using $(n+1)^3-n^3=3n^2+3n+1$. Take the sum of both sides.
