Ordinary Generating Functions and Recurrence Equations

1) Ordinary generating functions of a variable

Generating functions are an important tool for solving combinatorial problems of various types. A typical problem is the counting of the number of objects as a function of the size \(n \), which we can denote by \(a_{n} \). Thus, for each value of a non-negative integer \(n\) we have a sequence of values ​​\(\{a_{0}, a_{1}, \cdots a_{n}, \cdots \} \). We call generating function of the sequence \(a_{n} \) the following expansion of powers:

\[ G(x) = \sum\limits_{n=0}^{\infty} a_{n}x^{n}=a_{0}+a_{1}x + a_{2}x^{2} + \cdots \]

If there is an infinite number of terms it is a series of powers; in the finite case it is a polynomial. Two generating functions

\[ \begin{array}{l} F(x) = \sum\limits_{n = 0}^{\infty} a_{n} x^{n} \\ G(x) = \sum\limits_{n = 0}^{\infty} b_{n} x^{n} \\ \end{array} \]

are equivalent if \(a_{n} = b_{n} \) for each value of \(n \).
In the study of generating functions the aspects relative to the convergence of the series are generally overlooked. In this case the generating function is also called formal series. In this sense, the generating function is simply a way of representing the sequences of numbers, and the powers of \(x \) indicate the place associated with the various terms of the sequence.
Formal series are a useful tool to represent sequences of numbers even if they have many limitations. If you want to use the closed forms of the generating functions (for example the function \(\dfrac {1} {1-x} \) of the geometric series), then it is essential to study the convergence interval of the series.
Let us see with some examples how the generating functions can help in counting problems.

Example 1.1 – Newton’s binomial theorem
Suppose we want to calculate the number of subsets of \(k \) objects, taken from a set of \(n \) elements. It is known that the value is given by the binomial coefficient \(\displaystyle \binom{n} {k} \). So the generating function of these coefficients is Newton’s polynomial:

\[ G(x) = \sum_{k=0}^{n} \binom{n}{k}x^{k} = (1+x)^{n} \]

Example 1.2
Given the sequence \(\{1,1,1,1, \cdots \} \), the generating function is the geometric series:

\[ \begin{array}{l} G(x) =1+ x + x^{2}+ x^{3} + \cdots \\ = \sum\limits_{n=0}^{\infty}x^{n}= \dfrac{1}{1-x} \quad \quad |x| \lt 1 \end{array} \]

Exercise 1.1
Find the sequence-generating function \(\{1,2,4,8, \cdots \} \).

Exercise 1.2
Find the sequence generated by the following function:

\[ f(x) = \frac{1- \sqrt{1-4x}}{2} \]

Hint
Use the Maclaurin series expansions of the function.
The numbers of the sequence generated by the function are the Catalan numbers \(C_{n} = \frac {1}{n} \binom{2n-2}{n-1} \). For more details on Catalan numbers see the following link.

Exercise 1.3
Find the function that generates the sequence of Fibonacci numbers, which are defined as follows:

\[ F_{n}=F_{n-1} + F_{n-2} \quad \text{ if } n \gt 1 \]

with initial values ​​\(F_{0} = 0 \quad F_{1} = 1 \).

Hint
Combine the series \(G (x) \), \(xG (x) \) and \(x^{2}G (X) \) together. Thus, the generating function for the Fibonacci numbers can be expressed as:

\[ G(x)= \frac{x}{1-x-x^{2}} \]

---

2) Operations with generating functions

Sum and product of generating functions
Given two generating functions \(F (x) = \sum\limits_{n = 0}^{\infty} a_{n} x^{n} \) and \(G (x) = \sum\limits_{n = 0}^{\infty}b_{n} x^{n} \), the following sum and product operations are defined:

\[ \begin{array}{l} F(x) + G(x) = \sum\limits_{n=0}^{\infty}(a_{n}+b_{n})x^{n} \\ F(x)G(x) = \sum\limits_{n=0}^{\infty}c_{n}x^{n} \text{ where } c_{n}=\sum\limits_{k=0}^{n}a_{k}b_{n-k} \end{array} \]

