Using Generating Functions to solve Recurrence Relations
Find the general expression for c n , where
c n − 3 c n − 1 = 2 ⋅ 5 n .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
2 solutions
Discussions for this problem are now closed
I actually managed to do it brute-force way, but I see it's time for me to learn new ways of the force.
Indeed. I created this problem to illustrate the power of using generating functions to solve recurrence relations :) Click on the Skill (top right of solution discussions) to learn more!
You can also solve this "normally", using the characteristic equation and the specific solution approach.
what is A in this problem
There are a family of solutions to a recurrence relation with no initial conditions (boundary conditions). Replacing A by a specific constant, would give you a specific solution set.
Another name given for the Transform I heard. Could you teach me the concept of the transform or the method in shortest conceptual way?
In the top right corner, where it says skill, click on the skill name and you will be linked to the wiki directly :)
Consider the generating function
c ( x ) = c 0 + c 1 x + c 2 x 2 + …
Then, c ( x ) − 3 x c ( x ) = c 0 + 2 ⋅ 5 x + 2 ⋅ 5 2 x 2 + … = C + 1 − 5 x 2 .
Hence, c ( x ) = 1 − 3 x C + 1 − 5 x 2 = 1 − 3 x C − 3 + 1 − 5 x 5
Hence, the general expression for c n is
c n = A × 3 n + 5 n + 1 .