NON-HOMOGENEOUS RECURRENCE RELATIONS – Discrete Mathematics

welcome back to discrete mathematics last time we looked at homogeneous recurrence relations today we’re going to solve non homogeneous recurrence relations so previously we saw a relation like a n minus a n minus 1 is equal to K and we had a nice fancy formula for this so you’ve actually already seen a non homogeneous recurrence relation Y is non-homogeneous because our difference between terms is equal to something other than 0 so that makes it non homogeneous so before I said hey look if you have this n minus a n minus 1 and it has some sort of constant in front of it the solution doesn’t work and that is true so what happens when we have a situation like a n minus 2 n minus 1 is equal to 3 to the N if this were just 0 well we know what to do but it’s not it’s 3 to the N so let’s take a look at what we can do here well before we begin we should probably take a look at the general strategy so what we want here is when we have this long recurrence relation just formulas for saying coefficients plus terms to how many terms it goes to is equal to some function of n so for instance 3 to the N is a function of n then what we do is we split it up into two parts we get our homogeneous solution or homogeneous solution and then we add the particular solution so think of this sort of like a vector solution say you have a point that you’re going to over here so this is the general solution but then you want a particular solution so you shift it upwards and then you end up with the full solution so kind of like an X and a Y makes an X Y vector or something like that so kind of what we’re doing with homogeneous and non homogeneous Solutions we add the particular to the homogeneous solution so this is why it’s very important to know how to do the homogeneous recurrence relation because it’s expected in every problem of non og – or currents relations so what we do for the particular is we guess the form of the solution and then we’re going to substitute the form in to get the correct results this might seem unintuitive and challenging at first like how do we know what to guess but I have a nice little chart for you so if the function is just a constant our guess for the particular it’s just going to be some constant a and we’re just going to find that constant if it’s an N it’s going to be a constant times n plus a constant its M Squared be a constant times N squared plus another one times n plus another constant so these you can kind of see a pattern here if it’s R to the n then the solution to the particular is going to be some constant times R to the N so again we’re just sort of solving for coefficients once more there are other types for instance if there’s sine or cosine but those won’t be covered so we won’t look at those ok so possible forms might seem a little bit confusing because you don’t know what we’re doing it so here we go let’s do one a n plus 1 minus 2 a n is equal to 2 to the N so what do we do we say a n is equal to the solution to the homogeneous plus the particular solution so let’s find a n of H first okay so we have a n plus 1 minus 2 a n is equal to 0 so that’s what we’re solving here so the characteristic polynomial it’s going to be R minus 2 is equal to 0 so we have a root at 2 which means that a n H is going to be some constant alpha times 2 to the N okay this is where we stop for now so this might seem a little unintuitive but because the whole recurrence relation is the homogeneous plus the particular we can’t solve constants yet so we cannot solve this alpha yet so now what we do is we solve for the particular call a and P so this is the case where a n plus 1 minus 2 a n is equal to 2 to the n ok so our form here is some constant to the N which means

