Generating Functions in Discrete Mathematics

---

---

Generating functions provide a way to transform sequence problems into functions. They allow efficient manipulation and discovery of patterns. In this chapter, we will see the basics of generating functions and understand how these functions work. In addition, we will cover the various types generating functions and also how they are applied to solve mathematical problems.

What is a Generating Function?

A generating function makes a sequence of numbers as coefficients of a power series. It does not focus on individual elements in a sequence. We create a single function that represents the entire sequence in its series form.

For example, if we have a sequence like 2, 3, 5, 8, 12, … we can create a generating function like that "displays" these terms as coefficients in the power series −

$$\mathrm{2 \:+\: 3x \:+\: 5x^2 \:+\: 8x^3 \:+\: 12x^4 \:+\: \dots}$$

Here, each coefficient corresponds to a term in the sequence. Now the representation can simplify complex problems. And it helps us to use calculus and algebraic techniques to manipulate and understand the sequence.

Infinite Power Series

In generating functions, we often work with infinite power series. Infinite power series is essentially an infinite sum of terms in the form c_nxⁿ, where each c_n is a constant −

$$\mathrm{\sum_{k=0}^{\infty}\: c_k x^k \:=\: c_0 \:+\: c_1 x \:+\: c_2 x^2 \:+\: c_3 x^3 \:+\: \dots}$$

Here, the sequence is generated by this series. It is simply the list of coefficients (c₀, c₁, c₂,…). This allows us to focus on the sequence as a whole. Rather than individual terms. This can be useful for analysis.

Working with Generating Functions

Let us understand how generating functions represent sequences. Let us consider a simple example.

Example 1: Finding a Sequence from a Generating Series

Suppose we have the generating series −

$$\mathrm{3 \:+\: 8x^2 \:+\: x^3 \:+\: 17x^5 \:+\: 100x^6 \:+\: \dots}$$

To find the sequence, we simply look at the coefficients of each power of x. The sequence is thus −

$$\mathrm{3,\: 0,\: 8,\: 1,\: 0,\: 17,\: 100,\: \dots}$$

Note that each coefficient corresponds directly to a term in the sequence. It is starting from x⁰, and any term without a corresponding power of x is zero.

Building Generating Functions

Let us see how to construct generating functions for specific types of sequences. This idea provides ways to generate various sequences and opens up strategies to handle them efficiently.

Geometric Series

One of the simplest sequences is the constant sequence 1, 1, 1, 1, Its generating series is −

$$\mathrm{1 \:+\: x \:+\: x^2 \:+\: x^3 \:+\: \dots}$$

This is a classic geometric series, which has a closed-form solution −

$$\mathrm{\frac{1}{1 \:-\: x}}$$

From this formula we get values of x within the interval |x| < 1. However, in generating functions, we do not worry about convergence because we will not plug in specific values for x. The generating function 1/(1 - x) generates the constant sequence 1,1,1,…

Using Multiplication

From the geometric series generating functions by adjusting the terms, we can generate other sequences. For instance, if we want the sequence 2, 2, 2, 2, we can simply multiply our function by 2 −

$$\mathrm{\frac{2}{1 \:-\: x} \:=\: 2 \:+\: 2x \:+\: 2x^2 \:+\: 2x^3 \:+\: \dots}$$

This generates the sequence 2, 2, 2, 2, . Now similarly, to get the sequence 3, 9, 27, 81, we can multiply the series by 3, then replace x with 3x −

$$\mathrm{\frac{3}{1 \:-\: 3x} \:=\: 3 \:+\: 9x \:+\: 27x^2 \:+\: 81x^3 \:+\: \dots}$$

Example of Constructing a Sequence with Constant Differences

Let us make a generating function for the sequence 1, 3, 5, 7, 9, where each term increases by 2. The generating function for a constant sequence is simple. We need to account for the increasing difference. We will call the generating function A −

$$\mathrm{A \:=\: 1 \:+\: 3x \:+\: 5x^2 \:+\: 7x^3 \:+\: 9x^4 \:+\: \dots}$$

To find a function for this, we can adjust our approach. Here noting that adding the generating functions for each individual increment builds the complete sequence.

Solving through techniques like differencing helps us to find −

$$\mathrm{A \:=\: \frac{1 \:+\: x}{(1 \:-\: x)^2}}$$

This approach helps in constructing generating functions for sequences with constant differences.

Advanced Techniques with Generating Functions

We have learnt the idea of generating functions. They can also be used to represent sequences that follow specific rules or recurrence relations.

Recurrence Relations

For a sequence defined by a recurrence relation, such as −

$$\mathrm{a_n \:=\: 3a_{n-1} \:-\: 2a_{n-2}}$$

we can use generating functions to handle these patterns more systematically. With the recurrence relations, multiplying and shifting terms will give provision to transform the sequence algebraically and identify a compact generating function.

Example of Generating Function for a Recurrence Relation

Let us consider the sequence 1, 3, 7, 15, 31, 63, which follows the recurrence relation −

$$\mathrm{a_n \:=\: 3a_{n-1} \:-\: 2a_{n-2}}$$

We can find the generating function A by organizing terms and solving −

$$\mathrm{A \:=\: \frac{1}{1 \:-\: 3x \:+\: 2x^2}}$$

This function a way to generate terms in the sequence without manually finding each based on the previous terms.

Differentiation

Differentiation is another interesting technique for generating specific sequences. For example, if we start with 1/(1 x), differentiating it term by term generates the series −

$$\mathrm{1 \:+\: 2x \:+\: 3x^2 \:+\: 4x^3 \:+\: \dots \:=\: \frac{1}{(1 \:-\: x)^2}}$$

This is the generating function for the sequence 1, 2, 3, 4, which represents the sequence of natural numbers.

Differentiating again gives us −

$$\mathrm{\frac{2}{(1 \:-\: x)^3} \:=\: 2 \:+\: 6x \:+\: 12x^2 \:+\: 20x^3 \:+\: \dots}$$

Which represents the triangular numbers sequence. It is showing how derivatives helps to get more complex sequences.

Example of Using Differentiation for Triangular Numbers

To create a generating function for triangular numbers 1, 3, 6, 10, we differentiate the generating function for the natural numbers, yielding −

$$\mathrm{\frac{1 \:+\: x}{(1 \:-\: x)^3}}$$

This gives successive differentiation can uncover structured numerical patterns. It extends the utility of generating functions.

Applications of Generating Functions

As we have understood the generating functions are quite useful. They have many such applications in combinatorics, probability, and other areas where we work with sequences. They are used to solve counting problems. To analyze the complex patterns, and work with recurrence relations more effectively we use generating functions.

For example, in combinatorics, generating functions simplify the counting of objects like subsets and arrangements. In probability theory they model distributions of discrete random variables and analyze series over discrete sample spaces.

Conclusion

In this chapter, we explained the concept of generating functions in discrete mathematics. We covered how generating functions transform sequences into power series.

We reviewed examples of constructing generating functions for simple and complex sequences. It can use techniques like multiplication, differencing, and differentiation. Lastly, we understood the practical applications of generating functions in combinatory and probability.