Recurrence Relations via Generating Functions | Discrete Math Tutorial

[00:00:02]welcome to all in the new lecture uh that is on the solution of recurence relation by the generating functions so here till now up to the lectures we discussed about the solution of the recurrence relation by iteration method characteristic root method now in this lecture we discuss about the solution of recurence relation using the Genting function and what is the genetic function uh we studied about it in the last lecture that what is the genetic function so here uh this is our the genetic function you know that g0 + g1x plus G2 x² G3 X3 so this type of Series this is are the uh in the Genting function we have the this type of series and in the another way we can say that in the summation form we can write summation of K isal to 0 to Infinity g k x to the^ K so uh this is the series that is the genetic function so here we have some genetic functions here it is a table in which we have the terms is given here in this uh table and these are the genetic function of these sequences actually this is the uh term suppose one so one one it means that the summation of one right it is only GK it is only that GK value that is one if it is one it means that all terms of the sequence is one and uh you know that the genetic function of the if we have the series is 1 1 1 1 so that genetic function is 1 upon 1 - x similarly this is only the GK means these all terms we take with with the summation so that Genting function is this so if we have the GK is k + 1 means that is summation K is equal to 0 to Infinity k + 1 x ra to the^ K it means that the genetic function is 1 upon 1 - x² similarly if we have the GK is K GK is K here so that generating function will be X upon 1 - x whole s and uh if our fun term is k k + 1 that Genting function will be 2x upon 1 - x cub and if we have the genetic terms are k + 1 k + 2 so that genetic function will be 2 upon 1 - x Cube if our genetic term is uh a ra to the power K so that is gentic function is 1 upon 1 - ax you know this so we use these uh terms these genetic functions of these terms in the solution of the recurrence relation clear so let's take some examples to solve the recurrence relation by the generating function here so if our example is that uh we take that genetic function a n + 2 - 3 n + 1 + 2 a n is equal to 0 and the initial conditions are given that a0 is equal to 2 and A1 is equal to 3 so now you have see that how can we solve this recurence relation by the Genting function so here first of all we have to multiply this recurrence relation this equation with X ra to the power n why we multiply this with X ra to the power n because we use here the Genting function to solve this Regence relation and our Genting function is the uh z0 like that Z 0 plus g1x G2x x² so we have the X ra to the power K terms right so here if we have X ra we have to multiply this equation by first X ra to the power n and sum sum it means that the summation from 0 to Infinity so this is a important thing and you have to understand this here we take that 0 to Infinity so how we take here the summation is 0 to Infinity because you can see here in this Regence relation we have the uh we have the order is less or uh term is a n right this is n + 2 n + 1 and N so Lessing term is a n so when we put here n is equal to 0 so we get the initial value and that is given the initial condition is a0 so we have to put here n is equal to 0 to Infinity uh we have the two types of reference relation we can write this right you know that in uh one is um in terms of plus and second one is in terms of minus means n minus 2 N minus1 and like that so whichever you have the Lesser term so here our subscript is less is n here so we have to the summation take from 0 to infinitive because our initial condition uh when we put n equal to Z so we get our the first initial condition initial that is a0 right so here we take the summation 0 to Infinity it's clear okay so let's take the next step so here we multiply this x ra to the power n the whole terms and the summation we take n is equal to 0 to Infinity so we have this type of expression now after that we expand these so when we expand this so put here n is equal to 0 1 2 like that up to Infinity similarly here so when we put here n equal to 0 so we get here A2 and X ra to the^ 0 so it become 1 second term is uh uh for the first term the second value is n put n equal to 1 so it become a3x when we put n = 2 so it become A4 x² and so on similarly in the second term we have minus 3 and when we put here n is equal to 0 so we get A1 plus a 2 x ra to the x + A3 x² and so on and the third term + 2 when you put here n is equal to 0 1 2 so it become a0 + A1 x + A2 x² and so on now uh we know that what is our genetic function our genetic function uh we can express our Genting function GX is a0 uh Plus in terms of a0 Plus A1 x + A2 x² is like that right so now we have to put in this term of G are the this series so we manipulate above equations in terms of the G so each term actually each term of this Regence term we have to express in terms of G in terms of Genting function so uh for this we take solve first term so that is a A2 + a3x + a 4x² so what we need here to make this is GX actually in GX you see that we have a0 so x x to the^ 0 when we take A1 so X ra to the power n when we take A2 so X ra to the power 2 with this and here we have A2 a3x so here uh what we need here here we need to multiply uh if we multiply here x² and here so become X Cub it become X4 so it means that we have to multiply by x² and if we multiply by x² so obviously we have to divide x² to maintain the equation right so now we multiply here x² and divided by x² so it becomes in terms of A2 X2 + a 3 X3 + A4 X4 now to make the GX we need here a0 + a1x terms right so we add these terms to make GX and when we add this so obviously we have to subtract is also minus a 0 minus a1x be uh to maintain the equation so now we add this a 0 + A1 X here and also subtract a0 plus a1x here so now what is this up to here a0 to This this term are become the GX so it is become GX and this is my - a 0 - A1 X upon x² so uh like that all terms all other terms you have to convert in terms of G so this are the uh recurence relation terms so now when we convert into the G so it become minus 3 and this is here what is have here here we need A1 X and here x² here x Cub so we have to multiply X and divide it by X here here and then it become the GX if we add a z here and subtract a z here so we add here so it become GX - a 0 upon X and this is already a GX so this become 2 GX is equal to 0 now put here the initial conditions which is given in the question a 0 is equal to 2 and A1 = to 3 when we put here so it become this so now we solve it and find the value of GX from here so when we solve it so we get the value of GX is 2 - 3x upon 2x² - 3x + 1 so this is our the GX right so uh if this is our the GX uh our Genting function so now after this we use the partial fraction decomposition you know that what is how to do the partial fraction decomposition uh if you have any confusion so you can see the uh before lectures that in which that is a particular lecture for the partial fraction decomposition so here we when we do the partial fraction of this term so it become 1 upon 1 - x + 1 upon 1 - 2x so you have to do this is yourself because uh you know that how to do the partial fraction in each and every question when we using the genetic function to solve the recurrence relation we need the partial fraction okay so it's it's necessary that you first understand how to do the partial fraction of any function so now after that this is are the partial fraction of the function Now using the table which table earlier I show you that the table here we have this terms so what this is the genetic function or you can say that the reversely if we have the genetic function is this so what will be the general term that will be this one so now here this is the genetic function right so and to make the particular genetic function what is GX GX is our the summation n equal to 0 to Infinity a and X ra to the power and this is term of uh form of GX so to become this form what we can write here this is 1 upon 1 - x so what is the Genting if our Genting function 1 upon 1 - x it means that our GK term is 1 it means that with the summation it becomes summation n = to 0 to Infinity 1 ra to the power n x ra to the power n in terms of Genting function you can write this because this is only GK now plus second term we have 1 upon 1 - 2x so this is the Genting function so what what is the Genting function if our Genting function is 1 upon 1 - 2x so what is the term here you can see here if we put here a isal to 2 so it become this means this is 2 ra to the ^ K so our function is summation n = to 0 to Infinity 2 ra to the power n x to the power n clear now uh to reducing the expression here means take out the summation both sides uh cancel out the summation so it become the terms only a n is equal 1 + 2 to the power n so this is the what is this this is the solution of our the given recurrence relation so like that you can find the solution of the given recurence relation by using the Genting function let's take another example here our recurrence relation is this un n is equal to un - 1 + 2 un minus 2 and initial conditions are given that U is equal to 3 and U1 is equal to 7 so same procedure we follow here here multiply the equation with X ra to the power n and sum sum here we take 2 to Infinity why we take here summation 2 to Infinity because here our subscript are n n minus1 n minus 2 so ler lesser subscript is n minus 2 so to make it uh uh our initial condition is initial condition is u0 right so make it zero we need that we put n is equal to 2 when we put is n equal to 2 so it we have we get the our in first initial condition u0 so we take the summation 2 to Infinity clear okay so now let's do the procedure here summation n is equal to 2 to Infinity u n x ra to the power n plus un n -1 x ra to the power n 2 unu N - 2 X to the power n now uh one uh another way to do this is here in this question you see that uh here we take that the exponent of x equal to the suffix of U inside the summation sign means here when uh in the last example actually we do that we have to uh to make the Genting function form we uh divide or multiply by X or x² or X Cube like that so here initially you can do this like that uh here if you because in the genetic function we have the same uh suff same um same power of X that is a suffix of u u or a also right so here you have U and xn it is uh same is here now you have to take the same power is here means X ra to the power nus1 should be here if you have un n minus one and xn minus 2 should be here if you have UN nus 2 so we take the similar here so it become when we want to see uh that here x - 1 it means that we have to multiply with X and sub divide it by X so it become X and it become X x n - 1 so to uh come here n minus 2 so we have to multiply by x² and x to the ^ minus 2 so it become x to the power nus 2 so directly from here you can do it now after when you expand it so it become n is equal to 2 here so U2 X2 + u3 X3 + u4 X4 and so on and this is X and this become when you put n is equal to 2 so it become u1x u2x X2 u3 X3 and so on and the last term 2x² it become u0 + u1x + U2 X2 and so on so now we know that our genetic function GX we can express it by u0 + u1x + U2 X2 so we solve first our the first term of the recurence relation so that is U2 X2 u3 X3 so how can we solve it you know that to solve it uh only we need that we have to add U Plus u1x here and also we can have to subtract U + u1x so now it becomes up to here to here this term is become GX and this is min - u0 - u1x now this was our the recurence relations so all terms when we put in terms of GX so it becomes this is GX - u - u1x and this is this is u1x u2x s so what we need here to make the GX we need that U not so you add here U not and subtract here U not so it become GX minus U with X and this is already a GX so this is 2x² GX now solve it and uh uh put here the initial conditions in U and U1 that is 3 and 7 so when we solve it and find the GX here so our GX is here become 3 + 2 4X upon 1 - x - 2 x² what we do after here after this we have to do the partial fraction of this and what will be the partial fraction of this expression so you know this so when you do the partial fraction first you have to factorize this quadratic equation and then to the partial fractions because these are the linear functions so it well you have to take only the constant so it become 10 upon 3 1 - 2x - 1 upon 3 1 + x so these are the uh partial fraction of this expression so this was our partial fraction now we have to take using the table also here again this was our table here 10 upon 3 this is a constant and 1 1 upon 1 - 2x so what will be the if our Genting function is 1 upon 1 - 2x so what will be the term here means in place of a you have two so it become 2 ra to the power K and if we have 1 upon 1 + x so uh 1 + x means our a is here minus1 so it become Min -1 to the^ K so it is 10 upon 3 2 to the power n x to the power n in terms of GX when you write in terms of summation and it is -1 ra to the^ n right you can write it now uh reducing the expression here only taking the terms so it is u n is equal to 10 upon 3 2 to the power n - 1 upon 3 - 1 ra to the power n so this is are the solution of the given recurrence relation clear how to solve the recurrence relation by using the generating function okay so let's take another example here we have the non homogeneous equation right because this is extra term here is 2 ra to the^ minus one so till now we solve the homogeneous recurrence relation now here we have the non homogeneous recurrence relation and initial condition is given that U is equal to 1 here we need only one initial condition why because we have only the n and n minus one so we have the only linear uh equation here now same procedure we have to follow here multiply the equation with X ra to the power n and here we take the summation 1 to Infinity why we take here 1 to Infinity because here our lesser subscript is n - 1 so we take here summation 1 to Infinity because our the initial condition is 0 is given so to make the initial value zero we have to put here n is equal to 1 so uh when we apply this this becom summation n u n xn un nus1 xn 2 to the ^ n minus1 xn now same thing is here we have to do to make the generating function we have to take the similar power and similar subscript of U so to make the xn minus one we have to multiply here with X and here to make the N minus one we have to also multiply with X here so it becomes 6X and this is X this one now expand when we expand it so it become when you put n equal to one here u1x + U2 X2 + u3 X3 and so on and here 6x and this become u0 plus U1 X Plus U2 X2 plus and so on and this is X1 + and when you put here n is equal to 1 so it become 2 to the^ 0 x to the^ 0 it become 1 plus next term is 2x 2 2 2 2 2 x² + 2 Cub X Cub like that clear now we know that our Genting function is U 0 + u1x + U2 X2 so when we solve the recurence relation means if we use the first term the our first term is U1 X U2 X2 u3 X3 so to become the genetic function we have to add here U so obviously the subtract u0 so it become GX minus u0 now this was our the expression so now when we use all terms in terms of the Genting function so it become GX this is are the GX minus U and this is 6X and this is is already a GX plus now what is this this is uh 1 + uh we write it 2 ra to the power K and X ra to the power K so it means that this is 1 upon 1 - 2 K according to the table right so this series generating function is X upon 1 - 2x it's clear okay so now uh put here the initial condition that is given U is equal to 1 so this is our the expression here after putting the initial condition now calculate here the GX when we solve it so our GX is become uh 1 - x upon 1 - 2x 1 - 6 x so now we have to do the partial fraction of this already we have the factors here so when we do the partial fraction so it become this is our the partial fraction of this 5 upon 4 1 - 6x - 1 upon 4 1 - 2x now we use the table here because these are the genetic function and we need the solution so to make the uh terms from the generating function we need the table and this was our table so if we have the 1 - 6X so what will be the term here means a is equal to 6 here so so it BEC 6 ra to the power K if we have 1 - 2x so it become 2 ra to the power K so in terms of genetic function we can write it our Genting function is U and X ra to the power n 5x 4 we can write it 6 ra to the power n and this is we can write 2 ra to the power n so when we reducing it so taking only the terms that that is unu n is equal 5x 4 6 ra to the^ N - 1 by 4 2 to the power n so this will be the solution of our given recurrence relation easy yes I think this is the so easy to solve the recurence relation by using the genetic function only one thing you have to remember if you remember this table so you can solve easily the genetic uh recurence relation by the Genting function mainly this uh term okay so I I hope all of you are understand how to solve the regen relations so now your this unit has completed today so thank you today's lecture is completed now be happy be healthy