Given an infinite sequence of numbers $<a_0, a_1, a_2, a_3, . . .>$, the (ordinary) generating function for the sequence is defined to be the power series:

$A(x) = \sum_{i=0}^{\infty}a_ix^i =  a_0 + a_1x + a_2x^2 + a_3x^3 + . . . $ 

 

Consider the binomial expansion of $(1-x)^n$, where $n\in \mathbb{Z}^+$

$(1-x)^n = \sum_{i=0}^{n}\binom{n}{i}(-x)^i$

$\quad = 1 - nx + \frac{n(n-1)}{2!}x^2 – \frac{n(n-1)(n-2)}{3!}x^3 \ldots +(-1)^k\frac{n(n-1)(n-2)\ldots (n-k+1)}{k!}x^k .\ldots + (-1)^nx^n $

 

Note that if we substitute $n$ with its negative value, the expansion fails to converge, i.e.

$(1-x)^{-n}  = 1 - (-n)x + \frac{(-n)(-n-1)}{2!}x^2 - \frac{(-n)(-n-1)(-n-2)}{3!}x^3  +\ldots $

$\qquad =1 + nx + \frac{n(n+1)}{2!}x^2 + \frac{n(n+1)(n+2)}{3!}x^3  +\ldots $

$\qquad = \sum_{i=0}^{\infty}\binom{n+i-1}{i}x^i$

 

(Expansion of $(1+x)^{-n}$ is the same, but with alternating signs. Try to derive it yourself)

In 99% of the cases, we’ll be dealing with $(1-x)^{-n}$ as far as GATE is concerned.

 

Applying the above formula for $n=-1$, we get

$(1-x)^{-1} = 1 + x + x^2 + x^3 + x^4 + . . .$

 (Notice that it’s a generating function for the sequence $<1,1,1,...>$)

 

Similarly for $n=-2$, we get

$(1-x)^{-2} = 1 + 2x + 3x^2 + 4x^3 + 5x^4 + . . .$

(Notice that it’s a generating function for the sequence $<1,2,3,4,5,...>$) 

 

**Operations on Generating Functions**

Let’s assume two generating functions:

$A(x) =  \sum_{i=0}^{\infty}a_ix^i $

$B(x) =  \sum_{i=0}^{\infty}b_ix^i $

 

  1. $\forall \alpha, \beta \in \mathbb{R}$,  $ \alpha A(x) + \beta B(x)$ is another generating function $C(x)$ where
$c_i = \alpha a_i + \beta b_i$,    $ \forall i \in \{0,1,2,3,...\}$ 

 

 

  1.  $A(x)\times B(x)$ is another generating function $D(x)$ where
$d_i = a_0b_i + a_1b_{i-1} + a_2b_{i-2} + . . . + a_ib_0$,    $ \forall i \in \{0,1,2,3,...\}$

 

 

  1. $A^2(x) = A(x) \times A(x)$ is another generating function $E(x)$ where
$e_i = a_0a_i + a_1a_{i-1} + a_2a_{i-2} + . . . + a_ia_0$,    $ \forall i \in \{0,1,2,3,...\}$

 

 

  1. $A(kx)$ is another generating function $F(x)$ where
$f_i = k^ia_i$,    $ \forall i \in \{0,1,2,3,...\}$

 

 

  1. $x^mA(x)$, $m\in\mathbb{N}$ is another generating function $G(x)$ where
$g_i = 0$,     $\forall i \in \{0, 1, 2, …, m-1\}$ 
$g_i = a_{i-m}$,    $\forall i \in \{m ,m+1, m+2, . . .\}$

 

 

  1. $(1-x)A(x) = A(x) – xA(x)$ is another generating function $H(x)$ where
$h_i = a_i – a_{i+1}$,    $\forall i \in \{0,1,2,3,...\}$

 

 

  1. $\frac{A(x)}{(1-x)} = A(x)[1+x+x^2+x^3+...] = A(x) + xA(x) + x^2A(x) + . . . $ is another generating function $J(x)$ where
$j_i = a_0 + a_1 + a_2 + … + a_i$,    $ \forall i \in \{0,1,2,3,...\}$

 

 

  1. $A’(x) = \frac{d}{dx}A(x)$ is another generating function $K(x)$ where  
$k_i = (i+1)a_{i+1}$,    $ \forall i \in \{0,1,2,3,...\}$

 

(**Note: Try deriving all the 8 operations above, pretty easy and mechanical)

 

Kind of questions that may be asked in GATE:

 

  1. Given something like $(a_0x^k + a_1x^{k+1} + a_2x^{k+2} + ...)^m$, find the coefficient of $x^p$, where $k,m,p, a_i \in \mathbb{N}, \forall i \in \{0,1,2,...\}$ 

Approach: If all the coefficients are $1$, take $x^k$ as common and bring it out, i.e.

$[x^k (1 + x + x^2 + x^3 + ...)]^m = x^{km}[1+x+x^2+x^3...]^m = x^{km}[\frac{1}{1-x}]^{m} = x^{km}(1-x)^{-m}$

 

Now $(1-x)^{-m}$ is simply $\sum_{i=0}^{\infty}\binom{m+i-1}{i}x^i$. Putting everything together, we just need to find coefficient of $x^p$ in the expression:

$x^{km}\sum_{i=0}^{\infty}\binom{m+i-1}{i}x^i$.

