Difference Equations, nth Difference is Constant

nth Difference is Constant

The simplest nth order equation sets the nth difference to a constant c. By the previous theorem, the solutions form an n dimensional space, corresponding to the vectors of initial conditions.

For any set of initial conditions, and any constant c, the solution is always an nth degree polynomial. This is similar to differential equations, where repeated integration yields a polynomial. Of course the polynomials are not the same. Consider y′′ = 2, with y(0) = 3 and y′(0) = 0. If this were a differential equation, the solution would be y(x) = x2+3. When viewed as a difference equation, the solution is x2-x+3. (We'll see this below.)

To help us solve these equations, we are going to generalize the binomial coefficient. As you recall, (n:j) is n times n-1 times n-2 … down to n-j+1, divided by j factorial. Although n is usually a number, it could be a variable, such as x. Thus (x:2) = x×(x-1)/2, and (x:3) = x×(x-1)×(x-2)/6. By definition, (x:0) = 1.

Here is the power behind this construction. If y(x) = (x:j), then y′(x) = (x:j-1). Take a moment to verify this; it's beautiful.

If the initial conditions are all zero, the solution to our nth order difference equation is y = c×(x:n). The jth difference sequence is c×(x:n-j), and this equals 0 when evaluated at 0. The nth difference equals c×(x:0), which is just c.

In the above example, think of c as cn. Let c0 through cn-1 represent the initial conditions. In other words, y(0) = c0, y′(0) = c1, y′′(0) = c2, and so on. As before, the nth difference is set to the constant cn. The unique solution is as follows.

y(x) = c0 + c1x + c2(x:2) + c3(x:3) + … cn(x:n)

Let's try an example. Solve y′′′ = 8, where y(0) = 1, y′(0) = 2, and y′′(0) = 3. The solution is 8(x:3) + 3(x:2) + 2(x:1) + (x:0), which yields the following cubic polynomial.

y(x) = (8x3 - 15x2 + 19x + 6) / 6

Note that any linear combination of binomial coefficients can be rewritten as a traditional polynomial, and vice versa. The translation preserves the degree of the polynomial, and is one to one.

Setting the Difference equal to a Polynomial

Consider a difference equation that sets the nth difference equal to a polynomial p(x). Rewrite p(x) as a linear combination of binomial coefficients. These can be "integrated" term by term. We are basically replacing each (x:j) with (x:n+j). Bring in additional terms, below (x:n), for the initial conditions, if any. Finally, turn the expression back into a polynomial.

For example, solve y′′ = x2+x+1. Rewriting the polynomial yields 2(x:2)+2(x:1)+(x:0). Shift the "exponents" by 2, giving 2(x:4)+2(x:3)+(x:2). If the initial conditions are both zero, there are no terms below (x:2). Convert back to a polynomial and get this.

y(x) = (x4 - 2x3 + 5x2 - 4x) / 12