The two-series product is also called Cauchy’s product, and the expression \(c_{n} \) plays an important role in counting indistinguishable objects.
Two generating functions \(F (x), G (x) \) are reciprocal if it results that \(F (x) G (x) = 1\). The inverse of \(F (x)\) exists if and only if \(a_ {0} \neq 0 \).

Example 2.1
The inverse generating function of \(F (x) = \sum\limits_{n = 0}^{\infty} x^{n}\) is the function \(G (x) = 1-x \) since

\[ (1-x)(1+x+ x^{2}+ \cdots)=1 \]

Change of scale
Multiplying a generating function by a constant is equivalent to scaling each term of the sequence by the same value.
For example, the generating function \(\dfrac{1}{1-x^{3}} \) generates the sequence \((1,0,0,1,0,0,1, \cdots) \). If we multiply by \(5 \), the new function \(\dfrac {5}{1-x^{3}} \) generates the sequence \((5,0,0,5,0,0, \cdots ) \).

Shift to the right of the succession
Let \(\{a_{0}, a_{1}, a_{2}, \cdots \} \) be a sequence and let \(G (x) = \sum\limits_{n = 0}^{ \infty} a_{n} x^{n} \) be its generating function. If we change the sequence by adding \(k \) zeros to the left \(\{0,0, \cdots, 0, a_{0}, a_{1}, a_{2}, \cdots \} \), then the new generating function is \(x^{k} G (x) = a_{0} x^{k} + a_{1} x^{k + 1} + \cdots \).

Example 2.2
The generating function of the sequence \(\{0,0,0,1,1,1, \cdots \}\) is the function \(G (x) = \dfrac {x^{3}} {1-x } \).

Derivative operation
Let \(\{a_{0}, a_{1}, a_{2}, \cdots \} \) be a sequence with the generating function \(G (x) = \sum\limits_{n = 0}^{\infty} a_{n} x^{n} \). The derivative of the function \(G (x) \) is the generating function of the sequence \(\{a_{1}, 2a_{2}, 3a_{3}, \cdots \} \).

Example 2.3
The derivative of the function \(\dfrac{1}{1-x} \) is the function \(\dfrac {1}{(1-x)^{2}} \), which generates the sequence of natural numbers \(\{1,2,3,4, \cdots \} \).

---

3) Computing the coefficients of a generating function

A fundamental problem is to determine the values ​​of a sequence for each \(n \), starting from the generating function expressed in closed form as a function of \(x \).

Exercise 3.1
Find the coefficient \(a_{n} \) of the following generating functions, expressed in closed form:

\[ \begin{array}{l} G(x) = (1+x)^{3000} \\ G(x) = \dfrac{1}{1-5x} \\ G(x) = 10 e^{x^{2}} \end{array} \]

Exercise 3.2
Find the coefficients \(a_{n}\) of the following generating function, expressed in closed form:

\[ G(x) = \frac{1}{(1-x)^{r}} \quad \text{ r integer} \ge 0 \]

Solution
Multiplying the \(r \) Taylor representations of the function \(\dfrac{1}{1-x}\), we see that the coefficient in front of \(x^{n}\) is the number of ways of writing \(n = p_{1} + p_{2} + \cdots + p_{r} \text { where } p_{i} \ge 0 \). This is equivalent to the problem of finding the number of combinations with repetitions of \(r \) objects taken in groups of \(n \). As is known, this value is

\[ a_{n} = \binom{n + r-1}{r-1} = \binom {n + r-1}{n} \]

Definition 3.1
Given a sequence of numbers \(a_{0}, a_{1}, \cdots \), we define the partial product of order \(n \): \(\prod_{i = 0}^{n} a_{i } = a_{0}a_{1} \cdots a_{n} \). Therefore we define the infinite product as the limit of the partial product (in analogy to the definition of the sum of an infinite series):

\[ \prod_{i=0}^{\infty}a_{i}= \lim_{n \to\infty}\prod_{i=0}^{n}a_{i} \]

The study of infinite products, like that of the series, is very important in Mathematical Analysis. For further information see, for example, Knopp’s beautiful book^[1].

