Generating Functions for Recurrence Relations

Welcome to the final lesson of this module on Discrete Mathematics. In our last session, we developed a powerful algebraic method for solving linear recurrence relations using characteristic equations. While effective, that method is specialized. Today, we will explore an even more versatile tool: ordinary generating functions.

This lesson introduces generating functions as a unified framework to tackle two major types of problems crucial for the GATE exam: complex counting problems with constraints and solving recurrence relations. You will learn how to encode a sequence into a single function, manipulate that function algebraically, and then decode it to find the solution you need. This technique not only solves the same recurrences we saw before but also handles many that the characteristic equation method cannot.

By the end of this lesson, you will be able to formulate generating functions for combinatorial problems and use them to derive closed-form solutions for recurrence relations.

1. Generating Functions: The Accountant's Bookshelf

Imagine a sequence of numbers, $a_{0}, a_{1}, a_{2}, \dots$ , as an infinite collection of items. A generating function is like a formal "bookshelf" or polynomial where we store this sequence. The ordinary generating function for the sequence ${a_{n}}$ is defined as the formal power series:

F (x) = n = 0 \sum \infty a_{n} x^{n} = a_{0} + a_{1} x + a_{2} x^{2} + a_{3} x^{3} + \dots

Here, $a_{n}$ is the coefficient of $x^{n}$ . The variable $x$ is just a placeholder; we don't usually plug in a value for it. The magic lies in the coefficients.

Encoding Counting Problems

Generating functions provide a surprisingly elegant way to solve counting problems. The core idea is to represent the choices for each part of a problem as a separate polynomial. When we multiply these polynomials, the exponents add up, automatically exploring all combinations of choices. The coefficient of $x^{k}$ in the final product tells us exactly how many ways there are to achieve a total "value" of $k$ .

The following video introduces this fundamental concept.

GENERATING FUNCTIONS - Discrete Mathematics

This video from TrevTutor explains how to translate counting problems into the language of generating functions. It demonstrates how constraints on variables (e.g., upper/lower bounds, even/odd) correspond to specific terms in a polynomial.

Watch the first section of the video (to the end), which covers three examples: Solving an integer equation with bounds (like x1+x2+x3=12). Selecting jellybeans with different constraints on each color. Making change with different coin denominations. Focus on how each constraint is translated into a sum of powers of x. For instance, if a variable v can only take values from the set \{c_1, c_2, c_3\}, its corresponding polynomial is x^{c_1} + x^{c_2} + x^{c_3}.

2. The Generating Function Toolkit: Closed-Form Identities

Working with infinite polynomials is impractical. The real power of generating functions comes from our ability to represent these infinite series as simple, compact, closed-form expressions. Mastering a few key identities is essential for your GATE preparation.

The most important identity is for the geometric series, which represents the sequence $1, 1, 1, \dots$ .

GENERATING FUNCTIONS - Discrete Mathematics

The same video now derives the fundamental closed-form expressions that you will use constantly. It shows where the identity for 1/(1-x) comes from and lists several other crucial variations.

Please watch the segment from this point. Pay close attention to the table of identities presented. You should memorize these, as they are the building blocks for solving nearly all generating function problems.

Here is a summary of the most critical identities you must know:

Sequence $(a_{n})$	Generating Function $F (x) = \sum a_{n} x^{n}$	Description
$1, 1, 1, 1, \dots$	$\frac{1}{1 - x}$	All ones.
$1, c, c^{2}, c^{3}, \dots$	$\frac{1}{1 - c x}$	Geometric progression.
$1, - 1, 1, - 1, \dots$	$\frac{1}{1 + x}$	Alternating ones.
$1, 1, \dots, 1, 0, 0, \dots$ (k+1 ones)	$\frac{1 - x ^{k + 1}}{1 - x}$	Finite sequence of ones.
$1, 2, 3, 4, \dots$	$\frac{1}{( 1 - x ) ^{2}}$	Arithmetic progression.
$(k - 1 n + k - 1)$	$\frac{1}{( 1 - x ) ^{k}}$	Important for stars and bars problems.

