Subscribe to Macosxnerd101's Blog

## Discrete Calculus and Sums of Powers

Have you ever wanted to know why \sum_{i=0}^{n} i = n(n+1)/2? The obvious proof is by induction, but it doesn't give us insight as to how we got the formula. I'll show you how to derive these formulas using discrete calculus.

We can actually derive this solution for any sum of powers using discrete calculus. We need a few things:
-The falling factorial
-The discrete derivative
-The discrete integral

The falling factorial is pretty straight-forward. We denote it as follows: xn = x(x-1)(x-2) ... (x - (n-1)).

So n3 = n(n-1)(n-2).

We now want a discrete derivative. In regular calculus, we have our difference quotient: lim_{x \to a} [f(x) - f(a)]/(x - a). In discrete calculus, we're dealing with integers, not reals. So our difference is 1. We have: Df(x) = f(x + 1) - f(x).

So now the interesting part is that Dxn = nxn-1.

And of course, our discrete integral is a sum which reflects the correlation to integration of a polynomial power in continuous calculus: Integral( xn ) = xn+1/(n+1) (in the continuous case).

In the discrete case, we get that \sum_{x=a}^{b-1} xi = (bi+1 - ai+1)/(i+1).

So for example, the discrete integral of x2 from 0 to 5 is x3/3 = x(x-1)(x-2)/3 = 5 * 4 * 3/3 = 20.

Now, let's put it all together. The trick is to write the power in terms of falling factorials. So:
x = x1
x2 = x2 + x1 = x(x-1) + x

We then take a discrete integral and do some algebra. So for your case of \sum_{i=0}^{n} i = (n+1)2/2 = n(n+1)/2.

If we consider the case of \sum_{i=0}^{n} i2 = \sum_{i=0}^{n} (i2 + i) = i(i+1)(i-1)/3 + (i+1)i/2. Doing some algebra gets us n(n+1)(2n+2)/6 as the answer for the summation.

There is actually a closed form solution using Stirling Numbers of the Second Kind to rewrite xn in terms of sums of falling factorials. I will use S(n, k) to denote Stirling Numbers of the Second Kind.

I note S(n + 1, k) = k * S(n, k) + S(n, k-1), with S(0, 0) = 1 and S(0, n) = S(n, 0) = 0. There is also an explicit formula for Stirling Numbers of the Second Kind, provided on the Wikipedia link.

So xn = \sum_{i=0}^{n} S(n, k) xk. (Note that if the x in the summation isn't being parsed correctly. It should be a falling factorial- [il]x[u]k).

Thus, we can derive a closed-form solution for any sum of powers, giving us an Theta(1) solution as opposed to Theta(n).

S M T W T F S
123 4
567891011
12131415161718
19202122232425
2627282930