Let \(p (n) \) be the arithmetic function that counts the number of partitions of the positive integer \(n \) in not necessarily distinct parts. Order is not taken into account. For example if \(n = 4 \), \(p (4) = 5 \). The partitions are as follows:

\[ 4=1+1+1+1=1+1+2=1+3=2+2 \]

Exercise 3.3
Determine the generating function of the function \(p (n) \), which represents the number of partitions of a positive integer \(n \) in parts that are not necessarily distinct.

Solution
Let’s analyze the following identity:

\[ \prod_{k=1}^{\infty} \frac{1} {(1-x^{k})}=\prod_{k=1}^{\infty}(1+x^{k}+x^{2k}+x^{3k}+ \cdots) \]

We observe first that, although there is an infinite product, to calculate of the coefficient \(a (n) \) of the power \(x^{n} \) it is necessary to analyze only a finite number of terms, precisely those that have a power less than or equal to \(n \).
In our case the coefficient of the power \(x ^ {n} \) is precisely the function \(p (n) \), as the term we choose in each factor \((1 + x^{k} + x^{2k} + x^{3k} + \cdots) \) determines how many times the number \(k \) appears in the partition. So we have:

\[ \prod_{n=1}^{\infty} \frac{1} {(1-x^{n})}=\sum_{n=0}^{\infty}p(n)x^{n} \]

Exercise 3.4
Determine the function generating the function \(p^{d} (n) \) which represents the number of partitions of a positive integer \(n \) in distinct parts.

Solution: \(\prod\limits_{n = 1} ^ {\infty} (1 + x^{n}) \)

Exercise 3.5
Prove the following identity:

\[ \prod\limits_{n=1}^{\infty} (1+x^{n})= \prod\limits_{n=1}^{\infty} \frac{1}{(1-x^{2n-1})} \]

Hint
Multiplying two factors at a time in the following infinite products, we obtain:

\begin{array}{l} (1-x)(1+x)(1+x^{2})(1+x^{4})(1+x^{8}) \cdots &=1 \\ (1-x^{3})(1+x^{3})(1+x^{6})(1+x^{12})(1+x^{24})\cdots &=1 \\ \end{array}

Continuing in this way we obtain the following final identity:

\[ \prod_{n=1}^{\infty} (1+x^{n}) \prod_{n=1}^{\infty} (1-x^{2n-1})=1 \]

Exercise 3.6
Prove the following relationship:

\[ \sum\limits_{k=0}^{n} \binom{n}{k}^{2}=\binom{2n}{n} \]

Hint
Note that \((1 + x)^{2n} = \sum\limits_{k = 0}^{2n} \binom{2n} {k} x^{k} \). Furthermore:

\[ (1+x)^{2n} =((1+x)^{n})^{2} =\left(\sum_{k=0}^{n}\binom{n}{k}x^{k}\right )^{2} \]

Then conclude by remembering that \(\binom{n}{k} = \binom{n}{n-k}\).

---

4) Polynomial generating functions

A very important class of generating functions is represented by polynomials obtained by multiplying polynomial factors with coefficients equal to \(1 \). For example the polynomial

\[ p(x) = (1 + x + x^{2})^{6} \]

The coefficient of \(x^{k} \) corresponds to the number of integer solutions of the equation \(a_{1} + a_{2} + a_{3} + a_{4} + a_{5} + a _{ 6} = k \), with \(0 \le a_{i} \le 2 \). The solution to this equation is equivalent to the problem of choosing \(k \) objects from a collection of \(6 \) types, with two objects for each type. Or it is equivalent to the problem of distributing \(k \) identical objects in \(6\) separate boxes, with a maximum of two objects per box.
Vice versa, given a combinatorial problem of choice with repetition of identical objects, we can determine the corresponding generating function.

Example 4.1
Let us consider 3 types of balls of different colors: red, black, green. Calculate, through the generating function, the number of possible ways to select \(6\) objects with repetition, with a maximum of \(4\) objects of each type.

Solution
In terms of diophantine equation, we have to find integer solutions of the equation \(a_{1} + a_{2} + a_{3} = 6, \quad 0 \le a_{i} \le 4 \). It is easily found that the solution is the coefficient of \(x^{6} \) of the generating function \(G (x) = (1 + x + x^{2} + x^{3} + x^{4 })^{3} \).

