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!
 A: 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.
A: 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.
A: 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"
