0:00

Welcome to Digital Calculus.

I'm your synthesized, digitized Professor Greist.

We're about to begin Lecture 47 on the Discrete Calculus.

[SOUND].

In our last two lessons, we have covered sequences

and a discrete form of differentiation that works on sequences.

In this lecture, we're going to go fully

digital and build a discrete calculus for sequences.

[SOUND].

The discrete calculus mirrors the

differential calculus in the following ways.

The discrete version of a function is a sequence.

The discrete version of a derivative is a difference.

The discrete version of an integral is a sum.

And the discrete version of a differential equation is a recurrence relation,

also called a recursion relation.

1:02

[SOUND].

Let's start with something big, something fundamental.

The Fundamental Theorem of Integral Calculus has a digital form.

It takes the form of the sum, as n goes from A to B

and the forward difference of a sequence U is equal to that

sequence U. Evaluated from N equals A to N equals

B plus one. Now what does that mean?

That means you evaluate the anti-derivative

that is the anti-difference at the end

points, but notice, that there's a, a little bit of a difference here.

We have to add a plus one to the upper limit.

That's in a case of a forward

difference, for backward difference, there is one subtracted

from the lower limit.

Now what's the proof of the Fundamental Theorem of discrete calculus.

Well, let's move this sum up, and expand out exactly what it means.

Remember, the forward difference says, we take the

next term in the sequence, minus the current term.

So if we add up all of the forward differences

as n goes from A to B. Then what do we see?

We see that most of the terms cancel,

because you have a plus, and then a minus of the same term.

The only things that do not cancel are the first term, negative

U sub A and the last term, plus U sub B plus 1.

And that is, indeed, as we have written it, the sequence evaluated at the limits.

Now, sometimes, these kinds of sums are called Telescoping Sums.

But if you ever see reference to that, now

you know you're really seeing the fundamental theorem in disguise.

[SOUND].

Here are a few examples of the fundamental theorem of discrete calculus in action.

Since the forward difference of the sequence 1 over n is equal to, by

definition 1 over n plus 1, minus 1 over n, which when

simplified is negative 1 over n squared plus n, then we can,

if you like, integrate both sides. To obtain, an explicit

formula for the sum as n goes from A to B of one over

n squared plus n. It is the anti-derivative, if you will.

Negative one over n evaluated from A to B plus one.

This can be written with a little bit of algebraic simplification.

As B minus A plus 1 over A times quantity B plus 1.

Here's another example.

Since the forward difference of the sequence n factorial

is, by definition, n plus one factorial minus n factorial.

Which after factoring out n factorial gives n factorial times n,

then we get an unusual looking formula. The sum, as n goes from A to B of n

factorial times n, is equal to n factorial, evaluated

from A to B plus one. That's simply B plus one factorial

minus A factorial, very, very simple.

[SOUND].

Now, since we know a few things about the

differences of falling powers, we can say some stronger things.

For example, the sum as n goes from one to k of n.

We've seen that sum before.

Here's a way to get it by means of integration.

This is really the sum of n to the falling one power.

What's the anti-difference

of that? Well, it's one half n to the falling two .

When we evaluate that from one to k plus one, we get k plus one times k over two.

Now, you've seen this formula before.

But I bet you've never seen this simple derivation.

5:28

Here's one that's less obvious, the sum as n goes from one to k of n squared,

we can rewrite n squared as n to the falling two plus n to the falling one.

We know how to anti-differentiate these following powers and

so we get one third n to the falling three.

Plus one half end of the following two evaluated from one to k plus one.

I'm going to let you do the algebra here to obtain the final answer

of k times k plus one times two k plus one over six.

[SOUND].

By reversing the product rule for forward differencing, it's possible

to obtain an integration by parts formula. Here's what it looks like.

The sum, as n goes from A to B of U, times the

forward difference of V is equal to U times V evaluated

from A to B plus one. Minus, the sum from A to B

of Ev, the forward shift of v times the difference, delta u.

I'm not going to go through a proof

6:42

of this.

We'll leave that to some homework problems.

Let's just do a simple example.

The sum, as n goes from zero to K of n times 2 to the n, is

equal to what? Well, let's let u be equal to n,

because I know what the forward difference in that is, that's simply one.

And, we're going to let

the v, and hence v, be the exponential

sequence, two to the n. Now,

in this case, what does the integration by parts formula tell us.

It tells us that this sum is equal to U times v, that is N times 2 to the

n, evaluated from zero to K plus one, minus the sum of

the forward shift of v.