---

5) Recurrence equations

Many problems of combinatorial nature are reduced to finding the solution of a recurrence equation, with appropriate initial conditions. Basically, a recurrence equation breaks down a problem of order \(n \) into one or more similar problems of a lower order. Many recursive divide and conquer algorithms, such as merge-sort, have a temporal complexity that can be modeled with recurrence equations.
We limit our study to linear equations. For an in-depth study of recursive algorithms see ^{[2] or [3].}

Definition 5.1
A linear recurrence equation of degree \(k \) with constant coefficients is a relationship of the type

\[ y_{n+k} + c_{1}y_{n+k-1}+ c_{2}y_{n+k-2}+ \cdots +c_{k}y_{n} = f(n) \]

where the coefficients \(c_{i}\) are constant. It is said homogeneous if \(f (n) = 0\), otherwise it is said not homogeneous.

Example 5.1
The relationship \(y_{n} = n y_{n-1}\), with \(y_{1} = 1 \), defines the factorial function of \(n \).

A recurrence equation is also called a finite difference equation. There is a close analogy with ordinary linear differential equations. To solve a linear non-homogeneous recurrence equation, first we find the general solution of the homogeneous equation, then we add a particular solution of the non-homogeneous equation.

5.1) Solution of the homogeneous equation

To solve the homogeneous equation, we must first find the solutions of the characteristic equation.

Definition 5.2
The characteristic equation of the recurrence equation of degree \(k \) defined above is the following algebraic equation:

\[ r^{k} + c_{1}r^{k-1}+ \cdots + c_{k}=0 \]

In the case of ordinary linear differential equations the exponential functions \(e ^ {\lambda x} \) are taken as the basis for the roots. In recurrence equations we use the functions \(y_ {n} = r^{n} \). The algebraic solutions of the characteristic equation are called characteristic roots. Three cases need to be distinguished:

• all roots are real and distinct
• all real roots but not distinct
• some roots are complex numbers

In the first case the general solution of the homogeneous equation is the following:

\[ y_{n} = a_{1} r_{1}^{n}+ a_{2} r_{2}^{n}+ \cdots a_{k} r_{k}^{n} \]

where \(a_{1}, a_{2}, \cdots a_{k} \) are arbitrary constants.
In the second case, for example if a root is double \(r_{1} = r_{2} \), we have the solution \((a_{1} + a_{2} n) r_{1}^{n} \). We have similar formulas if the multiplicity of the root is greater than \(2\).
In the third case, for every complex solution \(\alpha + i \beta\) there is also the complex conjugate \(\alpha – i \beta \). So we can write the solution, for each complex root, like this: \( A (\alpha + i \beta)^{n} + B (\alpha – i\beta)^{n} \).
For a deeper study of the methods for solving finite difference equations see ^[4].

Exercise 5.1
Find the general solution of the recurrence equation:

\[ y_{n}-6y_{n-1}+9y_{n-2}=0 \]

Exercise 5.2
Find the general solution of the recurrence equation:

\[ y_{n} + 3y_{n-1} + 3y_{n-2} + y_{n-3}=0 \]

Answer: [\((A + Bn + Cn^{2}) (-1)^{n} \)]

Exercise 5.3
Find the solution of the recurrence equation:

\[ \begin{array}{l} y_{n} = 4y_{n-1} – 4y_{n-2} \\ y_{0}=2,y_{1}=5 \end{array} \]

Exercise 5.4
Find the solution of the following recurrence equation:

\[ \begin{array}{l} y_{n}=3y_{n-1} \quad n \gt 0 \quad y_{0}=2 \end{array} \]

Answer: [\(y_{n} = 2 \cdot 3^{n} \)]

5.2) Solution of the non-homogeneous equation

To solve the non-homogeneous equation, we just have to find a particular solution of the overall equation and add it to the general solution of the homogeneous equation. Particular solutions can generally be found through methods that vary depending on the format of the non-homogeneous term \(f (n) \).

Exercise 5.5
Solve the equation \(y_{n + 2} -4y_{n + 1} + 4y_{n} = n \).

