Discuss Method of Generating function for solving a non homogenous recurrence relation.

Generating functions are a useful tool in solving non-homogeneous recurrence relations. Here's a step-by-step guide on how to use them:

1. Define the Generating Function: The first step is to define the generating function. If you have a sequence {a_n}, the generating function G(x) is defined as G(x) = a_0 + a_1x + a_2x^2 + a_3*x^3 + ... . Essentially, each term of the sequence is multiplied by x raised to the power of its index, and these terms are all added together.

2. Write the Recurrence Relation in Terms of G(x): The next step is to write the recurrence relation in terms of G(x). This involves replacing each occurrence of a_n in the recurrence relation with the corresponding term in the generating function.

3. Solve for G(x): Once you have the recurrence relation in terms of G(x), you can solve for G(x). This will typically involve algebraic manipulation and possibly the use of calculus.

4. Find the Coefficients: Once you have G(x), you can find the coefficients a_n by expanding G(x) and matching the coefficients on both sides. This will give you the solution to the recurrence relation.

5. Solve the Non-Homogeneous Part: If the recurrence relation is non-homogeneous, there will be an additional function on the right-hand side. This function can be handled separately, and its generating function can be added to the generating function of the homogeneous part to get the final solution.

Remember, this is a general method and might need some adjustments depending on the specific recurrence relation you're dealing with.