In the second example, how do you get that generating function for 3x^2+3x^3 as 3x^2/(1-x) ??? and why it is necessary to calculate Generating Function for that part ?? Hope, I'm not asking anything stupid.
If it was just those two terms (3x^2 + 3x^3) we would leave it like that. But we have infinitely many terms (a generating series: 3x^2 + 3x^3 + 3x^4 + ...) Luckily we realize this is very similar to the generating series 1 + x + x^2 + x^3 + ..., which is equal to 1/(1-x). To get our generating series we must multiply every term by 3x^2, so we have 3x^2/(1-x). Now that we have simplified the infinite part of the series, we can solve for A.
Mathematics Exemplified Okay Okay, it means while finding A, if we encounter a new generating series, we have to normalize that to get the actual A.. Thank You so much sir.
I had to to an assignment and coudn't understand anywhere how to do it. 5 minutes in this video I was able to get the generating functiong from my recurrence!
Great easy to understand video. But isn't sum_(i=2)^(infinity) 3x^i = -3x^2/1-x? How come you got it in positive? And do you basically ignore the constant term like 3 in the second example when calculating? And what is the resulting A actually outputting? How is it related to the recursive sequence?
+dongwoo1005 The infinite sum is positive 3x^2/(1-x). Note that if you ask Wolfram Alpha about this, they claim it is -3x^2/(x-1), but they have switched the denominator. I'm not really sure what you mean about ignoring the constant terms. The 3 in the second example is why we have all the 3's after subtracting. As for what the A is actually outputitng: it is not outputting anything. A generating function is not a function of x. That is, you do NOT plug in a value for x to get a value of the function. Rather, a generating function is a nice closed formula whose power series "displays" the terms of a sequence as the coefficients.
Sir I liked your video but one thing I didn't understand in genrating function video is that what if directly sequence is given to us for ex 1,6,216,.....then how to proceed?
But the formula does not work for other values of n. For example when x=1, the formula gives 2/5 which is not the same as 3. May be I am wrong but I am just confused.
A is a generating function, not a closed formula for the nth term of the sequence. You do not plug in values for x. Instead, we have found a function that is equal to an infinite power series whose coefficients are the terms in the sequence.
thanks for nice video. How do you start if you were not given recursive function but you were given only sequence. For example how do you do this sequence : 2,6,12,20,30,42,......?
You need to find a recurrence relation for the sequence. In that case, if you look at the difference between terms, you should notice a pattern. Better yet, if you know where the sequence comes from (i.e., what it models) then you can usually find the recurrence relation from that.
Oscar Levin thanks for reply. Given recurrence relation I can find the closed formula easily but the point is how do you create the recurrence relation given only sequence (without any initial value, no clue at all). Can you explain on those two specific sequences I gave A) 2,6,12,20,30,42,.... B) 1,0,-2,2,6,12,20,30,42,...
Using the recurrence relation. For the first example, you are given that a_0 = 1 and a_1 = 3, so there are your first two terms. Then you know that each term a_n = 2 a_{n-1} + 4 a_{n-2}. So to get the next term, you take 2*3 + 4*1 = 10. The term after that is 2*10 + 4*3 = 32. And so on.
in second example why you multiply both sides by 'x'...as in first example you multiply both sides of equation with 2.........Please explain this and tell me the general defination of generating function
In the first example you multiply both sides by 2x. You need to multiply by x or x^2 to "shift" the terms of the series over. A generating function for some sequence is just a function which has an infinite power series whose coefficients are the terms in the sequence. That is, in the infinite power series, the coefficient of x^n is the nth term of the sequence. Multiplying by 2x doubles each term, but also puts the coefficients onto the next power of x.
I'm sorry, could anyone help? I really don't get this. In first example, we have A=((1+x)/(1-2x-4x²)). If x=0, then A=1, that's correct, because a0=1. However, if x=1 then A=-2/5. Shouldn't it be 3?
Hi Puff R. Sorry for the tardy reply. It appears you are trying to get the terms of the sequence by plugging in values for x. That is not what a generating function does. I am not claiming that A is a closed formula for the x-th term of the sequence. A generating function is some function whose power series has the terms of the sequence as coefficients. The powers of x are mearly placeholders (which tell you where in the sequence you are. So if the power series has quadratic term 5x^2, that tells you that the a_2 term of the sequence is 5).
do you have examples of solving more complicated recurrence relations using this method? - I can't seem to find any other workbook solving RR's quite like you.
I don't right now. How much more complicated are you looking for? This method should be able to work whenever you have a "linear" recurrence relation. Do you have an example in mind?
Mathematics Exemplified Thanks for the quick response - i'm about to take a mid-term and only understand the methods you use so you'll be of great help. a(subscript)k = 3a(subscript)(k−1) + 4^k−1 with initial condition a0 = 1. Although I was even having trouble with a simpler one such as a(subscript)k = 3a(subscript)(k−1)+2 with initial condition a0=1
Mathematics Exemplified I guess my other question is also, in the first example you solved, how to you turn (1+x)/(1-2x-4x^2) into a closed form recurrence relation such as an = 3 *2^n or something like that?
royherma If you have terms in the recurrence relation like the 4^k or 2, then you should basically just leave those alone. That is, do the same thing you would do without those: subtract over all the a_[something] terms to one side. Now instead of having 0 on the right hand side, you will have 4^k-1 or 2. So when you do the differencing with the generating series, you will be left with the generating series for 4^k-1 or 2 on the bottom (after the subtraction). You should know generating functions for these which you can use the replace all of the infinitely many non-zero terms. As for going from a generating function to a closed formula for a_n, I know of one usefuly trick: partial fraction decomposition. Break up the generating function into parts that you can recognize as generating functions for 3*2^n or the like. Alternatively, if you just want a closed formula, you can often skip the generating function entirely. See: ruclips.net/video/pErXD1Q_HYI/видео.html and ruclips.net/video/lPCS2FFyqNA/видео.html for example. I don't have time to work out videos for these right now, so I'm afraid you are on your own. Best of luck with your mid-term.
alright so i guess just for the first part I would replace the constants or them 4^k-1 term with a generating function. I'm asking specifically about generating functions bc there will be a question that will ask to solve the RR using them and no other anyways, i hope it isn't a hard one - thanks.
I think your confusion is in the difference between a_(n-1) and n-1. The third term is a_2 which can be found by taking 2(3) + 4(1). The 3 is a_1 and the 1 is a_0.
hyun seul You shift over two places so that when you subtract you have like terms lined up. The 1/(1-x) is the generating function for 1 + x + x^2 + x^3 + ..., which in this case is multiplied by 3x^2.
I have exam tomorrow, my teacher explained in Russian and I didn't understand anything. Now I see the full picture, Thanks a lot.
My lecturer didn't explain this as clearly, now I actually got it. Thanks a bunch!
Kenneth Rosen's incompetence brought me here. But this is gold! Thanks for the upload.
Very clear, very helpful. Really appreciate you taking the time to create this video!
Thanks you Sir, love you from Viet Nam
It helped me on the night of the exam.. Thank you!
A BIG thanks for this. Still helping me in 2018!
Wonderfully explained! Thank you!!
YOU ARE A LIFE SAVIOR, I HATE DISCRÈTE MATHS, THANKS FROM U OF MONTREAL!!!
This has helped me out so much thank you so much.
In the second example, how do you get that generating function for 3x^2+3x^3 as 3x^2/(1-x) ??? and why it is necessary to calculate Generating Function for that part ??
Hope, I'm not asking anything stupid.
If it was just those two terms (3x^2 + 3x^3) we would leave it like that. But we have infinitely many terms (a generating series: 3x^2 + 3x^3 + 3x^4 + ...) Luckily we realize this is very similar to the generating series 1 + x + x^2 + x^3 + ..., which is equal to 1/(1-x). To get our generating series we must multiply every term by 3x^2, so we have 3x^2/(1-x). Now that we have simplified the infinite part of the series, we can solve for A.
Mathematics Exemplified Okay Okay, it means while finding A, if we encounter a new generating series, we have to normalize that to get the actual A..
Thank You so much sir.
This is good. This is really really good.
Saved me before endsems! Amazing content.
The explanation I needed
It helped me so much! Thank you!
You're a legend! This helped so much, thanks!
Thank you sir. You were of great help.
I had to to an assignment and coudn't understand anywhere how to do it. 5 minutes in this video I was able to get the generating functiong from my recurrence!
please guide how the values 1,3,10,32 are comes from?
That's Greart....I understand it for the first time only.
Thank you so much .that was very nice
Thank you very much, this was very helpful to me.
Thanks sir it helps me a lot.
I'm not sure what you mean. The only way to get 0 on the right hand side is if your sequence is constant 0. But then the generating function is 0.
Thanks a lot for this video!
That really helped me a lot! Thanks so much!:D
Best best best best best best best
Great easy to understand video. But isn't sum_(i=2)^(infinity) 3x^i = -3x^2/1-x? How come you got it in positive? And do you basically ignore the constant term like 3 in the second example when calculating? And what is the resulting A actually outputting? How is it related to the recursive sequence?
+dongwoo1005 The infinite sum is positive 3x^2/(1-x). Note that if you ask Wolfram Alpha about this, they claim it is -3x^2/(x-1), but they have switched the denominator. I'm not really sure what you mean about ignoring the constant terms. The 3 in the second example is why we have all the 3's after subtracting.
As for what the A is actually outputitng: it is not outputting anything. A generating function is not a function of x. That is, you do NOT plug in a value for x to get a value of the function. Rather, a generating function is a nice closed formula whose power series "displays" the terms of a sequence as the coefficients.
awesome step by step explanation....:)
it would had been better if you went in deep with more examples and explanation
Superb explanation thanks a loTT :D
how did u get 3x2 divided by 1-x in second example
So what are the a(n) formulas in terms of n after finding the generating functions?
Sir I liked your video but one thing I didn't understand in genrating function video is that what if directly sequence is given to us for ex 1,6,216,.....then how to proceed?
thanks for the video!
But the formula does not work for other values of n. For example when x=1, the formula gives 2/5 which is not the same as 3. May be I am wrong but I am just confused.
A is a generating function, not a closed formula for the nth term of the sequence. You do not plug in values for x. Instead, we have found a function that is equal to an infinite power series whose coefficients are the terms in the sequence.
Amazing!
Thank You
i'm confused but why would you multiply it with 2x over and over again? thx
Thank you
Hello, how would we use this process if the an term was not 1? thanks
thanks for nice video. How do you start if you were not given recursive function but you were given only sequence. For example how do you do this sequence : 2,6,12,20,30,42,......?
You need to find a recurrence relation for the sequence. In that case, if you look at the difference between terms, you should notice a pattern. Better yet, if you know where the sequence comes from (i.e., what it models) then you can usually find the recurrence relation from that.
Oscar Levin thanks for reply. Given recurrence relation I can find the closed formula easily but the point is how do you create the recurrence relation given only sequence (without any initial value, no clue at all). Can you explain on those two specific sequences I gave
A) 2,6,12,20,30,42,....
B) 1,0,-2,2,6,12,20,30,42,...
What if you have a_{n+1} instead of a_{n-1}?
how did u get d sequence 1,3,10,32, and in second example 2,2,9,16,37
Using the recurrence relation. For the first example, you are given that a_0 = 1 and a_1 = 3, so there are your first two terms. Then you know that each term a_n = 2 a_{n-1} + 4 a_{n-2}. So to get the next term, you take 2*3 + 4*1 = 10. The term after that is 2*10 + 4*3 = 32. And so on.
a0 = 1 and a1 = 3 so a2 = 10 and so on..
what if the constants are complex and their addition is different than 1?
in sequence order that u took 1,3,10,32... i have dout on hw should take sequence order from 10 will u plz explain tht
in second example why you multiply both sides by 'x'...as in first example you multiply both sides of equation with 2.........Please explain this and tell me the general defination of generating function
In the first example you multiply both sides by 2x. You need to multiply by x or x^2 to "shift" the terms of the series over. A generating function for some sequence is just a function which has an infinite power series whose coefficients are the terms in the sequence. That is, in the infinite power series, the coefficient of x^n is the nth term of the sequence. Multiplying by 2x doubles each term, but also puts the coefficients onto the next power of x.
hello sir, can you explain for more detail. how you get 3x^2/(1-x) in second example through generating function for 3x^2+3x^3?
+Alif fikri You need to know the generating function for 1 + x + x^2 + ..., which is 1/(1-x). Now notice we are just multiplying through by 3x^2.
I'm sorry, could anyone help? I really don't get this. In first example, we have A=((1+x)/(1-2x-4x²)). If x=0, then A=1, that's correct, because a0=1. However, if x=1 then A=-2/5. Shouldn't it be 3?
Hi Puff R. Sorry for the tardy reply. It appears you are trying to get the terms of the sequence by plugging in values for x. That is not what a generating function does. I am not claiming that A is a closed formula for the x-th term of the sequence. A generating function is some function whose power series has the terms of the sequence as coefficients. The powers of x are mearly placeholders (which tell you where in the sequence you are. So if the power series has quadratic term 5x^2, that tells you that the a_2 term of the sequence is 5).
do you have examples of solving more complicated recurrence relations using this method? - I can't seem to find any other workbook solving RR's quite like you.
I don't right now. How much more complicated are you looking for? This method should be able to work whenever you have a "linear" recurrence relation. Do you have an example in mind?
Mathematics Exemplified Thanks for the quick response - i'm about to take a mid-term and only understand the methods you use so you'll be of great help. a(subscript)k = 3a(subscript)(k−1) + 4^k−1 with initial condition a0 = 1. Although I was even having trouble with a simpler one such as a(subscript)k = 3a(subscript)(k−1)+2 with initial condition a0=1
Mathematics Exemplified I guess my other question is also, in the first example you solved, how to you turn (1+x)/(1-2x-4x^2) into a closed form recurrence relation such as an = 3 *2^n or something like that?
royherma
If you have terms in the recurrence relation like the 4^k or 2, then you should basically just leave those alone. That is, do the same thing you would do without those: subtract over all the a_[something] terms to one side. Now instead of having 0 on the right hand side, you will have 4^k-1 or 2. So when you do the differencing with the generating series, you will be left with the generating series for 4^k-1 or 2 on the bottom (after the subtraction). You should know generating functions for these which you can use the replace all of the infinitely many non-zero terms.
As for going from a generating function to a closed formula for a_n, I know of one usefuly trick: partial fraction decomposition. Break up the generating function into parts that you can recognize as generating functions for 3*2^n or the like. Alternatively, if you just want a closed formula, you can often skip the generating function entirely. See: ruclips.net/video/pErXD1Q_HYI/видео.html and ruclips.net/video/lPCS2FFyqNA/видео.html for example.
I don't have time to work out videos for these right now, so I'm afraid you are on your own. Best of luck with your mid-term.
alright so i guess just for the first part I would replace the constants or them 4^k-1 term with a generating function. I'm asking specifically about generating functions bc there will be a question that will ask to solve the RR using them and no other anyways, i hope it isn't a hard one - thanks.
how did u get 1,3,10,32
I am confused about third position "10" if an=3 then an=2(3-1)+4(3-2)=8, is anyone know how term 3 is equal 10? Please.
I think your confusion is in the difference between a_(n-1) and n-1. The third term is a_2 which can be found by taking 2(3) + 4(1). The 3 is a_1 and the 1 is a_0.
Oscar Levin OK got it, thank you.
Oscar Levin AT 8:58, why is it shifted to two places giving 3x^2? How did u get 1-x? Please explain further.
hyun seul You shift over two places so that when you subtract you have like terms lined up. The 1/(1-x) is the generating function for 1 + x + x^2 + x^3 + ..., which in this case is multiplied by 3x^2.
There is a black screen in your video, can't you see!
Your video is good but is scrambling in middle
I'm not seeing this. Can you give me a time code?
Christie: You multiply by 2x once! But to multiply an (infinite) polynomial by 2x, you must distribute to each term.