Solution
The characteristic equation \(r^{2} -4r + 4 = 0 \) has a double solution \(r = 2 \). So the general solution of the homogeneous equation is \(y_{n} = a 2^{n} + bn 2^{n} \), where \(a, b \) are two arbitrary constants to be determined by means of two initial conditions.
To find a particular solution of the non-homogeneous equation, we must look at the form of the term to the right of the equation. In this case, we try with a polynomial of degree equal to the maximum degree of the term on the right. So let’s try with \(y_{n} = An + B \). Substituting this expression in the equation and equating the coefficients of the various powers of \(n \) we obtain the values ​​\(A = 1, B = 2 \). So the general solution of the non-homogeneous equation is the following:

\[ y_{n} =a2^{n} + bn2^{n} + n + 2 \]

Exercise 5.6
Solve the equation \(y_{n + 2} -4y_{n + 1} + 4y_{n} = n^{2} \).

In this case, find the particular solution of the non-homogeneous equation starting from the polynomial \(y_ {n} = An ^{2} + Bn + C \).

Solution: [\(y_{n} = a2^{n} + bn2^{n} + n^{2} + 4n + 8 \)]

Exercise 5.7 – Perrin’s equation
Solve the equation \(y_{n} = y_{n-2} + y_ {n-3} \) for \(n \ge 3 \), with the initial conditions \(a_{0} = 3, a_{1} = 0, a_{2} = 2 \).

Solution
We solve by the method of the generating function. Let \(G (x) = \sum\limits_{n = 0}^{\infty} a_{n} x^{n} \). We first calculate the expressions \(xG (x), x^{2} G (x), x^ {3} G (x) \). So with some calculations we get the following expression for the generating function:

\[ G(x) = \frac{x^{2}-3}{x^{3}+x^{2}-1} \]

The algebraic equation in the denominator has three roots, one real \(r_{1} \) and two complex conjugate \(r_{2}, r_{3} \). The inverse of the real root is also called plastic number, whose approximate value is 1.32471 (see link).
We now use the method of decomposition into partial fractions:

\[ G(x) = \frac{x^{2}-3}{x^{3}+x^{2}-1} = \frac{A}{x-r_{1}}+\frac{B}{x-r_{2}}+\frac{C}{x-r_{3}} \]

By carrying out the calculations we find the following values ​​for the three constants: \(A = -r_{1}, B = -r_{2},C = -r_{3} \). So putting together the series development of the three functions we obtain the following formula for the coefficient \(a (n) \) of the generating function:

\[ a(n)= \left(\frac{1}{r_{1}}\right)^{n}+ \left(\frac{1}{r_{2}}\right)^{n}+ \left(\frac {1}{r_{3}}\right)^{n} \]

---

6) The numbers of Fibonacci and Lucas

6.1) Fibonacci numbers

Fibonacci (1170-1235) numbers are non-negative integers defined by the following recurrence equation:

\[ \begin{array}{l} F_{0} = 0 \\ F_{1} = 1 \\ F_{n} = F_{n-1} + F_{n-2} \\ \end{array} \]

The first Fibonacci numbers are \(\{0,1,1,2,3,5,8,13, \cdots \} \).

Exercise 6.1
Prove the following relationships:

\[ \begin{array}{l} F_{1} + F_{3} + \cdots + F_{2n-1} &= F_{2n} \\ F_{2} + F_{4} + \cdots + F_{2n} &= F_{2n+1}-1 \\ \end{array} \]

First method for solving the recurrence equation
We solve the recurrence equation satisfied by Fibonacci numbers using the characteristic function. Let \(F_{k} = r ^{k} \). In this case, the characteristic equation and its solutions are the following:

\[ \begin{array}{l} r^{2} – r – 1 = 0 \\ r_{1} = \dfrac{1 + \sqrt{5}}{2} \\ r_{2} = \dfrac{1 – \sqrt{5}}{2} \\ \end{array} \]

The general solution of the homogeneous equation is therefore:

\[ F_{n} = A\left(\frac{1 + \sqrt{5}}{2}\right)^{n} + B \left(\frac{1 – \sqrt{5}}{2}\right)^{n} \]

