Comment by gordaco

Induction is also a very good way to prove these formulas. In fact, these are just perfect textbook exercises for someone learning induction: try to find formulas for the sum of the first k-th powers (for some not so big integer k), then prove the formulas using induction. As someone else mentions, the formulas themselves are related to the Bernoulli numbers and have some surprising properties, like how formulas for odd values of k can be expressed in terms of k·(k+1)/2.