Main

Differences

What is the derivative of a sequence? The original definition will not work because change in input is discrete and so one cannot take the limit as the change in input goes to 0. Instead, using the interpretation of the derivative as a rate of change leads to two different discrete derivatives. They are called difference operators, and are defined below.

Difference operators

The discrete analog of the derivative is the difference operator, defined as follows.

Difference operators

Given a sequence , the forward difference of , denoted , is defined by

The backward difference of , denoted by , is defined by

This can be interpreted as the change in output over the change in input:

which resembles the definition for the derivative of a continuous function, but without the limit. If we plot the points of the sequence as if we were graphing the function, and then connect the dots with linear segments, then the forward difference can also be interpreted as the slope between adjacent points:

Example

The sequence has forward difference sequence

Example

Find the forward difference sequence of the Fibonacci sequence .

The difference sequence is

Note that this is just the Fibonacci sequence again, but slightly shifted. This makes sense since the difference

by rearranging the Fibonacci recursion relation.

Example

Find the forward difference of the powers of two: .

The difference sequence is

This shows that can be thought of as the discrete analog of the exponential , in the sense that it is its own (discrete) derivative.

Product rules

These difference operators have their own versions of the differentiation rules for continuous functions. For example, there is a product rule. For sequences and , define the new sequence by . Then

This should be reminiscent of the product rule .

Higher order difference operators

Just as the derivative of a function gives another function, the difference operator of a sequence gives another sequence . Then one can take the difference operator of which gives yet another sequence . And so on. Consider, for instance, the sequence for . Then

A little bit of pattern matching shows the following:

Just as taking higher derivatives of a polynomial eventually gives 0, taking higher order difference operators of a polynomial eventually gives 0. Moreover, if is a polynomial of degree , then .

Note that the power rule is not quite the same as for regular derivatives (e.g. ). This is an artifact of the binomial expansion. The next section shows a convenient way to avoid these problems.

Falling powers

The falling power is defined to be

The falling power can be thought of as a discrete version of the monomial . One nice feature of the falling power is that

which is the familiar power rule.

Example

Express in terms of falling factorials and use the power rule above to find .

This requires a little bit of algebra. We know that we need a to get a . Note that

So we have our , but we also have some unwanted lower order terms. We must add to both sides to cancel the . Note that

and so

So to get rid of the final term of , we note that , and so we can add this to both sides to find

This tells us that

which matches the observation about in the above section.

Discrete

With the falling power in hand, consider the discretized version of the exponential function, found by replacing the usual monomials with in the Taylor series for the exponential:

If one evaluates this at to find the "discrete ", note that all the terms after the first two disappear because of the factor in all the higher terms. Thus, the discrete version of is 2. This is consistent with the earlier note that acted like the exponential function (it is its own discrete derivative). Indeed, the above series is , which can be seen by noting it is simply the binomial series evaluated at .

Sequence operators

Just as there were operators on functions (e.g. integration, differentiation, logarithm, exponentiation), there are operators on sequences:

OperatorNotationWhat it doesNotes
Identity
Left shift shifts twice, etc.
Right shift
Forward difference
Backward difference

Higher derivatives

The expressions for the forward and backward differences in terms of and can be used to compute the higher derivatives of sequences more easily than it would be to compute them by hand. For example, the third derivative can be found by expanding the expression as a binomial:

More generally, the th derivative can be written similarly:

Indefinite integral

As shown above, the forward difference can be expressed in terms of the operators and :

A logical question is to ask whether it is possible to take the anti-difference, just as there is the antiderivative for functions. The claim is that

This looks reminiscent of the geometric series. By taking the inverse of (and a few liberties with the algebra), we have

by thinking of as the reciprocal of in a sense (because acts like 1), and applying the geometric series. This derivation is not rigorous, but the above formula does give the anti-difference (up to an additive constant), so long as the sequence is eventually 0.

This is just a hint of the calculus of sequences, which we explore a little bit more in the modules to come.