We note that the general solution contains two arbitrary constants. Taking into account the initial conditions \(F_{0} = 0, F_{1} = 1 \), we finally have the solution that gives the formula for Fibonacci numbers:

\[ F_{n} = \frac{1}{\sqrt{5}} \left(\frac{1 + \sqrt{5}}{2}\right)^{n} – \frac{1}{\sqrt{5}}\left(\frac{1 – \sqrt{5}}{2}\right)^{n} \]

Second method of solving the recurrence equation
We solve the recurrence equation satisfied by the Fibonacci numbers with the method of generating functions, which has been found previously:

\[ \begin{array}{l} F(x) = \dfrac{x}{1-x-x^{2}} \end{array} \]

Theoretically we could develop this function with Taylor’s development at the point \(x = 0 \) and find the coefficients of the powers of \(x \), which are the Fibonacci numbers. However, this calculation would be too complicated; in this case, since the function is a ratio between two polynomials (a rational function) it is better to carry out the decomposition by means of the partial fraction method.
We observe first that \(x^{2} -x-1 = (1- r_{1} x) (1-r_{2} x) \), where \(r_{1}, r_{2} \) are the two roots previously found. Thus, the following decomposition can be written:

\[ \frac{x}{1-x-x^{2}} = \frac{A}{1 – r_{1}x} + \frac{B}{ 1 – r_{2} x} \]

Finding the least common multiple of the two fractions on the right, and equaling with the expression on the left, we find the following values ​​for the constants: \(A = \dfrac{1} {\sqrt {5}}, B = – \dfrac {1} {\sqrt {5}} \). Recalling now the geometric series expansion

\[ \frac{1}{1-x} = 1 + x + x^{2} + x^{3} + \cdots \]

and putting the results together, we obtain again the general expression for the coefficients \(F_ {n} \) already found before.

6.2) The golden ratio

Two quantities \(a, b \) are said to be in a golden ratio if the following proportion results:

\[ (a+b):a= a:b \]

If we denote \(x = \dfrac{a} {b}\) we have the equation \(x^{2} -x-1 = 0 \), whose roots are, as we have seen previously, \(r_{1 }, r_{2} \). The symbol \(\Phi \) is used to denote the value

\[ \Phi = \dfrac {1+ \sqrt {5}} {2} = 1.1618033 \cdots \]

which is an irrational number. In geometry, we say that a segment is divided into two parts according to the golden section if their ratio has value \(\Phi \).

Exercise 6.2
Prove the following formula:

\[ \lim_{n \to \infty} \frac{F_{n+1}}{F_{n}}= \Phi \]

Hint
Write \(\dfrac{F_{n + 1}} {F_{n}} = \dfrac{F_{n} + F_{n-1}} {F_{n}} \) and then compute the limit as \(n\) goes to infinity.

6.3) Lucas’s numbers

Lucas (1842-1891) numbers are defined similarly to Fibonacci numbers:

\[ L_{n}= L_{n-1} + L_{n-2} \quad (n \ge 2) \]

but with different initial conditions:

\[ L_{0}=2, L_{1}=1 \]

The first Lucas numbers are \(\ {2,1,3,4,7,11,18, \cdots } \). The recurrence equation is the same as the Fibonacci numbers, so the general solution is the same. However, the particular solution, obtained by imposing the two initial conditions, is obviously different:

\[ L_{n} = \left(\frac{1 + \sqrt{5}}{2}\right)^{n} + \left(\frac{1 – \sqrt{5}}{2}\right)^{n} \]

Exercise 6.3
Prove the following relationship: \(F_{2n} = L_{n}F_ {n} \).

---

Conclusion

As we have seen in this article, ordinary generating functions are a useful tool for solving many combinatorial problems with repetitions. In a future article we will describe exponential generating functions, which are useful for solving problems of distribution of distinct objects.

---

Bibliography

^[1]K. Knopp – Theory and Application of Infinite Series (Dover)

^[2]T. Cormen – Introduction to Algorithms (The Mit Press)

^[3]J. Edmonds – How to Think about Algorithms (Cambridge UP)

^[4]M. Spiegel – Finite Differences and Difference Equations (McGraw-Hill)