RECURRENCE RELATIONS using GENERATING FUNCTIONS - DISCRETE MATHEMATICS

Learn how to solve recurrence relations with generating functions.

*--Playlists--*

*--Recommended Textbooks--*

In this video we use generating functions to solve nonhomogeneous recurrence relations. This is a pretty long process that requires fairly good attention to detail. This video requires that you know generating functions fairly well.

Hello, welcome to TheTrevTutor. I'm here to help you learn your college courses in an easy, efficient manner. If you like what you see, feel free to subscribe and follow me for updates. If you have any questions, leave them below. I try to answer as many questions as possible. If something isn't quite clear or needs more explanation, I can easily make additional videos to satisfy your need for knowledge and understanding.

[rawshn]

Earned 10 marks in exam by watching this 30 minutes. Means a lot. Thank You Trev!

[kaiparakiwi]

The correct coefficients for the partial fractions are A = -1/4, B = -2/4 and C = 7/4

[hritiksharma]

Am from india and Am grateful to watch ur videos nd clear all my doubts... Keep making nd thank u so much...

[mukuls]

Dude, you really saved my ass in my assignment. You explained everything perfectly. Thanks.

[piyushtiwari]

thanks sir .. looking at the book I had assumed that I was not gonna complete this chapter by today .. but it helped a lot .

[savboo]

Thank you sooo much!! This is one of best generation function example problems I have came across.

[cbbuntz]

Well done video. I've always been confused by generating functions. They always look so simple.

I know how to solve similar problems of how to find the numerator and denominator terms to generate a known sequence. Just solve a matrix that's an identity matrix for the N numerator terms and toeplitz of the sequence for the denominator terms. You can solve the same problem with fft or z transform with a similar method too, but I've never figured out how to relate any of it to generating functions since there's sort of an added dimension

[guhannar]

Great series!! Loved the characteristic equation videos!

[TimBersama-cojp]

From a problem I encountered, I have derived quite a complicated generating function with 2 variables like this:

G(n, m) = (x^2y^2 + xy + 1)/(1 - x^3y^2 - x^2y - x)

I wanted to extract the formula for the coefficient, but since the denominator cannot be factorized, I am not sure if we can do partial fractions. Do you have any clue/hints or sources that I can learn from to solve this? or is it impossible?

Thanks in advance

[jaideepshekhar]

I think the point of the video is not to be rigidly accurate, but to show how to solve a problem.
So, please let it be.

[k]

Another way to solve the coefficients of the partial fractions is to let x equal 1/3 and 1 and then some arbitrary x to finally solve for A after solving for B and C. This avoids a matrix and u get them all faster.

[TcPwn]

4c=7 => c=7/4 not the other way around, and yea it is frustaring :\ keep up the good vids ;)

[utof]

20:44 shouldn't we also multiply by (-1)^n because we have a negative x?

[yenzyhebron]

Thanks ! It's hard but I'm getting the hang of it

[jahanvi]

Thank you so much, this was extremely helpful

[demenion]

for a_n-c*a_(n-1)=f(n), you could just modify the method of summation you explained some videos before. so a_n = c^n*(a_0+sum(k=1, n, f(k)/c^k)), if i didnt make a mistake in the indices

replacing c by n, you get n! instead of c^n and k! instead of c^k

[nguyentranconghuy]

you are my god, Trev! Thank you so much

[shoaibmohammed]

The correct coefficients are A=-1/4, B=-1/2 and C=7/4
The final answer for the last question I got was,
an = 1/2(1^n) + 1/2(3^n)
Could someone cross check?

[apurvsawant]

Thank you for making such wonderful videos and helping us

[johnchang]

Way faster: The equation is (x^2-x+1)/((1-x)^2(1-3x)) = A/(1-x) + B/(1-x)^2 + C/(1-3x). Multiply the equation by (1-x)^2, then evaluate at x=1 to get B=-1/2. Similarly, multiply by 1-3x and evaluate at x=1/3 to get C=7/4. To get A, set x=0. Doing this would take off about a quarter of the video, 7 of the 8 minutes you spend on the method of undetermined coefficients and the subsequent (incorrect) matrix arithmetic.
After you do this a few times, you'll realize you can just ignore the factor that is zero and evaluate the rest of the function to get the coefficient. This is the definition of the residue.