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.

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

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.

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

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.

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 formula for any $k$th power, and why it is indeed a polynomial in $n$.

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.

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