That's 2 to the n plus 1, times the forward difference out of n.

Well that forward difference is simply one.

And so, we get when we evaluate that middle term, a plus one

times two to the k plus one minus zero. And then we have to subtract the sum.

From zero to

K of, two to the n plus one.

That sum is not so bad, we know how to do that.

We get, after a little bit of algebra, the final answer of

k minus 1 times 2 to the k plus 1, plus 2.

This is a highly non-obvious result, and a good example of

integration by parts.

8:27

[SOUND].

Let's turn to differential equations.

These are are recurrence relations, or sometimes recursion relations.

The shift operator E acts something like a derivative in discrete calculus.

Let's look at a linear first order recurrence relation.

This is something of the form, u sub n plus 2

equals lambda times u sub n, where lambda is a constant.

Now we can rewrite this using the language of operators.

As Eu equals

lamda times u, or moving the lamda u over to the other side and factoring out the u.

We have have the operator E minus lambda I applied to u equals 0.

Now, it's obvious what the solution to this recurrence relation is, u has

to be some constant times lambda to the n. Why is that?

Just look at the recursion relation, un plus 1, the next term, equals

lambda plus un the previous term. What is that constant big C?

Oh, of course, that is the initial condtion for the quote differential

equation. It is U not A constant.

So at each step you are simply multiplying by

lambda, that is the simplest differential equation in discrete calculus.

10:06

[SOUND].

Now if we change things just a little bit

and look at a linear first order difference equation.

This is something of the form delta u equals lambda u.

Now using what we know about operators, we can

say well delta is really E the shift minus I the identity.

And so what we're really saying is that E minus I applied

to u is lambda u. Can we solve this?

Moving things over to the other side, we see

that this difference relation, reduces to the recurrence relation.

E minus quantity lamda plus one is applied to u equals zero.

We already know the solution to this, it is

constant times quantity, lambda plus one

to the n. Now this is extremely significant.

If we compare this to the differential equation, x prime equals lambda x.

We know what the solution is.

It is the constant, the initial condition, C, times E to the lambda t.

Now, comapre what's happening here. This tells you why the exponential

sequence two to the n is really the discrete exponential function.

It is the solution to the difference equation delta u equals u.

In other words, it's the solution to

this difference relation when lambda equals one.

But notice,

according to our solution, it's lambda plus one to

the n and since one plus one equals two.

We see that two to the n is the

proper version of e to the x in discrete calculus.

[SOUND]

. Let's go back to the Fibonacci sequence.

This comes from something like a second order differential equation.

Really, a second order recurrence.

Recall, the Fibonacci sequence satisfies. F sub n plus two equals

F sub n plus one plus F sub n. If we move everything over to the left

hand side of the equation and write out using operators what do we get?

E squared minus E minus I applied to F,

equals zero. If we consider that as a

second-order polynomial and factor

this, just like E was a variable and I were a variable,

then what would we get? We would get E minus phi I.

Times E minus CI, applied to F equals zero,

where fee and C are those two constants related to the

golden ratio that we see whenever we find Fibonacci.

The solutions to this recurrence relation are built from

solutions to the individual first order pieces.

That is, E minus phi I applied to a sequence F1 equals 0.

Or E minus CI applied to a sequence F2 equals 0.

13:36

You don't quite know why this is true yet.

You'll learn that in multivariable calculus.

But lets just follow

the conclusion. Namely that the first type of solution is

of the form constant. C one time phi to the n, the second type

of solution is of the form, constant C2 times C to the n.

[SOUND].

The general solution as I have claimed, is really a combination

of these primal solutions, these peieces. The Fibonacci

sequence, F sub n, is of the form constant C1 times phi

to the n plus constant C2 times C to the n.

What are these constants? Well we know what

Fibonacci sequence is when n equals zero. The 0th term is of course 0

applying n equals 0 to our general solution gives C1 plus C2.

We know that the next term in the Fibonacci sequence F one equals one.

That is C one times phi plus C two times C.

This is a system with two equations and two unknowns.

We can solve that for C one and C two. C one is equal to one over root five.

C two is negative one over root five. Applying that to our general

solution for the Fibonacci sequence of Fs of N we get an exact answer.

Fs of N equals one over root five times phi to the n minus one

over root five times psi to the n. That's a pretty amazing result.

One that comes from a little bit of discrete calculus.

[SOUND].

Well, that's the end of our introduction to discrete calculus.

But that's by no means the end of this subject.

There's a lot more to it, but it's not usually covered by calculus class.