Sum of Powers of Positive Integers

Many people have seen formulas for the sum of the first $n$ positive integers, or the sum of their squares or cubes. But what about finding a formula for the sum of the $n^{\text{th}}$ powers of these integers? We show a recursive method of finding polynomial formulas for $$1^k + 2^k + \cdots + n^k$$ that is due to Pascal.