Induction question - sums

Question

I just proved $\sum_{i=1}^n i^3 = [\frac{n(n+1)}{2}]^2$ using mathematical induction. I have to prove it for $i^4$ now. So would that be

$\sum_{i=1}^n i^4 = [\frac{n(n+1)}{2}]^3$ ?

Answer 1

Let's take a look at the "previous" formulas: $$ \sum_{i=1}^{n}i=\frac{n(n+1)}{2}\qquad\sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}\qquad\sum_{i=1}^{n}i^3=\frac{n^2(n+1)^2}{4} $$ In each case, we find that if you think of these as a function of $n$, they are polynonomials; further, the degree of that polynomial always exceeds the power of $i$ by $1$. (So the sum of $i=i^1$ gives degree $2$; etc.)

Generalizing, it is reasonable to suspect that when we sum fourth powers, we should get a degree $5$ polynomial in $n$ as a result. Let's assume that's the case, and work backwards.

Say that $$ f(n):=\sum_{i=1}^{n}i^4=a_5n^5+a_4n^4+a_3n^3+a_2n^2+a_1n+a_0. $$ Plugging in $n=0$, we should get $0$ (the empty sum); so, we see that $a_0=0$.

Now, we know that for any $n\geq 1$, $$ f(n+1)=f(n)+(n+1)^4,\qquad\text{or}\qquad f(n+1)-f(n)=(n+1)^4. $$ We compute $$ f(n+1)-f(n)=a_5[(n+1)^5-n^5]+a_4[(n+1)^4-n^4]+\cdots+a_1[(n+1)-n]. $$ You can expand out the powers on the right side, then remember that this must be equal (as a polynomial) to $(n+1)^4=n^4+4n^3+6n^2+4n+1$. This will allow you to explicitly solve for the coefficients.

Answer 2

Define falling factorial powers by: $$ u^{\underline{m}} = u (u - 1) \ldots (u - m + 1) $$ It is easy to prove by induction that: $$ \sum_{1 \le k \le n} k^{\underline{m}} = \frac{n^{\underline{m + 1}}}{m + 1} $$ Now you can write $u^m$ as a combination of $u^{\underline{r}}$ for $0 \le r \le m$, and thus cobble up a formula for the sum you are looking for.

There is in fact a general formula for sums of powers involving Bernoulli numbers.