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. [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. 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 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. [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. [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. 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. [SOUND]. I hope you've enjoyed this foray of the world of discrete calculus. I hope you didn't find it too confusing. I hope it was a little bit inspiring, but if it was confusing don't worry. In our next lesson we're going to move on to some more concrete applications. [SOUND]