RECURRENCE RELATIONS - DISCRETE MATHEMATICS

welcome back to discrete mathematics today we're going to take a look at recurrence relations so what is a recurrence relation a recurrence relation occurs when some number in a sequence depends on the previous numbers so a good example is the Fibonacci sequence so we start off with the number 0 + 1 and then the next number in the sequence is always going to be the previous two added together so 0 plus 1 is 1 1 plus 1 is 2 1 plus 2 is 3 2 plus 3 is 5 3 plus 5 is 8 so on and so forth so that's the counting sequence more formally we can define the nth number a n to be equal to the sum of the two previous numbers so we can say this is a n minus 1 plus n minus 2 commonly you'll see this with Fibonacci written FN is equal to FN minus 1 plus FN minus 2 I'm just going to use a s to be consistent with all of my examples so this is for N greater or equal to 2 because we don't want a of negative 2 because we can't have the negative tooth number in a sequence doesn't make any sense so we have a n is equal to a n minus 1 plus a and minus 2 the problem is right now is that n has to be greater than or equal to 2 so a 2 is equal to a 1 plus a 0 but I haven't defined what a 1 and a 0 are yet we need those two so we'll start off the sequence by saying that a 0 is equal to 0 and a 1 is equal to 1 and that is the formal definition of the Fibonacci sequence so let's take a look at another type of sequence a geometric progression ok so 3 2 6 12 24 48 okay this seems pretty straightforward let's write out a formal definition for this ok a n is equal to okay if we take some nth number some arbitrary number back let's take 48 how do we get 48 well we take the previous number a n minus 1 and then we multiply by 2 and of course this has to be for N greater equal to 1 because we need one previous number to figure out what the current number is and what is the first number in the sequence to start it off well that's the number 3 so this is the recurrence relation for this sequence now what's nice about this is that we can figure out a 5 8 8 a 12 let me figure out whatever we want the only problem is when I say hey what's a of 667 well that's going to be 2 times a of 666 but hold on a second once what's a of 666 well we just need to figure out that a of 666 is just 2 times a of 554 665 ok so if you know a of 665 then you can figure out a 666 and a 667 but that's kind of an absurd claim because that's a lot of unnecessary computation what we want is a way to solve this for a formula so let's solve a n is equal to okay well the first number we want is 3 so we want a of 0 to equal 3 so what's a good way of doing that well we could take our number 3 and okay we have 3 but this needs to be multiplied by something so a 1 is going to be 6 a 2 is going to be 12 so why don't we multiply it by 2 to the N okay so a 0 it's just 3 times 2 to the 0 is 1 ok that's good a to the 1 is equal to 3 times 2 to the 1 3 times 2 is 6 ok that looks good a of 2 is 3 times 2 to the 2 so 3 times 4 is equal to 12 ok that seems pretty good so here's how geometric progression solutions work and these are unique because these are fairly straightforward on ways to solve these relationships these are very nice if we have a relation a n is equal to D times a n minus 1 so D is just our constant and a 0 is equal to some number K then we can summarize this formula as a n is equal to K times D to the N and of course this is going to be for n greater or equal to 0 this section is going to be n greater or equal to 0 and this recurrence relation is going to be n greater or equal to 1 so these are two different ways of looking at things one is a recurrence relation the other is a nice formula that allows us to compute any number without needing to know the previous numbers so that's great but what can happen is we can get some more tricky examples so for instance this sequence 0 2 6 12 20 30 40 - I hope you can see the pattern just by looking at it to get from the first to the second we add 2 to get from the second to the third we get plus 4 and plus 6 then plus 8 plus 12 I start is 10 so on and so forth so another way of writing this and I know this technique is going to seem like I'm just pulling it out of my butt but it's hard to see and the fact that somebody else has shown me how to do this makes it a lot easier so what I expect you to just understand what I'm doing straight away or how I got to the solution no that's why you're watching a video so you can see someone else do it and hopefully you get some insight into future questions or future examples where you see something very similar ok so let's write this as a 1 minus a 0 so this is 2 minus 0 this is equal to 2 okay a 2 minus a 1 is 6 minus 2 which is 4 again what I'm going to do is just to make things super clear I'm going to write this as a 0 a 1 a 2 a 3 a 4 so on ok a 3 minus a 2 is 12 minus 6 which is 6 so we can see this pattern here so following this pattern we can see that a n minus a n minus 1 is going to be 2 times n ok so what we're going to do now is we're going to add all of these up so let's add up all of these formulas and what we're going to get is well ok easier a 1 minus a 0 let's add at the left side first a 1 minus a 0 plus a 2 minus a 1 we're going to get a 1 minus a 1 so these a ones are going to cancel then we're going to get a 2 plus a 3 minus a 2 ok so these a 2's are going to cancel and similarly the a 3s will cancel all the way up for the a n minus ones will cancel and we'll be left with an minus a 0 and this is going to be equal to 2 plus 4 plus 6 plus 8 all the way up to plus 2n which we can just factor out a 2 and then we get 1 plus 2 plus all the way up to plus n which we can write as 2 times the sum from I goes to 1 to N of I and if you remember this formula from a calculus course I don't expect you to to know the formula for any exam or test questions that I have on my website if I did I would give you the formula so whether you need to know this formula or not depends on your professor but this is the same thing as 2 times n times n plus 1 over 2 so this simplifies to n times n plus 1 so the recurrence relation solution is a n minus a 0 is equal to n times n plus 1 what is a 0 ok let's take a look here a 0 o 0 okay so a n is equal to n times n plus 1 so this is the solution so that might have been a little bit fast and it's going to be fast because well this is a unique way of looking at recurrence relations that you probably haven't seen before adding up a bunch of equations and summarizing so instead well first we should check to make sure it works let's pick a 6 so a 6 we know is equal to 42 that's this number here so a 6 is going to be 6 times 6 plus 1 which is 6 times 7 which is 42 so it works very cool ok here's a nice way of looking at things when we have any any recurrence relation that looks like a n minus a n minus 1 is equal to some number okay what we can do is say that well we should probably define a zero to be some number C and this is for N greater or equal to 1 if we ever have any relation of this form this is ok there we go this is equal to so a n is going to be equal to a 0 plus the sum as I goes from 1 to n of K so in our previous example we had a m- let's do this in a different color we have a n minus a n minus 1 is equal to 2 times n we had a 0 is equal to 0 for N greater than equal to 1 this a n is equal to a 0 which is 0 plus the sum as I goes from 1 to N of 2 to the N we can simplify this and say this is 2 times the sum of I equals 1 to N of n we just factor out the 2 and this is equal to 2 times n times n plus 1 all over 2 which we know cancels and we get n times n plus 1 so this is another little formula for recurrence relations that it's pretty important this I'm sorry there should be a little bit higher this requires a n minus a n minus 1 if you have a number here like 3 it does not work we will cover that next time but for now there's your solution that might have been tricky so I definitely suggest going over this very slowly in fact for those of you who are still saying where the hell did that some proof come from Oh e of I equals 1 to N of I is equal to n times n plus 1 over 2 you should know this why does this work ok here's a here's a proof of why this works let's do this impromptu proof we're going to take s this is going to be equal to 1 plus 2 Plus 3 plus 4 all the way up to n we're going to take the same sequence except we're going to take it backwards so this is n plus n minus 1 plus n minus 2 all the way up to plus one okay let's add these together let's add this whole sequence together so to s is equal to okay well 1 plus n is n plus 1 n minus 1 plus 2 is n plus 1 n minus 2 plus 3 is going to be n plus 1 so this is going to add up to the last number here which is n plus 1 which is n plus 1 again I'm just adding vertically here okay so how many numbers are there well there are n numbers so this is added n times so really two s is equal to n times n plus 1 so that means that s is equal to n times n plus 1 over 2 so this is equal to the sum of I equals 1 to N of I and that's n times n plus 1 over 2 there you go that is the proof of the sum for those of you wondering where that came from if you ever needed this I would provide it your profit might not so that was some very simple recurrence relations I say simple not because they should be easy to you because they shouldn't be if you're just seeing this for the first time but simple because the next videos are going to be much much harder so if you have any questions leave them in the comments below or leave them at the subreddit at reddit comm slash are slash Trev tutor or you can go to the website or email me directly if this helped you feel free to share with your friends because it will probably help them too unless there is a curve in the course in which case do not show them this information at all because your grade will probably suffer because they will do good as well unless you're a kind person so hopefully you are I'll see you guys next time for some homogeneous recurrence relations

Channel: TheTrevTutor

Views: 484,357

Rating: 4.8568888 out of 5

Keywords: recurrence relations, discrete math recurrence, recurrence relation in discrete mathematics, recurrence relation, recurrence relations discrete math, arithmetic recurrence relation, geometric recurrence relations, homogeneous recurrence relation, recurrence relations algorithms, generating function recurrence relation, TrevTutor, non-homogeneous recurrence relation, recurrence relations substitution method, geometric progression, mathematics, discrete mathematics functions

Id: eAaP4XaB8hM

Length: 15min 24sec (924 seconds)

Published: Tue May 05 2015