If f(x) is a function on integers, the forward difference operator is defined by
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 ordinary calculus. For example, there is a “summation by parts” technique for computing sums analogous to integration by parts for integrals. This is quite useful technique and I intend to write a separate post on it.
The product rule for forward differences looks a little odd:
The left hand side is symmetric in f and g though the right side is not. There is also a symmetric version:
Here is the quotient rule for forward differences.
One of the first things you learn in calculus is how to take the derivative of powers of x. If f(x) = xn then f‘(x) = 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
Falling powers can be generalized to non-integer exponents by defining
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.
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,
I plan to write posts in the future about summation by parts and the connection between harmonic numbers and logs.
To read more about the calculus of finite differences, see Concrete Mathematics.
For daily posts on analysis, follow @AnalysisFact on Twitter.