Main

Discrete Calculus

The previous two modules have laid the groundwork for the discretization, or digitization, of calculus:

  1. The discrete version of a function is a sequence.
  2. The discrete version of the derivative is the difference operator.
  3. The discrete version of the integral is the sum.
  4. The discrete version of a differential equation is a recurrence relation.

This module mostly deals with #3, the integral of a discrete function. For continuous functions, there was the Fundamental Theorem of Integral Calculus which made computing integrals easy under certain conditions. Essentially, it said that the integral of the derivative is the function itself, evaluated at the endpoints. The discrete version says the same thing:

The Discrete Fundamental Theorem of Integral Calculus (FTIC)

Given a sequence ,

and

To see why this holds, evaluate the sum and carefully note the cancellation. This type of sum is called a telescoping sum. First, for the forward difference operator, one finds

as desired. Similarly, with the backwards difference operator, one finds

as claimed.

Example

Note that

Use this, along with FTIC, to find .

By FTIC,

Example

Use the fact that

along with the FTIC to find

By the fact above, we have

Example

Let denote the Fibonacci sequence defined by

Note that

by rearranging the above recursion relation. Use this, along with the FTIC, to find

By the above fact, we have

Power rule for falling powers

Recall from the previous module that the falling power

has a nice power rule for the difference:

By running this in reverse, we can find the anti-difference (or antiderivative) of the falling power, which is very similar to the power rule for integration:

where is a constant. Using this, along with the FTIC, allows one to find closed formulas for the sum of polynomials.

Example

Using the power rule and the FTIC, find

Note that , and so

Example

Find

Note that

Therefore,

Example

With a little algebra (shown in the previous module), one finds that

Use this fact, along with FTIC, to find

Using the above fact and FTIC, one finds

Now, note that when for all , because of the factor of . Therefore, the evaluation at the bottom limit is 0. Continuing with the algebra, we find

Recalling that , this shows the remarkable fact that

Integration by parts

There is also a discrete version of integration by parts. First, the following product rule can be established for the forward difference:

By subtracting and adding a common term and rearranging, one finds

Then, just like for continuous functions, one can integrate both sides (i.e. sum both sides), rearrange, and apply FTIC to find

Example

Find .

Let and . It follows that , , and . Thus, by the integration by parts formula,

Differential equations

The discrete version of a differential equation is a recurrence relation. This is an equation relating one term of a sequence with one or more previous terms in the sequence. In this context, the shift operator acts like the derivative.

Example

Consider the linear first-order recurrence relation

which can be written as

or, with some rearrangement,

By inspection, one can see the solution , where is some constant (it can be thought of as an initial condition).

Example

Now, consider using the following linear first-order difference equation

This is reminiscent of the differential equation , considered earlier in the course. Recall that , and so this difference relation can be written

With a little more rearranging one finds

which is almost identical to the equation from the previous example, but with replaced by . Therefore, the solution is .

Compare this to the solution in the continuous case, which was

When , we have the solution

If we let in the discrete difference equation, we have

which again shows that is the discrete version of the exponential function .

Fibonacci numbers revisited

We can take the recurrence relation for the Fibonacci numbers:

and rearrange it to be rewritten in terms of the shift operator:

Note that the solutions to the equation

are

So we can factor the operator to see that

It is a fact that solutions to this equation are combinations (that is, a sum) of solutions to

The solutions to these equations are

So we have that

for some constants and , which depend on the initial conditions of the sequence. To find those constants, we can plug in convenient values of and solve.

Letting , we have

Letting , we have

So we find

This gives an explicit, closed form equation for the Fibonacci numbers:


EXERCISES

  • (a) What is ? (b) Using part (a), find .