With these tools, we can now simplify the complex polynomials from our counting problems. The video continues to demonstrate how to manipulate these expressions, for example, by factoring out $x^{k}$ to handle "at least" constraints (a shift).

GENERATING FUNCTIONS - Discrete Mathematics

The video now shows how to apply these identities to simplify and solve a full counting problem.

Watch the remainder of the video, from the end. It covers: Shifting: How multiplying by x^k affects the sequence (the shift). This corresponds to setting a minimum value. Worked Example: A complete problem (the example) where constraints are turned into polynomials, which are then converted to their closed forms.

3. Solving Recurrence Relations with Generating Functions

Now, we pivot to the second major application: solving recurrence relations. This method is more general than the characteristic equation approach and follows a clear three-step process.

The Three-Step Process:

Recurrence to Algebra: Convert the recurrence relation for $a_{n}$ into an algebraic equation involving its generating function, $F (x)$ .
Solve for F(x): Algebraically solve this equation to find a closed-form expression for $F (x)$ .
Algebra to Sequence: Decompose $F (x)$ into a sum of simpler functions from our "toolkit" and read off the coefficient of $x^{n}$ to find the explicit formula for $a_{n}$ .

Let's see this process in action.

RECURRENCE RELATIONS using GENERATING FUNCTIONS - DISCRETE MATHEMATICS

This video from TrevTutor walks through the entire process of solving a non-homogeneous recurrence relation using generating functions.

Watch the setup and the derivation of the algebraic equation for F(x). Introduction (to sums): The video sets up the problem a_n - 3a_{n-1} = n. Conversion to F(x) (to right side): This is the crucial part. Observe how the recurrence a_n - 3a_{n-1} = n is transformed. The key steps are: Multiply the entire recurrence by x^n. Sum both sides from n=1 to \infty. Rewrite each sum in terms of F(x) = \sum_{n=0}^\infty a_n x^n. For example: \sum_{n=1}^\infty a_n x^n = F(x) - a_0 \sum_{n=1}^\infty a_{n-1} x^n = x \sum_{n=1}^\infty a_{n-1} x^{n-1} = x \sum_{k=0}^\infty a_k x^k = xF(x)

Step 2 & 3: Solving for F(x) and Extracting the Coefficient

Once you have an equation like F(x) - a_0 - 3x F(x) = ..., you can algebraically solve for $F (x)$ . This typically results in a rational function (a ratio of two polynomials).

The final step is to break this rational function into a sum of simpler terms that match our known identities (like $1/ (1 - c x)$ or $1/ (1 - x)^{2}$ ). This is done using partial fraction decomposition, a technique from algebra. Once decomposed, we can simply read off the coefficient of $x^{n}$ for each part to construct our final solution for $a_{n}$ .

The video demonstrates this with a very involved example that requires a lot of algebra. The process is important, but don't get lost in the complex calculations of this specific problem.

RECURRENCE RELATIONS using GENERATING FUNCTIONS - DISCRETE MATHEMATICS

The video now solves for F(x) and uses partial fractions to find the closed-form for a_n.

Solving and Partial Fractions (to the solution): Watch how F(x) is isolated. The instructor then performs a lengthy partial fraction decomposition. Focus on the goal of this step: to break \frac{x^2 - x + 1}{(1-x)^2 (1-3x)} into the form \frac{A}{1-x} + \frac{B}{(1-x)^2} + \frac{C}{1-3x}. Extracting the Coefficient (to verification): This is the final payoff. See how the decomposed form allows the coefficient of x^n to be read directly from our toolkit, yielding the formula for a_n.

A Cleaner Example: Connecting the Methods

Let's walk through a cleaner example to solidify the process and connect it back to our previous lesson. Consider the recurrence $a_{n} = 5 a_{n - 1} - 6 a_{n - 2}$ for $n \geq 2$ , with $a_{0} = 0$ and $a_{1} = 1$ .

