## Sum of integer powers

This came up while preparing for CSE 326 section. Perhaps you are aware that Gauss is credited with discovering the sum of the first *n* integers as a schoolboy according to mathematical folklore. In one of Feynman’s lectures (I forget which one), he presents a nice pictorial view of a staircase of blocks which is equivalent to Gauss’s formula. Thinking pictorially, the sum of integer squares can be represented as a double sum reducing to the base case of integers. By meta-induction, the sum of successive integer powers can be solved using all sums of lower powers. Then the puzzle is simply this: is there a closed form solution for the general sum of integer *k*-powers? It’s known to be approximable by n^{k+1}, but c’mon now, Gauss’s dog could have guessed that. I haven’t actually solved this problem yet, but it may involve inventing some new notation. Again, solutions should be posted in the comments.