that our guess is going to be a times 2 to the N so we’re just going to substitute a 2 to the N into each of our positions here so because we have a n plus 1 we are going to substitute in a times 2 to the n plus 1 now here’s something you might be thinking and I’ve waited until now to show you but we have a solution that’s 2 to the N here and we have a solution that’s 2 to the n here and in our homogeneous solution we also have a 2 to the end and what happens if we have similar roots well we have to multiply by n for the second case because just like before if our guess is just 2 to the M and it just happens to be some constant times 2 to the N then we just get alpha plus the constant times 2 to the N is a solution which we know can’t be right so we have to multiply our guests by n for the same reasons we had to do with the homogenous solution so that means that this a down here is also going to be multiplied by n plus 1 yn plus 1 because we’re substituting it in the position of a n plus 1 so let’s do the substitution for -2 a to the N in white so now we’ll subtract 2 because we keep the constant and now we substitute in a times two to the N times n and this is just going to equal we’ll do this in green this is just going to equal 2 to the N so now we want to solve and simplify so we have a times n plus 1 times 2 to the n plus 1 minus well we can put this two times 2 to the end together so this will be 2 to the n plus 1 times a n is equal to 2 to the N so let’s divide everything by 2 to the N so that way we can reduce this right side to 1 okay so that means that to a n plus 1 minus 2 a n is equal to 1 and because we divide 2 to the N plus 1 divided by 2 to the N that just leaves 2 okay so now let’s expand to a n plus 2 times a minus 2 a n is equal to 1 so this means that 2 a is equal to 1 so a is equal to 1/2 so what we have here is that our particular solution is going to be 1/2 times 2 to the N times n so again we could simplify this and say this is just n times 2 to the N minus 1 because 2 to the N divided by 2 is just 2 to the N minus 1 okay so we have a particular solution here which is n times 2 to the N minus 1 and we have our homogenous solution alpha times 2 to the N so our total solution and of course we know is an H plus and P so this is going to be alpha times 2 to the n plus N times two to the N minus one so now we can finally solve for coefficients well what do we know we know that a zero is equal to one okay so let’s go down here and we’ll say that a zero is equal to one which is going to be alpha plus 0 so alpha is equal to 1 which means that a of n is going to be 2 to the n plus n times 2 to the n minus 1 which we can just factor out 2 to the n minus 1 times 2 plus n as our final solution and this will be for N greater or equal to 0 so we could test some numbers out if we want what do we know here so let’s get a

list of numbers going so a 1 minus 2 a 0 has to equal 2 to the 0 is 1 so that means that a 1 minus 2 is equal to 1 so a 1 has to be 3 ok so 8 so then that means that a 2 minus 6 has to be equal to 2 so a 2 has to be equal to 8 again I’m just plugging some numbers into the recurrence relation ok so a 1 is 3 a 2 is 8 so let’s just verify that a 2 works so we should have that a 2 is equal to 8 so a 2 is equal to 2 to the 1 times 2 plus 2 so this is going to be 2 times 4 which yes is equal to 8 so it works okay let’s do another practice problem just a little bit bigger so this is where you really have know your solutions to homogeneous recurrence relations and be able to do them pretty quick because if I said hey you have five minutes to this question could you do the whole thing in five minutes well you’re going to have to be able to do that so practice is very good so a n is equal to the homogeneous plus the particular so let’s do a n of H so we have a n plus two plus three a n plus 1 plus 2 a n is equal to zero so this is going to be R squared plus three R plus two is equal to zero and this is going to be R plus two times R plus one is equal to zero so our homogeneous equation is going to be of the form alpha times negative two to the n plus beta times negative 1 to the N because our roots are negative two and negative one okay now it is time to do our particular solution so this is the case where a n plus two plus three a n plus 1 plus 2 a n is equal to 3 to the M so we should guess the form well the form is still going to be a times 3 to the N because it’s some constant times 3 to the N we don’t need to multiply by M because how other solutions have been negative 2 and negative 1 so that’s good ok so let’s see what we can do here so we’re going to substitute a 3 to the N into each of these positions so a n plus 2 will become a times 3 to the n plus 2 this 3 a n plus 1 is going to become plus 3 times a times 3 to the n plus 1 and then this 2n is going to become 2 times a times 3 to the N and this whole thing is going to equal 3 to the N so let’s just divide everything by 3 to the N so then what we’re going to get is 3 squared times a let’s just make that 9 since 3 to the n plus 2 over 3 to the N is just 3 squared which is 9 3 to the N is going to be 3 times 3 so it’s going to be 9 a + 2 a 3 to the N divided by 3 to the N it’s just 2 a and that’s going to equal 1 so 20 a is going to equal 1 which means that our a is going to be equal to 1 over 20 so this means that our guess is going to have the solution 1 over 20 times 3 to the N ok so what this means is now we can solve for the whole relation so a n of H plus a n of P and n of H is alpha times negative 2 to the n plus beta times negative 1 to the end remember we figure that out earlier and then we’re going to add 1 xx times 3 to the N ok so now we can solve for some