Recurrence to Algebra:
Multiply by $x^{n}$ and sum from $n = 2$ to $\infty$ :
$n = 2 \sum \infty a_{n} x^{n} = 5 n = 2 \sum \infty a_{n - 1} x^{n} - 6 n = 2 \sum \infty a_{n - 2} x^{n}$
Let $F (x) = \sum_{n = 0}^{\infty} a_{n} x^{n}$ . Let's express each term using $F (x)$ :
- Left side: $\sum_{n = 2}^{\infty} a_{n} x^{n} = F (x) - a_{1} x - a_{0} = F (x) - x$
- First term on right: $5 \sum_{n = 2}^{\infty} a_{n - 1} x^{n} = 5 x \sum_{n = 2}^{\infty} a_{n - 1} x^{n - 1} = 5 x (F (x) - a_{0}) = 5 x F (x)$
- Second term on right: $6 \sum_{n = 2}^{\infty} a_{n - 2} x^{n} = 6 x^{2} \sum_{n = 2}^{\infty} a_{n - 2} x^{n - 2} = 6 x^{2} F (x)$
  Our equation becomes: $F (x) - x = 5 x F (x) - 6 x^{2} F (x)$ .
Solve for F(x):
$F (x) (1 - 5 x + 6 x^{2}) = x ⟹ F (x) = \frac{x}{1 - 5 x + 6 x ^{2}}$
Notice the denominator: $1 - 5 x + 6 x^{2}$ . If you replace $x$ with $1/ r$ , you get $1 - 5/ r + 6/ r^{2} = 0$ , which simplifies to $r^{2} - 5 r + 6 = 0$ . This is exactly the characteristic equation from our last lesson! Generating functions rediscover it automatically.
Algebra to Sequence:
We use partial fractions on $F (x)$ :
$F (x) = \frac{x}{( 1 - 3 x ) ( 1 - 2 x )} = \frac{A}{1 - 3 x} + \frac{B}{1 - 2 x}$
Solving for $A$ and $B$ gives $A = 1$ and $B = - 1$ .
So, $F (x) = \frac{1}{1 - 3 x} - \frac{1}{1 - 2 x}$ .
Now we use our toolkit to find the coefficient of $x^{n}$ :
- The coefficient of $x^{n}$ in $\frac{1}{1 - 3 x}$ is $3^{n}$ .
- The coefficient of $x^{n}$ in $\frac{1}{1 - 2 x}$ is $2^{n}$ .
  Therefore, the coefficient of $x^{n}$ in $F (x)$ is $a_{n} = 3^{n} - 2^{n}$ . This is the closed-form solution.

Conclusion

In this lesson, you've learned about generating functions, a powerful and unifying concept in discrete mathematics. You now have a systematic method to approach a wide range of counting and recurrence problems that frequently appear in GATE.

Key Takeaways:

A generating function $F (x) = \sum a_{n} x^{n}$ encodes a sequence ${a_{n}}$ into a single algebraic object.
For counting problems, you translate constraints into polynomials and multiply them. The coefficient of $x^{k}$ gives the number of ways to get a total of $k$ .
For recurrence relations, you follow a three-step process: convert the recurrence into an equation for $F (x)$ , solve for $F (x)$ , and then expand $F (x)$ using partial fractions and standard identities to find the formula for $a_{n}$ .
Mastering the closed-form identities (especially for geometric series) is non-negotiable for success with this topic.

This concludes our module on Discrete Mathematics. We have built a solid foundation in logic, sets, graphs, and sequences. We will now transition to the next module, Engineering Mathematics, starting with a topic that is foundational to many areas of computer science: Matrices & Determinants. The skills of structured problem-solving and algebraic manipulation you've honed here will serve you well.

Recommended resources

1. Generating Functions: The Accountant's Bookshelf

Encoding Counting Problems

2. The Generating Function Toolkit: Closed-Form Identities

3. Solving Recurrence Relations with Generating Functions

Step 2 & 3: Solving for F(x) and Extracting the Coefficient

A Cleaner Example: Connecting the Methods

Conclusion