A proof for this series?

The summation, $$\sum_{i=1}i^2=n(n+1)(2n+1)/6$$ However, how could you prove this? All of the proofs I've seen already assume knowledge of the formula, but how do you prove this without first knowing the formula? What about formulas for higher powers, such as cubics and quartics? If possible, please keep this on a level where I can understand (I'm in calculus AB). Thanks!

• possible duplicate of Power summation of $n^3$ or higher which was itself closed as a duplicate. But the answers there seemed closer to what was wanted here. If you search the site for Faulhaber you will find many versions. – Ross Millikan May 4 '13 at 23:22
• @Daniel: she asked for a proof that "doesn't assume knowledge of the formula." Induction only helps once you know what the formula should be. – symplectomorphic May 4 '13 at 23:23
• There's a nice proof here: proofwiki.org/wiki/Sum_of_Sequence_of_Squares/Proof_4 – Harry Williams May 4 '13 at 23:23
• So you don't really want a proof of this, you want a way to figure this out, which is different. You can't "prove this without knowing the formula," because "this" includes the formula. There are general ways to solve this sort of problem, however - if $p(x)$ is a polynomial, there is a general way to figure out $\sum_{0}^{n-1} p(i)$. – Thomas Andrews May 4 '13 at 23:23
• It is a fact that $p(k):=\sum_{i=1}^k i^n$ is a polynomial of degree n+1. May be this will help you feel how one deduces the formula. – Amr May 4 '13 at 23:24

Polya gives a beautiful discussion of this problem in Chapter 3 (called "Recursion") in volume 1 of his book "Mathematical Discovery." One way to "discover" the formula is to exploit the identity $$(n+1)^3=n^3+3n^2+3n+1$$ which implies $$(n+1)^3-n^3=3n^2+3n+1$$ If you sum all such equations from $n=1$ to $n=k$ you find the left side telescopes, leaving $$(k+1)^3-1=3S+3(1+2+\cdots+k)+k$$ where $S$ is the sum you wanted. Of course, the sum in parentheses is just $\frac{k(k+1)}{2}$, and solving the equation for $S$ after making that substitution gives the result.

In my opinion, the "best" way is doing it as a telescoping sum:

$$\sum_{k=1}^n 3k^2 = \sum_{k=1}^n \big((k+1)^3 - k^3\big) - \sum_{k=1}^n 3k - \sum_{k=1}^n 1$$

and each of the sums in the right hand side is easy to work out.

Wilf's "generatingfunctionology" gives the general solution doing the following: Take: $$\sum_{0 \le k \le n} z^k = \frac{1- z^{n + 1}}{1 - z}$$ Now note that each time you apply $z \dfrac{d}{dz}$ you multiply $z^k$ by $k$. Differentiate $m$ times, and evaluate the result on the right hand side by applying l'Hôpital ad nauseam.

One way of getting the general formula is to start with: $$G(z) = \frac{z (e^{m z} - 1)}{e^z - 1} = \frac{z}{e^z - 1} \cdot \frac{1}{e^{m z} -1}$$ The first form, expanded first as a finite geometric sum in $e^z$ and then each term in $z$ gives a series with $S_m(n) = \sum_{0 \le k \le n} k^m$ in the coefficient, the second one is the generating function for the Bernoulli numbers by a geometric series in $e^{m z}$, expanding and equating terms gives: $$S_m(n) = \frac{1}{m + 1} \sum_{k \ge 1} \binom{m + 1}{k} B_{m + 1 - k} (n + 1)^k = \frac{1}{m + 1} \sum_{k \ge 0} \binom{m}{k} B_{m - k} \frac{n^{k + 1}}{k + 1}$$ The Bernoulli number page gives much more details. There are other simple ways to get there.

Another way is to note that if you define $z^{\overline{m}} = z (z + 1) \ldots (z + m - 1)$ then: $$\sum_{0 \le k \le n} k^{\overline{m}} = \frac{n^{\overline{m + 1}}}{m + 1}$$ As $x^m$ can be expressed as a combination of $x^{\overline{k}}$, the sum $S_m(n)$ can in turn written down.

Yet another take was Faulhaber's, as brilliantly exposed by Knuth in "Johann Faulhaber and sums of powers"