Generating Functions

Introduction

Generating function is a method to solve the recurrence relations.
Let us consider, the sequence a₀, a₁, a₂....ar of real numbers. For some interval of real numbers containing zero values at t is given, the function G(t) is defined by the series
G(t)= a_0, a₁t + a₂ t²+⋯+ a_r t_r+............equation (i)
This function G(t) is called the generating function of the sequence ar.
Now, for the constant sequence 1, 1, 1, 1.....the generating function is

It can be expressed as
G(t) =(1-t)^-1 = 1 + t + t² + t³ + t⁴ + ⋯[By binomial expansion]
Comparing, this with equation (i), we get
a₀ = 1, a₁ = 1, a₂ = 1 and so on.
For, the constant sequence 1,2,3,4,5,..the generating function is
G(t) =  because it can be expressed as
G(t) =(1-t)^-2 = 1 + 2t + 3t²  + 4t³ +⋯ +(r+1) t^r Comparing, this with equation (i), we get

a₀ = 1, a₁ = 2, a₂ = 3, a₃ = 4 and so on.
The generating function of Zr,(Z≠0 and Z is a constant)is given by
G(t) = 1+Zt + Z² t² + Z³ t3 +⋯+Z^r t^r
G(t) =  [Assume |Zt|<1]
So,  G(t) =   generates Z^r, Z ≠ 0
Also, If a⁽¹⁾r has the generating function G₁(t) and a⁽²⁾r has the generating function G₂(t), then λ₁ a⁽¹⁾r + λ₂ a⁽²⁾r has the generating function λ1 G1(t)+ λ2 G2(t). Here λ1 and λ2 are constants.

Application Areas

Generating functions can be used for the following purposes -

• For solving recurrence relations
• For proving some of the combinatorial identities
• For finding asymptotic formulae for terms of sequences

Example: Solve the recurrence relation a_{r + 2}-3a_r+1 + 2a_r = 0
By the method of generating functions with the initial conditions a₀ = 2 and a₁ = 3.

Let us assume that

Multiply equation (i) by t^r and summing from r = 0 to ∞, we have

Now, put a₀ = 2 and a₁ = 3 in equation (ii) and solving, we get

Put t = 1 on both sides of equation (iii) to find A. Hence
-1=- A       ∴ A = 1
Put t = 1/2  on both sides of equation (iii) to find B. Hence
1/2 = 1/2 B       ∴ B = 1
Thus G (t) =  . Hence, a_r = 1 + 2^r.