Supplement: Functional Equations and Recurrences

With rigor, and also practice a technique which is of prominent importance in calculus and your subsequent study. So pick up from where we were in the morning. And Catherine, we didn't cover this individually, but only because the example came at heart and it's a simple one. It's a Fibonacci sequence. So I'm going to quickly recapture the context. Elaine, I do not have your recording. I can't see you. So.We're going to go by the definition of the Fibonacci sequence. This is a recursive relationship, and I am going to give you a quick way, so that you could come up translated recursion into generating function relationship. So we, this is a second order. In order to get the whole board rolling, we need two initial terms. F zero is given as zero, F one is given as the one, and we're using our familiar container, which develop a generating function.The G of x now to carry the entire Fibonacci sequence in that going from zero to infinity. F k and x to the k power. Alright, the quickest way to do it is to multiply both sides of the equation. Actually, with the the x to the, you can do x k plus one or you can do x k, whichever term you want. Yeah, so I simply multiply the equality every single coefficient by x to the k power.Right, and at the moment, this is generically true for the k. And oh, sorry, I called at the n. I shouldn't be calling that k. Sorry, because I called a subscript n. Not so we're multiplying as to the n power. Please do interrupt me if there's anything that you don't understand. Okay, well, since generically every single term fits.Into that summation, then why don't we repeat the same equation to make the n going from zero all the way to infinity and just sum all of these up? What you have on the left is a sigma of the xn f of n plus one going from zero to infinity, would equal to sigma from zero to infinity f n x to the n power, and then plus sigma of the f of n minus one x to the n power going from zero to infinity.Correct. Okay, well, let's see. This is exactly the generating function g of the x. Now, what about this one? You can see if we want to force it into a generating function, I need to pull out the x, so that they would have matching coefficients. However, because the n goes from zero, there is that unknown of the f of ninety one, so we might as well just bring in all those, for example.Example that f of ninety one, f of ninety two, all of those just equal to zero. They fit into the member. Oh, no, they don't because if I pretend they do, then the recursive relationship fails at one now because one f one does not equal to the f zero plus f of ninety one. So we'd better really just do that. I with care now. If so, you know I can't make the n equal to zero because if I do so, this term becomes undefined. I have.To make the n equal to one, going from one to infinity. But if I do so, now both sides of the equation are safe in terms of a definition. And this it's exactly the x times the g of x, right? Because we do have the matching coefficient with the power and n goes from one to infinity, which means a minus one goes from zero to infinity. So this term fits to the t. We just have the g x times. The G of X. This one almost fits, but apparently the beginning index here starts with one. We miss out one single term. Fortunately, because X iPhone zero equal to zero, that's not necessary anymore. Because of the f zero equal to zero, I can just immediately lower that index back to zero because gratuitously the missing term is nothing, it's just zero. So.This is again exactly the g of x, correct. Alright, well, let's look at the other side of the equation. If we want to make it fit, then I need to lower this index, or we actually need to pull out one over the x to force the exponent to meet. So I have to rewrite it in this manner. But on the outside, I did this. That means that.But if we do so, we do see that the summation goes from one to infinity, which means the real index, which is n plus one, goes from two to infinity. That means we do have this, all right? But inside, we're missing the term because we started from the two. Now we have to manually add in. This is going to be the g of x minus the first term, which is the f one x. Now that term is not there. I need to.Try to buy it. Do you agree? Because of the boundary, the index of this term here starts with two. Give me a signal: if you do or if you don't agree.I agree. And helps you. Wait, why does it start from two? Ah, because well, the real boundary is one. Nevertheless, though you can see that index in terms of the subscript and the power, it's not the n, it's n plus one. So when the n goes from one to infinity, the real index goes from two to infinity. Oh, okay. Makes sense.Yeah. And the Catherine, are you good? Oh, when we multiply by one over x, why do we subtract x? Oh, this would match with the real left-hand side of the equation, which is now the x raised to the n plus first power, but instead x to the n power. But we force it into the n plus one. I need to get it back by dividing by x on the outside. Oh okay.But why do we force it into x to the n plus first power? Because we need to match with the subscript of the coefficient to make it equal to the Fibonacci generating function. We're good. Yeah, very good. Now this is a quick way for for us to get to the generating function equation. Now what we're getting, let's get rid of the denominator. We're gonna multiply by.Inside of the x now, and what you're getting is the one we put out to the g. Every term that has a g of the x now is pushed to the right-hand side, and we also multiply everything by the x now. So what you're getting one minus x minus x squared equal to the x now. We're getting the same conclusion, but hopefully this gives you the procedure that you could quickly get it. Instead of depending. On Indiania Smart Eyeballing. Are we good? Alright, now we're going to go through the standard procedure of doing partial fraction. There's no need to pull out the eggs. In the morning, I was simply prompting, waiting for the kids to take over, but apparently, and I think you guys, the morning class actually.Still remembered enough to push it forward, but there were so many missed details that was just making it unnecessarily hard. We know this can be immediately factored into the two partial fractions, right? So this g one second would simply equal to the two factor on the denominator. And let's solve this quadratic equation. We know the two roots are. Go ahead and and prove it yourself.``Ì got the same. Excellent. Well then, let's do our regular procedure of doing partial fraction. It would equal to the x minus one of the root, which is one half of the negative. Ah, let me just write it: the root five minus one. It's a positive number, and that's zero point six one eight. It's a smaller one between the two golden ratio. The other is x minus one half of.Of the negative five, a negative five minus one, meaning it's less. Then let's actually find the coefficient on the top. These are just a factor of the denominator, and you can see the original religious equal to less if you force it into those two factors.Let's find the coefficient. We know the procedure to find the first question mark. We're actually plugging in x equal to root five minus one into the rest of it, into this whole thing. And we're plugging in the x equal to the root five minus one over two, correct? To make the first denominator approach zero. So what are we getting?```loop When we plug it in, we have a root five and negative root five. Ah, then it like you actually have a left out the negative x on the numerator automatically. What you're doing is the one. When we do plug in on the denominator, we're getting root five, and we can keep it both actually share that denominator, but on the numerator, and Catherine, I agree with what you had. This is ah the one.One half of a the one minus root five, and the second one we're plugging in into this now into the first component. Now here we're plugging the x equal to the negative one half the root five plus one. Do it rigorously, and then you can double check your answer whether what I have.````````Ì got root five plus one over negative two times root five. Very good. We quite agree with each other. I'm getting exactly the same.I also got the same. Hmm. Excellent. I also got the same thing. Yeah, excellent. Ah, at this moment here, maybe we can use a little simple. We can really go by the convention now. The phi is a the Fibonacci number. Ah, sorry, the phi is a golden ratio that equal to it's positive five plus one over two, and there's another phi. This is a it's actually just one over the phi now. H e it's equal to the yeah it's equal to the small.Golden ratio, which is root five minus one over the two. It's a reciprocal of the big golden ratio number. And if we do so, then the g of the x now can be written as one over the root five. And what you're getting will be: this is a x minus the smaller golden ratio number, the sign on the top, it's a negative sign, and the minus the bigger golden ratio number five and x plus the five. That's just another way to write it. Otherwise, it's getting cumbersome if we keep copying those two pretty big numbers. I mean, troublesome numbers. Wow, just a bundle of numbers.If you do agree, give me some acknowledgement. I agree. Yeah, at this moment, it's very easy to do.The geometric sequence, a power expansion, and for convenience, we really want the denominator to begin with a one plus something. But that's just that's easy because we could first divide both top and bottom by that negative sign. So this is equal to, and I keep the one over the root five on the outside. The first one really becomes a one on the one minus that x over that side, right.This is the first fraction because I divided both the top and the bottom by the negative sign. But keep in mind now, the one over the sign is really just the five. So I can write in this manner: This is the first fraction, including the negative sign, including everything. Do you agree? Yeah.Alright, well, the second one the similar. We have actually divisible problem. Multiply by the five, and this becomes one plus x over the five, which is x times the smaller Fibonacci number. I keep saying the Fibonacci number. I mean the golden ratio number. At this moment, we're done. Go ahead and do the expansion of these two into the power.Function combine them, clean them up. I want you to come up with a generic formula of the um, please. Now we just need to power expand out the two and match the coefficient with the power. Turn to work, please.```中文嗯。 ```嗯，嗯。````````Ìs that X or is that multiplication? X. We're pulling out what is the coefficient now. Meaning, after we do the expansion, we're matching. We're looking for what is the coefficient of X to the nth power, which comes out of the two sources. I.Think you're on the right track, but my notation is really cleaning up that generating function returning to the generic formula of the f n.One plus x five plus x five squared, etc. It is. Then minus. Oh, it is exactly right. Catherine is actually doing the expansion. She's saying this expands out into one plus x five and plus the x squared, five squared, the da da da da da da. And the other component expands out into or minus one. Minus the x sine and plus x squared sine squared, it alternates because of the negative here, right? And then minus x cubed sine cubed, da da da da da. The point is, we need to combine the two, and then furthermore, we have the one over the root five, which fits into the generating function, which is the sigma of the f n x to the n power. So when you extract from this final expression, the g, what is going to be the f n now?What do we have?``Ànd there is a little inaccuracy here. Your general formula. How does that reflect the alternating bundle when we do the?Version```看来。Now your mental processes, especially emotions. Okay, that's very good. So, could we? You have indicated the several terms over here. Let's clean everything up, Elaine. I think you're totally on the right track, and let's have a final answer.中文嗯。嗯。我， got one over root five times. Sigma. Times um. Five.To the n power minus, uh, what is the other symbol called? Five. That's actually five, and the one is five. Um. Well, sigma one two n times, of of the phi to the n power, minus. Negative psi to the n power times x.And. Ah, so we're including and the alternating sequence in the negative side to the nth power. That's it. Who agrees? This is actually the generic formula for the Fibonacci. It's easy to check whether it's correct. We can just use it to find out whether it works for zero, one, two, three, etc. Etc. Because we know what the Fibonacci numbers are supposed to be. Who is getting this?I agree. Elaine, you notice here we need to include the ninety-one inside of this little sign. And Helms, are you getting the same? Yeah. Okay. Well, let's actually do a sanity check. Plug in the n equal to zero, n equal to one, n equal to two, n equal to three. We really want to get to the non-trivial part of this Fibonacci sequence. We do know there's supposed to be f of a zero. It's supposed to be zero. F one is supposed to be one. F of two is supposed to be one.iPhone three is supposed to be two. Let's check one more. Just because the Fibonacci sequence just getting man trivial. After that, iPhone four equal to a three, et cetera, et cetera. All right. Well, when we plug in zero, obviously it fits. So that checks out because anything to the zero's power is just one. When we plug in one now, we're having the five minus the negative five to the first power, which equal to the five plus the five.And then out there, we got actually divided by root five. This is actually the f one now. We're double checking whether it equal to one, right? By adding the two numbers, which is one half of the root five plus one, one half the root five minus one. Indeed, we get actually a total root five divided by root five equal to one. So that checks out. What about when you do squared? I'll tell you a trick. So on the numerator, you're getting actually the five squared on the minus. The little size squared under over u two, right? This is supposedly our f two now. If you don't want to square that nasty number, we can take advantage of the fact that these two are actually solutions to a quadratic equation. Only. And what is a quadratic equation? Remember the big five. In fact, these two. One second, where was the original?So the negative five and the little five are the very solution to the x squared plus x minus one equal to zero. Meaning the magnitude of the x squared now you can change it into that's what these two numbers fit. Okay, you can change it into one minus x, and we have worked out one minus x before, correct? So the five is the same as the this is equal to.The ninety-five squared. So, can I write it as the one minus phi? That's the replacement of the ninety-five squared. Oh, that's one minus the ninety-five. So that's one plus a five. The minus the other one is genuinely one minus the psi, because the psi itself is a root, which fits into this quadratic equation, and then divided by root five. And you can see this is.Returning to the F one now. When you simplify this, it happened to exactly equal the F one, which indeed also equal to one. Give me a signal if you fully follow, and also confirm what we're getting. For all of n zero to n.For. And well, at least I want you to follow. You confirm f two, and then later we could use the same trick because we really don't want to. By the time you're checking f three now, we we need to actually do the five q the minus c cube, right? Oh, that's plus now because it's on number over the root five. But if you want to avoid doing having to cube that, although it's not a big deal if you just cube.But I prefer just repeatedly use what we had earlier. If you know how, because we do know the two numbers negative five and psi they follow they both follow x squared equal to one minus x. This is how you could lower the power immediately. It's up to you. If you don't mind and raising that to the cubic, I don't mind either. You can do that.So, could we do in some manner? Take your favorite way to do an explicit check. Is the f three actually equal to two? We check all the previous ones now. Up to here, they all check out. Okay.``` ```中文嗯。If x squared equals one minus x, then the does x cubed equal to x minus x squared. Yes, absolutely. Catherine, you catch on the game very fast, then. So this is just a cheap way to lower the power, and we multiply this so that.It is indeed minus x squared, and you could further and then reuse this x squared. Now that's actually one minus x, right? So what you're getting is actually two x minus one. We're used to seeing the linear because we have figured out how they play out earlier. But keep in mind though, they do not work for the phi and psi. They work for negative phi and.So there's a little caveat that you have to watch out for. Then how do we do it? You force it into the sine cubed minus the negative sine cubed, and then you know both are roots now. And then we can do this translation. So in fact, the sine cubed is translated into twice of sine minus one, and the negative five is translated into twice of the negative sine, which is going to be the.Negative, two five, and then minus one. Do we agree? Yeah, and then over the root two, and we can see the constant term cancels out. You end up with twice of the side plus the five over the root two now, a root five, sorry, which is exactly a two because we circle back to this number which we have at worked out before that's one. So that's proven.Now, next one. I'm not going to say anything at all. Why don't you guys finish it? What about at four? Using the same pattern, I wanted to get to the level that you could sort of see through.``` ``Ànd after you finish, give me a signal.Well, to begin with, we could again scale this above. Now x to the fourth would actually equal to a two x squared minus x. But we figured out how to translate x squared. Right, x squared is replaced by one minus x now, so it actually becomes a two minus a three x. The whole point is, we drop everything down to linear because linear are easy.It will handle.I got three. Good, I get three as well. The two gets—I mean, this expression do two gets canceled out, were left with actually three times of the side plus of five.Well done, Catherine. And can I wait to get the confirmation or knowing the process from Helms and Elaine? Yeah, I also got it. Good. Me too. Very good. So this is actually the Fibonacci sequence. Now, if I summarize, we're not afraid of seeing the partial fraction, and the minute you have something which is a rational function, we know we're done because we know categorically how to expand out all.The rational function, as long as we could break it down into partial fractions, and each one is automatically a geometric series formula, which is a power function. So I'm really demonstrating how the generating function could be used to actually solve recurrences. We're good, huh? Yeah. Okay, very good indeed. Now I actually want to push you guys to see.Some kind of generating function, which is awfully hard if we don't do it with calculus. Nevertheless, I will give it a shot. I know this is it's really really hard, okay, but at least I want to get a few terms. First of all, are there any function that immediately when you look at it, you just know you cannot expand it out into a power function? Can you give me an example? There are infinite many, but I want to have intuitive feel for what kind of. Functionally, meaning I'm giving you a function that's well defined, it has got to be one of the seven early transcendents, basically the seven families we covered. Remember, they are power function, polynomial, rational function, trig, and inverse trig, exponential, and the log. Seven families now, so it just cannot be written as the sigma of the ak to the k power, going from zero to infinity. How.Could you come up with such a counter example. A log from a natural log. What a brilliant idea! What pushed you to think so? Why this cannot be? Because when we were doing calculus, when you could you could get one, ah, you ah, to find it, you'd have to evaluate different.Derivatives at zero, but there is no derivative at zero for the log function. Very good, very good. Yeah, and but with the people who haven't learned derivatives here, I would say your argument could be pressed down to one single boundary argument, which already works. That's sufficient already. Meaning it's not even defined at zero. If you could do that expansion, then obviously we know that a zero must equal to the f of zero, right? By plugging in the zero, we know if you're interested in a power.ExpansionExpansion, and then the quickest coefficient to be determined would be the constant term, because you just need to quickly plug in a special value that's going to immediately vanquish all the other powers and leaving us only at zero. So we know, for starters, if you actually want a power expansion, the function has to be well defined at zero. Otherwise, we can't even get started. This when we if we define f of x as natural logarithm. Now we know that f of zero, it's approaching.The infinity, right? It's undefined. Then surely we cannot have a power function. Do we agree? Okay, well, let's actually see now. What if I give you another function to guarantee it is well defined at zero? We do it as a shifted version. By the way, that's what we often do. So I'm going to come up with another function now. It's also an algorithm, but I'm defining it in this manner. Then do we have a well?We find the g of the zero. Surely we do, Catherine. What is the value of the g of zero? We're just plugging in x equal to zero, and go.Conceptually, what's the natural log of one? Zero, absolutely, it just equals zero. That's nice. That means that function goes through the origin. By the way, if you still remember the graph of the natural log, now the natural log I'm actually graphing it with a matching color, would be this. There's an asymptote and there's an interceptable one. This is a graph of natural.Log of x, right. There's no horizontal asymptote. It keeps increasing, except for it does bend down. It can't keep down. Then practice: what is its horizontal shift? What's the graph of natural log of the one plus x? If you're adding the one to the x, are you shifting the graph to the left or to the right by one unit? The left. Yes, very good. We're pressing it. We are shifting to the left because that means we need to. Plug in a smaller x, one smaller, to obtain the old function value, because you've got to add up one, add back on the one now. So instead of shifting the function, it's easier for me to shift the y axis. So in fact, let me actually say this is a new functional graph here, and that's the y axis, right? That's the graph of natural log of the one plus x. All right, we do know there's a well defined. We don't have the vertical asymptote at zero.Any more, instead we shifted to ninety one now. This function actually has a vertical asymptote at one at ninety one. Sorry. My question would be: Can we possibly do a power expansion? We haven't learned how to do it. It's unrelated to any binomial expansion or the exponential function. So how do we do it? Well, it is after all the inverse function of the exponential.So, can we just do one bit at a time now? We do know the G of the zero equals zero. Therefore, if I can write the sigma of the a k x to the kth, at least we already know one coefficient. We know that we start with a zero, and after that we do the a one x and we do the a two x squared. Da da da. I don't know what these numbers are, but I want to really push it forward as much as we can. So, is there any way to find the a one?Then don't use calculus. Okay, this is a we can't do it without calculus. So how do we look at a one now? We know it's just a first order infinitesimal. That means if I'm going to make the x approaching zero, then natural log of the one plus x now would be sort of just approximated by a a one x. This is how we find a one. What about these higher powers? They're negligible; they're all thrown out in the face of the lowest order infinitesimal.Because remember here, I'm not letting the x be anything arbitrary, but instead I make I'm making the x approach zero. Are you guys with me? Yes or no. Yes. Alright, how do we find a one? Mathematicians always resort to what you already know before, so we are good with the power expansion of an x.Exponential function, we are not really so prepared to handle the logarithm, but we could always translate the logarithm into exponential function counter way. So what do we do?嗯哼， Elaine， is thinking about this is an inverse function. This is the same as the y equals to the natural log of x. I agree. Except for right now, we have natural log of one plus x. If we want to get rid of natural log here, don't we just need to exponentiate both sides?If we put it on top of that exponent, now if we do this, then we'll be getting rid of that natural log, don't we? Yeah. Alright, go ahead and see what's going to happen. What would become the two sides of the equation. 中文嗯。嗯。请翻译成中文请以表格形式列出所有翻译内容。How do you like raise this two e. Good, and what come out. That is actually my point. What comes out then.``Àssistant perception markницRight, I think that's the link. And yes, but you suggested that we're gonna show exponential at both sides of the equation. And I wanna see what we're getting.I don't really know how. Oh, how to ex nihate a natural log here. Yeah, Catherine, knowing Elaine wrote it down for us. The meaning of a natural log. For example, if I. Actually, do the y equal to log of the x now, and I want to look at what is e raised to natural log of the x now. The meaning of the natural log of the x it means the exponent. If you put on the top of the e, would get you the x. So surely, this is get you the x. A different way, another take would be exponential function and natural log function are a pair of a function and the inverse. So when you're doing basically the exponential and follow.By its inverse, which is the natural log, the two functions cancel. You just end up back with the x. Doesn't make sense. Yeah. So the left hand side of the equation, really, Elaine, can you tell me what is the e raised to natural log of the one plus x, please. E to the one plus x. Huh. I'm talking about this. E to the natural log of the one plus.One plus x. Yes, it's simply one plus x. Helms, do you follow fully? And it is sorry, Catherine. Are you okay with that? Yeah. Okay, would equal to the other side, which is e to the a one x. Actually, if we didn't throw away all the higher power terms here, if we do say that's the entire.Very expansion. Now we not only have the a one x, we still have the a two x squared, and in fact, let me keep three terms. We can't keep infinite many, but we can at least keep a couple more, okay? And plus da da da, and here I'm going to actually bring in more terms. Let me clear the way. Of the a two of the x squared and then plus a three of the x cubed, da da da da da, makes sense, because x is approaching zero, so eventually you.Could only keep the lowest order infinitesimal. But at this moment here, I haven't done any approximation yet. I'm only saying rigorously: if this is a power expansion, if the power expansion is actually this now, then it's equivalent to saying it's saying one plus x just equal to that whole thing. Do you guys agree? Okay, but we know exactly how to expand the right hand side of the equation. I'm going to actually write it in purple now.I know this is quite a bundle, but if you're not, that expansion e to that huge thing, which is a power function of the gx now, wouldn't that just equal to one an plus that whole gx, which is a one x and plus a two x squared plus a three x cubed, da da da da da da da da, and then add on to whatever data is. I know it's quite a tedious bundle now, squared over the two factorial.And then continue. If you could at the G, then that side would be actually a lot lighter. But the next one would be the same and cubed over the three factorial. And you continue on at the infinitum. And all of these must add up to the one plus x, correct? Well, we just need to match all the coefficients. Well, to begin with, let's match what must be the linear term on that side.The linear term is a simple one. On this side, what is the coefficient of the linear term? On the right hand side, this infinite expansion. Let me actually tidy up, and we're gonna check the x to the first power. So it would equal to the one, which is the coefficient we're getting on the left, would equal to the coefficient on the right. What is it? A one. Simple term, just the A one. There's no other term. That's just A one. Makes sense. Yeah. And what about A two? How do we figure out A two? What term shall we compare? We can take the A two from the first parentheses, and for the second one, we can take two A ones because they multiply to get an x squared term. Brilliant.But what do they equal to, though? How do you compare with the x squared on the left-hand side? I mean, on the right-hand side of the equation, the coefficient over the x squared really is give me the a two n plus the a one squared over the two, and these are the only two contributions. Because the other parentheses like all start with a higher power. That's exactly right. But you know what do they add up to? What's the standard we compare with?Zero. Yes, very good, Catherine. You know this side, although it looks simple, but it contains all the information, all the higher components. The coefficients are zero. Go ahead and solve for a two. What is a two now? Yeah, because it won't have. Beautiful, you then you're seeing this confirms what you know from doing the derivative.I hope you still remember homework. I know it's a little tedious, but please figure out what is a three, what is a four for me, and that's it. I'm not asking for more now, and it's already complicated enough. Just carry the process. Would you? Okay, and now I promise we're really done with the power expansion. We've gone really far enough now. This is reading very deep waters, and the next session we're starting the new unit. Take care. Bye.Bye. Thank you.

Supplement: Functional Equations and Recurrences

Supplement: Functional Equations and Recurrences

Overview

Focus Areas

Lecture Video

Generated transcript