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.

Â