Finite differences

If f(x) is a function on integers, the forward difference operator is defined by

\Delta f(x) = f(x+1) - f(x)

For example, say f(x) = x2. The forward difference of the sequence of squares 1, 4, 9, 16, … is the sequence of odd numbers 3, 5, 7, …

There are many identities for the forward difference operator that resemble analogous formulas for derivatives. For example, the forward difference operator has its own product rule, quotient rule, etc. These rules are called the calculus of finite differences. The finite results are often much easier to prove than their continuous counterparts.

The calculus of finite differences makes it possible to solve some discrete problems systematically, analogous to the way one would solve continuous problems with more familiar differential calculus. For example, there is a “summation by parts” technique for computing sums analogous to integration by parts for integrals.

The product rule for forward differences looks a little odd:

\Delta(f(x)g(x)) = g(x) \Delta f(x) + f(x+1) \Delta g(x)

The left hand side is symmetric in f and g though the right side is not. There is also a symmetric version:

\Delta(f(x)g(x)) = g(x) \Delta f(x) + f(x) \Delta g(x) + \Delta f(x) \Delta g(x)

Here is the quotient rule for forward differences.

\Delta \frac{f(x)}{g(x)} = \frac{g(x) \Delta f(x) - f(x) \Delta g(x)}{g(x)g(x+1)}

One of the first things you learn in calculus is how to take the derivative of powers of x: the derivative of xn is n xn-1. There is an analogous formula in the calculus of finite differences, but with a different kind of power of x. For positive integers n, define the nth falling power of x by

x^{(n)} \equiv x(x-1)(x-2)\cdots(x-n+1)

Then

\Delta x^{(n)} = nx^{(n-1)}

Falling powers can be generalized to non-integer exponents by defining

x^{(n)} \equiv \frac{\Gamma(x+1)}{\Gamma(x-n+1)}

The formula for finite difference of falling powers given above remains valid when using the more general definition of falling powers. Falling powers arise in many areas: generating functions, power series solutions to differential equations, hypergeometric functions, etc.

The function 2x is its own forward difference, i.e.

\Delta 2^x = 2^x

analogous to fact that ex is its own derivative.

Here are a couple more identities showing a connection between the gamma function and finite differences. First,

\Delta \Gamma(x) = (x-1)\Gamma(x)

Also,

\Delta \log \Gamma(x) = \log(x)

To read more about the calculus of finite differences, see Concrete Mathematics.

11 thoughts on “Finite differences

  1. John,
    Thanks for posting this: I would be interested to see some applications. Would you believe that in my four year degree course on Mathematics we never covered this subject!

    Sam

  2. Sam, I got a PhD in math without ever seeing this. I worked with finite differences as approximations, but I never saw this elaborate calculus for working with finite differences until sometime after I was out of school.

    Notice there’s no approximation going on here, only exact results. These tools can be used to solve discrete problems with no reference to ordinary calculus.

  3. I’ve listened some older teachers telling about this but I never had the chance to study with details. I’ve been using foward and backward operators but didn’t know there were calculus-like rules. Thanks for the post.

  4. John,

    “Discrete Calculus” is indeed very interesting. I only discovered its existence last year, and I was immediately intrigued by it.

    You mentioned the “summation by parts” technique. Another cool technique of discrete calculus that bears resemblance with continuous calculus is the “discrete l’Hôpital’s rule”, i.e., the Stolz-Cesàro theorem.

  5. So which function should be considered the discrete analogue (no pun) of the logarithm function? Log base 2 , or H(n), the nth harmonic number?

  6. Jack, it depends on which analogy you want to draw. Log base 2 is analogous to the natural logarithm in that it is the inverse of 2x. But the harmonic numbers are analogous to the natural logarithm in that Δ Hn = 1/n, just as the derivative of ln(x) is 1/x.

  7. Thanks muchly for this informative post. whilst I look forward to your followup on summation by parts, I jumped the gun a little and derived the formula from the product rule (since that’s the easiest way in infinitesimal calculus), with a bit of effort I used it to glean a summation formula for [k^n from k = 1 to x] with any chosen n in terms of the summation formulae for lower values of n.

    Very satisfying result for me, feel like I’m much more apt with sums now that I have this ‘disctrete calculus’ in my toolkit and some practice under my belt.

  8. John, how is the gamma function defined for which you discover that the difference of gamma(x) = (x – 1)gamma(x)? Are you using the continuous (integral) definition? Since you reference non-integers, I assume so. I did check out your link but only saw graphs of the gamma function. It doesn’t feel right to me to use the integral definition, considering this is dealing with discrete calculus. Of course, it is easy to show this relationship for the factorial function.
    I must say, though, that I have enjoyed learning about discrete calculus over the past few months.

Comments are closed.