0:00
Welcome to Calculus, I'm professor Ghrist.
We're about to begin Lecture 46 on Differences.
>> We begin our construction of a discreet calculus
by building the notion of a derivative for a sequence.
This definition is going to turn out to be much simpler than that of a derivative for
smooth function.
But this simplicity hides a profound depth
that mirrors all the things we have learned in calculus thus far.
0:31
>> Recall that our goal is to build a discrete calculus,
a calculus based on sequences.
In this lesson, we'll consider what we mean by derivatives.
This will come in the form of differences or finite differences.
The definition is as follows.
Let's say, that you have a sequence a sub n.
We say, that the forward difference of a,
delta a at n = a sub n+1- a sub n.
That is, you look at the person in front of you, and
subtract off your present value.
1:14
Now, if we compare this to the definition of the derivative,
we see that there are some commonalities.
We are taking a difference in the output of the function
dividing by a difference in the input of the function.
In the case, where that difference is equal to 1,
because we're talking about a sequence.
Now, if we were to try to graph this function and give an interpretation
in terms of slope, then by connecting the dots, well, this would be
the slope of the line segment in front of you, hence the forward difference.
This motivates the definition of the backward difference.
If you look behind you, and consider the slope of at line,
we define the backward difference, nabla a at n
to be a sub n- a sub n- 1.
2:16
Let's consider a few examples.
If we take the sequence 4n and
compute it's forwards difference, what do we obtain?
I'm going to leave the verification of the computation to you.
I want you to show that one obtains the constant sequence 4.
Now, what do you observe here, it is if we are taking the derivative
of a linear function and obtaining the constant function,
but here these are sequences and differences instead of derivatives.
2:55
Here's another example a bit more interesting the Fibonacci sequence.
What happens when we take the forward difference of that 1 finds,
that again, 1 obtains the Fibonacci sequence, but
shifted over by one step.
With an additional 1 out in front, that seems like it must be significant.
For a last example, consider the sequence 2 to the n.
3:28
What happens when we compute the forward difference of that?
We obtain, again, 2 to the n.
It says, if this is something,
like the exponential function e to the x, which is its own derivative,
but here we're in the discrete world taking differences.
3:51
There are many parallels between differences and derivatives.
For example, if we ask the question, which sequences are polynomial?
Consider n squared, when we take its forward difference,
we obtain a sequence of odd numbers.
That is the sequence, 2n + 1.
What happens when we difference, again,
the second forward difference delta squared is in this case, a constant.
The constant sequence 2,
what happens when we take the next difference, the third forward difference?
Then we obtain the constant sequence 0.
This is very similar to what happens when we differentiate
a polynomial after a finite number of steps, we get 0.
In general, one can say that a sequence, a,
is a polynomial of degree p if the p plus first derivative,
that is difference of a is the constant 0.
Now, notice that there's something that's not quite
according to what you would expect here.
That is the difference of n squared is not 2n,
but rather, 2n + 1.
Now, that seems anomalous, but we can explain that with a bit more notation,
in particular, that of the falling powers.
These are discrete calculus versions of monomials.
We say, that n to the falling k is n times n-
1 times n- 2, all the way down to n- k + 1.
That works for a k bigger than 0.
For k = 0, we'll define n to the falling 0 to be 1, of course.
Now, the reason why this is so
useful is that the forward difference of n to
the falling k is k times n to the falling k- 1.
Let's look at this in the context of the example that we've done.
Consider the sequence n squared,
we could rewrite n squared as n(n- 1) + n),
that is, it's really n to the falling 2 plus n to the falling 1.
And hence, the forward difference of n squared is the forward difference of
n to the falling 2 + n to the falling 1.
Differencing, like differentiating is linear.
Hence, this is the difference of
n to the falling 2 + the difference of n to the falling 1.
That is 2n to the falling 1 + n to the falling 0.
Otherwise written as the sequence 2n+1, which is what we observed.
And that seems a bit complicated, why would you want to do that?
7:57
Consider the sum,
k goes from 0 to infinity of n to the falling k over k factorial.
Evaluated that n = 1.
What is that?
That's 1 + n + 1/2 n(n- 1) +
1/6 n(n- 1)(n- 2), etc.
What happens when we evaluate this if n = 1?
Most of the terms vanish.
All of the terms vanish, except the first two.
When we evaluate at n = 1, we get 1 + 1, which as you know is equal to 2.
Therefore, in discrete calculus e really takes on the value of 2.
And in fact, if we look at the version of e to the x,
that is the sum of n to the falling k over k factorial,
we get precisely the sequence 2 to the n.
And this is why, when we observed that the forward difference of 2 to the n is 2 to
the n, it reminded us of the behavior of e to the x.
9:15
At this point you may feel a bit like Alice in Wonderland.
What is with discrete e, and 2 to the n, and falling powers?
Discrete calculus can be a strange place, but
there is a more rigorous approach that you may find assuring.
This approach uses the perspective of operators.
These are things that transform functions into functions, or
in this case, transform sequences.
Some of these operators you've met before.
For example, the identity operator.
It acts on sequences the way you'd expect, it does nothing.
The identity applied to a, that is Ia, is the same sequence, a.
What's nice about operators is that we can work with them algebraically.
We can say that I squared, that is applying the identity twice,
is the same thing as applying the identity once, it does nothing.
10:17
E is the left shift operator, that is Ea is the sequence,
which in the nth slot, gives you a sub n+1.
And again, we can take powers of E to shift further to the left.
If there's a left shift, then there must be a right shift.
This has the notation E inverse, it undoes E.
10:48
Now, we can take powers of this operator as well,
and start multiplying them together.
They behave in the way that you would expect.
E inverse E, gives you E to the 0, that is the identity operator.
I, that works as well, if you reverse the order, it doesn't matter.
11:41
Here is an application to higher differences.
Let's say, you wanna compute the second forward difference of a at n.
This is the forward difference of the forward difference of a.
That is the forward difference of a sub n + 1- a sub n,
which with a little simplification gives
a sub n + 2- 2a sub n + 1 + a sub n.
What do you notice about those coefficients?
Well, if we rewrote the difference operators, E- I and
square that, then using the algebra of operators, and
simplifying according to what I does, we obtain E squared- 2E + I,
not simple.
In more generality, if we have the kth forward difference,
then by multiplying out E- I k times, we can obtain the formula.
The sum is i goes from 0 to k of negative 1 to the k- i
times the binomial coefficient k choose i, E to the i.
Now, this means what?
Let's say, that you wanted to compute a high difference.
Let's say, the eighth forward difference, that's gonna depend on a lot of terms.
What is the coefficient in front of the a sub n + 6 term?
Well, by writing down Pascal's triangle,
looking up the appropriate coefficient with the minus sign in the right place,
we easily see that, that coefficient is -56.
That is much simpler than trying to work it all out by hand.
13:45
Consider the discrete notion of an indefinite integral.
If the forward difference is E- I, then what
happens when we try to take the inverse, that is undo differencing.
Well, we need to take E- I to the negative 1 power.
Let's say, if I wrote that a little bit differently and
say put a minus sign out front, and we call it I- E.
Then it is as if we're trying to compute,
1 over I minus something.
Well, I've seen formulae for 1 over 1- x in terms of a geometric series.
What happens, if we tried applying the geometric series to this formula?
It would suggest that the inverse operator to forward differencing
is -(I + E + E squared + E cubed + E to the fourth, etc., etc.
Now, that seems rather dubious.
Let's check it on a simple example.
See what we get.
Let's take a random sequence.
Let's say, 3, -1, 4, -1, 5, -9, 2, -6, 5,
and I'm tired, so I'm just gonna write 0s from now on.
What would this delta inverse really mean, it means what?
Well, I need to at the nth term
take the sum of all the terms in a that follow, from n on up.
And then put a minus sign in front of it.
If we do so, walking down the line, we can marching from the right,
certainly compute the terms in this sequence.
This is easy, since our sequence terminated in 0s.
What happens when we take that, and forward difference it?
I'll leave it to you to check that we obtain the original sequence a,
that this actually does work.
Now, don't get too carried away.