coefficients so we want to solve for a 0 and a 1 a 0 was 0 and a 1 was 1 so 0 is going to be alpha plus beta plus K 3 to the 0 is 1 times 120 so that’s 1 xx 1 is going to be negative 2 alpha minus beta and here we have 3 to the 1 time one over 20 so this will be 3 twentieths okay so let’s take a look at this solution of equations or system of equations so this means that negative 1 xx is going to be equal to alpha plus beta and 17 xx is going to be negative 2 alpha minus beta so we can just add these two together to eliminate the betas so we’re going to get 16 xx is equal to negative alpha so you can say that alpha is going to be equal to 4/5 and ok so we got our alpha now we also know that 4/5 plus beta is equal to negative 1 over xx or negative 1 over 20 so let’s subtract 4/5 from that so that means that beta is going to be negative 1 over 20 minus 4/5 so this should be did I go wrong here hold on a second we add that’s negative alpha so alpha is equal to negative 4/5 that’s where I went wrong so negative 4/5 so we have to add 4/5 which means that beta is going to be 15 over 20 which is the same thing as saying that beta is equal to 3/4 so now we have our final solution of a n is going to equal negative 4/5 times negative 2 to the N sorry it should be negative 2 to the n plus 3/4 times negative 1 to the n plus 120 times 3 to the N so that’s going to be our total solution for N greater or equal to 0 so we could check some terms but it’s a lot of work so instead you can verify it yourself but this is how you solve non homogeneous recurrence relations so now that you know how to solve them let’s do a word problem where we take a word problem and just turn it into a recurrence relation because this is another interesting binary digit question well it’s a quaternary sequence so determine the number of n digit quaternary sequences in which there is never a three anywhere to the right of a zero so remember how we did this before we said okay we’re going to let a n equal all the sequences where it ends with a zero plus all the sequences where it ends with a 1 plus all the sequences ends with the two and all the sequences ending with a three okay so draw a nice little diagram we’ll do some positions and this is going to be the nth position so here we have the N minus 1 position and minus 2 and minus 3 of course this is 1 2 & 3 so if the last one is a zero what are our restrictions well there are no restrictions so the rest of these can be done in a and -1 ways since the N minus 1 can be ordered however they want what if the last ones a 1 okay well then there are no other restrictions so the rest can be ordered in a n minus 1 ways if the last one is a 2 we have the same situation no more restrictions but if the last one is a 3 we can’t have a 0 in any of these positions so that’s not okay that’s not okay that’s not okay we can never have a 0 in any of these so what does that mean well that means for

position 1 it can either be a 1 it can be a – or it can be a three so for position – it can be a one to two or three for position three it can be a one or two or three and four all of these positions it can only be either a one or two or a three so that means there’s three different numbers for number one three for number two three for number three so on so what is that well that is actually plus 3 to the n minus 1 so this recurrence relation is actually an is equal to three times a n minus 1 plus 3 to the n minus 1 so this is a non homogeneous recurrence relation and you could solve it if you wanted to because we just take a n minus 3 a and minus 1 is equal to 3 to the n minus 1 for all N greater or equal to 1 and what are the initial conditions for this well for a 0 we only need a 0 as an initial condition how many strings of length 0 are there hmm there’s one so how many strings of length 1 are there going to be well it could be 0 1 2 or 3 so there should be 4 let’s check to see if it works okay so a 1 minus 3 a 0 is going to be 3 to the 0 so a 1 minus 3 has to be equal to 1 so that means that a 1 is equal to 4 so both of our equations or our one equation gives us the intuitive result so we can assume that it’s going to hold for the rest but if you’re paranoid feel free to check more that was non homogeneous recurrence relations if you’d like some more practice you can go to trev tutor calm and you can check out midterm number two in the discrete math 2 section and that has more questions related to recurrence relations and generating functions in fact after the next video you will be able to completely solve it so if you have any questions feel free to leave them in the comments below or you can check out the website there’s more stuff there and we also have a subreddit at reddit.com slash are slash tribe tutor where you can post questions and I will answer there everything anyone has ever posted will also be there so it’s pretty good resource and it can be pretty much on anything in high school / very low level undergraduate mathematics so I will be there anyways if you enjoyed it share it to some friends because if this helps you this will help them see you guys next time