It has been pointed out (see KConrad's answer) that the usual proof that the sum of the first $n$ squares is $n (n+1) (2n+1)/6$ does not give insight.  However, I would like to show that a *different* inductive proof of this fact does give insight.  Instead of performing induction on $n$, we can perform induction on the *exponent*.  This approach is very instructive because it shows that the sum of the first $n$ $k$th powers is a polynomial in $n$.  It also shows how we can derive the formula for *any* exponent given that we know the formulas for all the smaller exponents.  Thus, in principle the only formula we need to know is that $1 + 2 + \dots n = n(n+1)/2$, which has a beautiful proof by picture [here](http://mathoverflow.net/questions/8846/proofs-without-words). 

I will illustrate this idea by computing the sum of the first $n$ squares.  

Observe that

$(n+1)^3-1=\sum_{i=1}^n (i+1)^3 -i^3 = \sum_{i=1}^n 3i^2 + 3i +1$.

Thus,

$3\sum_{i=1}^n i^2 = (n+1)^3-1 - n - 3 \sum_{i=1}^n i$.

However, we have already inductively determined that $\sum_{i=1}^n i = n(n+1)/2$.  Thus, substituting and solving yields

$\sum_{i=1}^n i^2 = n (n+1)(2n+1)/6$,

as required.  

We can now compute the sum of the first $n$ cubes using the same technique, given that we now know the sum of the first $n$ integers and the sum of the first $n$ squares.  This gives a systematic way to compute the sum of the first $n$ $k$th powers, and why it is a polynomial in $n$ of degree $k+1$.