If we let $p = km + z$ where $z \in \mathbb{N}$, then the coefficient of $x^p$ is just the coefficient of $x^z$ in $\sum_{i=0}^{\infty}\binom{m+i-1}{i}x^i$ which is simply $\binom{m+z-1}{z} = \binom{m+p-km-1}{p-km}$

 

If not all the coefficients $a_i$ in $(a_0x^k + a_1x^{k+1} + a_2x^{k+2} + ...)^m$ are $1$, then like before, bring out $x^k$ and simply try to bring $(a_0 + a_1x + a_2x^2 + ...)$ into closed form (maybe use the “manipulation” technique as mentioned below), then raise it to power $m$ and rest of the calculation is pretty similar to the one I wrote above. Pretty time consuming and tedious stuff depending on what the coefficients are, but considering GATE, the expression should be a direct expansion of $x^k(1\pm x)^{-n}$ where $k,n \in \mathbb{Z}^+$

 

 

  1. Given an expression for calculating each coefficient of some generating function (i.e. each term of the infinite sequence), find the closed form of that generating function.

Approach: Check if the expression involves $’+’$ symbol. If it does, then the resulting generating function will be a sum of generating functions generated by each of those terms. For example, if $a_i = 7i + 6i^2$, then generating function of $A(x)$ is simply the sum of generating functions of the sequences $<(7\times 0), (7\times 1), (7\times 2), . . .>$ and $<(6\times 0^2), (6\times 1^2), (6\times 2^2), ...>$ respectively.

If there’s no $’+’$ symbol, then it’s simply the generating function generated by that single term. Here’s an example to make things concrete:

 

If each term of an infinite sequence $\{a_n\}$ is calculated as $a_i = 7i + 6i^2, \forall i \in \{0,1,2,3,...\}$, find the generating function generated by the sequence $\{a_n\}$ 

Ans: As stated above, if we assume $A(x)$ to be the generating function generated by the sequence $\{a_n\}$, then $A(x) = B(x) + C(x)$, where $B(x)$ and $C(x)$ are generating functions of the sequences $<(7\times 0), (7\times 1), (7\times 2), . . .>$ and $<(6\times 0^2), (6\times 1^2), (6\times 2^2), ...>$ respectively.

 

$B(x) = 0 + 7x + 14x^2 + 21x^3 + … = 7(1x + 2x^2 + 3x^3 + ….) = 7x(1+2x+3x^2+4x^3+...) = 7x(1-x)^{-2}$

 

Calculating $C(x)$ is a bit tricky.

$C(x) = 0 + (6\times 1^2)x + (6\times 2^2)x^2 + (6\times 3^2)x^3 + … = 6(0 + 1^2x + 2^2x^2 + 3^2x^3 + ...)$

 

Using the “manipuation” technique (more on it below),

$(1-x)^{-2} = 1 + 2x + 3x^2 + 4x^3 + ….$

$=> x(1-x)^{-2} = x + 2x^2 + 3x^3 + 4x^4 + ….$

$=> \frac{d}{dx}[x(1-x)^{-2}] = 1^2 + 2^2x + 3^2x^2 + 4^2x^3 + ….$

$=> x[\frac{d}{dx}[x(1-x)^{-2}]] = 1^2x + 2^2x^2 + 3^2x^3 + 4^2x^4 + ….$

 

Therefore, $C(x) = 6[x[\frac{d}{dx}[x(1-x)^{-2}]]]$. Solving it, we get $C(x) = 6x(1+x)(1-x)^{-3}$.

Putting everything together,

 

$A(x) = B(x) + C(x) = \frac{7x}{(1-x)^2} + \frac{6x(1+x)}{(1-x)^3}$


”Manipulation” technique (or what I like to call it)

Given a generating function $A(x) = \sum_{i=0}^{\infty}a_ix^i$, whose closed form is not immediately apparent, start off with a generating function $G(x)$ of the form $\frac{1}{(1\pm x)^n}$ (or even something more complicated) which looks kinda similar to that of $A(x)$. The idea is to manipulate $G(x)$ by a series of multiplication/differentiation/integration ..or whatever operations, to make the RHS of it similar to that of $A(x)$.

 

Here’s a quick example of what I meant. Consider $A(x) = 1^2 + 2^2x + 3^2x^2+ 4^2x^3 + ...$

It’s looks kinda similar to $(1-x)^{-2} = 1 + 2x + 3x^2 + 4x^3 + . . . $.

So we can manipulate it like this:

$=> (1-x)^{-2} = 1 + 2x + 3x^2 + 4x^3 + . . . $

$=> x(1-x)^{-2} = x + 2x^2 + 3x^3 + 4x^4 + . . . $

$=> \frac{d}{dx}[x(1-x)^{-2}] = 1 + 2^2x + 3^2x^2 + 4^2x^3 + . . . = A(x) $

 

Therefore $A(x) = \frac{d}{dx}[x(1-x)^{-2}]  = \frac{1+x}{(1-x)^3}$

 

(These were pretty much my notes on Generating Functions for GATE 2020. Although this should pretty much cover everything needed for GATE, do refer to explanations from books as well (I recommend ”Principles and Techniques in Combinatorics” by Chen Chuan Chong) and of course, practice the questions (a lot of them !!))

posted Mar 27, 2020 edited Jun 22, 2020 by
25
Like
5
Love
0
Haha
1
Wow
0
Angry
0
Sad

4 Comments