Mathematics | Generating Functions – Set 2

Prerequisite – Generating Functions-Introduction and Prerequisites
In Set 1 we came to know basics about Generating Functions. Now we will discuss more details on Generating Functions and its applications.

Exponential Generating Functions –
Let  h_0, h_1, h_2, ........., h_n, ...... e a sequence. Then its exponential generating function, denoted by  g^e(x) is given by,

 g^e(x) =sum_{n=0}^{+infty} frac{x^n}{n!} h_n

Example 1:- Let {1, 1, 1…….} be a sequence . The generating function of the sequence is
 g^e(x) = sum_{n=0}^{+infty} frac{x^n}{n!} ( Here  h_n =1 for all n )
Example 2:- Let  perm{n}{k} be number of k permutation in an n- element set. Then the exponential generating function for the sequence  ^nP_0, ^nP_1, ......., ^nP_n is

 g^e(x) =sum_{k=0}^{n} frac{x^n}{n!} ^nP_k                                                   = sum_{k=0}^{n} frac{x^k}{k!} frac{n!}{(n-k)!}                                                   =  sum_{k=0}^{n} frac{n!}{k!(n-k)!} x_k                                                   = sum_{k=0}^{n} ^nC_k x_k                                                   =(1+x)^n

Exponential Generating Function is used to determine number of n-permutation of a set containing repeatative elements. We will see examples later on.

Using Generating Functions to Solve Recurrence Relations –
Linear homogeneous recurrence relations can be solved using generating function .We will take an example here to illustrate .

Example :- Solve the linear homogeneous recurrence equation  h_n=5h_{n-1}+6h_{n-2} .
Given h_0=1 and h_1=-2.

We use generating function to solve this problem. Let g(x) be the generating function of the sequence  h_0, h_1, h_2, ......, h_n, .....
Hence g(x)=h_0+h_1 x + h_2 x^2 +........+ h_n x^n+....
So we get the following equations.
g(x)=h_0+h_1 x + h_2 x^2 +........+ h_n x^n+....

-5xg(x)= -h_0x+h_1 x^2 + h_2 x^3 +........+ h_n x^n+1+....

6x^2g(x)=h_0 x^2+h_1 x^3 + h_2 x^4 +........+ h_n x^n+2+....

Adding these 3 quantities we obtain
  (1+5-6x^2)g(x)=h_0 + (h_1-5h_0)x +(h_2-5h_1+6h_0)+....... +(h_n-5h_{n-1}+6h_{n-2})x^n+.....

Now h_n-5h_{n-1}+6h_{n-2}=0 for all n>1. So,

  (1+5x-6x^2)g(x)=h_0 + (h_1-5h_0)x = (1-7x)

Or g(x)=frac{(1-7x)}{(1+5-6x^2)}

Now (1+5x-6x^2)=(1-2x)(1-3x)

So, g(x)=frac{(1-7x)}{(1-2x)(1-3x)}

It is easy to see that frac{(1-7x)}{(1-2x)(1-3x)}=frac{5}{(1-2x)}-frac{4}{(1-3x)}

Now frac{1}{(1-2x)}=1 + 2x+2^2 x^2 +2^3 x^3+.... +2^n x^n+......
And frac{1}{(1-3x)}=1 + 3x+3^2 x^2 +3^3 x^3+.... +3^n x^n+......

So g(x)=5(1 + 2x+2^2 x^2 +2^3 x^3+.... +2^n x^n+......)-4(1 + 3x+3^2 x^2 +3^3 x^3+.... +3^n x^n+......)

Since this is the generating function for the sequence h_0, h_1, ......h_n We observe that h_n=5*2^n-4*3^n

Thus we can solve recurrence equations using generating functions.

Proving Identities via Generating Functions –
Various identities also can also be proved using generating functions.Here we illustrate one of them.

Example: Prove that : ^nC_r=^{(n-1)}C_r+^{(n-1)}C_{r-1}
Here we use the generating function of the sequence ^nC_0, ^nC_1, ......^nC_r.... i.e (1+x)^n.
Now, (1+x)^n=(1+x)^{n-1}(1+x)=(1+x)^{n-1}+x(1+x)^{n-1}
For LHS the term containingx^n is ^nC_r.For RHS the term containingx^n is ^{(n-1)}C_r+^{(n-1)}C_{r-1}. So ^nC_r=^{(n-1)}C_r+^{(n-1)}C_{r-1}(proved)

Links of Various examples are given below regarding generating functions.

  1. GATE CS 2018 | Question 18
  2. GATE-CS-2017 (Set 2) | Question 52

This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment



load comments

Subscribe to Our Newsletter