GATE CSE 2018 | Question: 1

Question

Which one of the following is a closed form expression for the generating function of the sequence $\{a_n\}$, where $a_n = 2n +3 \text{ for all } n=0, 1, 2, \dots$?

• A. $\frac{3}{(1-x)^2}$
• B. $\frac{3x}{(1-x)^2}$
• C. $\frac{2-x}{(1-x)^2}$
• D. $\frac{3-x}{(1-x)^2}$

Comments

@sauravgahlawat can u plz explain how r u getting 5? 

r u putting x=1 in options? cz like tht it’s not possible in a1

---

@MANSI_SOMANI Differentiate all options once and then put x = 0 for $a_{1}$. General formula for $a_{n}$ is given above.

---

$\color{red}{\text{Detailed Video Solution:}}$ GATE 2018 Generating Function, Click HERE.

$\color{red}{\text{Generating Function Complete Playlist,}}$ ALL GATE Questions, Extended Binomial Theorem: https://youtube.com/playlist?list=PLIPZ2_p3RNHiu4mkROrhREYsslvp2lL5l 

Knowing the “Extended Binomial Theorem” makes Generating Function topic extremely easy. Watch the above playlist to learn everything, with Proof & Variations. 

Answer 1

Given that $a_{n}=2n+3$

Let $G(x)$ be the generating function for the sequence $\{a_{n}\} .$

So, $G(x)= \sum_{n=0}^{\infty }a_{n}x^{n}$
$\quad \quad = \sum_{n=0}^{\infty} (2n+3) x^{n}$
$\quad \quad = \sum_{n=0}^{\infty } (2n)x^{n} + \sum_{n=0}^{\infty }(3)x^{n}$
$\quad \quad = 2 \sum_{n=0}^{\infty }nx^{n} + 3 \sum_{n=0}^{\infty }x^{n}$
$\quad \quad = 2A + 3B$

Now, $A= \sum_{n=0}^{\infty } nx^{n}$. By expanding, it will look like: $0+1x+2x^{2}+3x^{3}+\ldots$ which is an AGP series with first term, $(a)=0,$ common difference, $(d)=1,$ ratio, $(r)=x.$

Sum of infinite AGP series $= \frac{a}{1-r} + \frac{dr}{(1-r)^{2}}$.

So, $A= \frac{0}{1-x} + \frac{x}{(1-x)^{2}} = \frac{x}{(1-x)^{2}}$

and $B = \sum_{n=0}^{\infty }x^{n} = 1+x^{}+x^{2}+x^{3}+\ldots = \frac{1}{1-x}$

Therefore, $2A+3B= \frac{2x}{(1-x)^{2}} + \frac{3}{1-x}$

$\quad \quad \quad =  \frac{2x+3-3x}{(1-x)^{2}} = \frac{3-x}{(1-x)^{2}}$

Option (D) is correct.

Comments

Is it necessary to consider first term 0 or we can leave it gives different value

---

∑∞n=0xn=1+x+x2+x3+…= 1 / (1-x)

If we try to find out the sequence using the formula of GP then wont it be:

(xn – 1 )/ (x – 1)  ?

---

@jiminpark it uses the sum of infinite geometric series. 
 

Good resource for generating functions:

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6_042JF10_chap12.pdf

Answer 2

Generating Function for sequence $g_0,g_1,g_2,g_3,g_4....$ is:

$ g_{0} + g_{1}x + g_{2}x^{2} + g_{3}x^{3} + g_{4}x^{4}+.....$

For $a_n = 2n+3$, sequence is ${3,5,7,9.....}$ and the corresponding generating function will be:

$G(x)= 3 + 5x + 7x^{2} + 9x^{3} + 11x^{4}+.....$, which is an Arithmatic-Geometric(AGP) series. The formula for sum of AGP upto infinite term is :

$S_{infinite}$= $\frac{a}{(1-r)}$+$\frac{dr}{(1-r)^2}$, using this formula , the closed expression for our generating function for $a=3, d=2, r= x$

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

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

=$\frac{(3-x)}{(1-x)^2}$

Answer (D).

PS:Good Read https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6_042JF10_chap12.pdf

Comments

Simple and concise explanation!

---

This should be the best answer!!

---

Admins make it best answer.

Answer 3

D is the answer.

Comments

how bro explain ..or upload solution

Answer 4

Find the generating function of the sequence $\{a_{n}\}$ where $a_{n}=2n+3$ for all $n=0,1,2,\dots$

Generating sequence$: a_{0} = 3 , a_{1} = 5, a_{2} = 7,a_{3} = 9, a_{4} = 11,\dots$

We know that Ordinary Generating Function, given that generating sequence are $\langle a_{0},a_{1},a_{2},a_{3},a_{4},\dots\rangle$

$$G(x) = a_{0} + a_{1}x + a_{2}x^{2} + a_{3}x^{3} + a_{4}x^{4}+\dots$$

$$G(x) = \sum_{k=0}^{\infty} a_{k}\cdot x^{k}$$

$\therefore$ In question given sequence is $\langle \:3,5,7,9,11,\dots\rangle$

We can write the generating function:

$G(x) = 3 + 5x +7x^{2} + 9x^{3} + 11x^{4}+\dots \rightarrow(1)$

Lets generating sequence are $\langle\: 1,1,1,1,1,1,1,1,1,\dots \rangle$  

We can find the generating function:

$1+ x + x^{2} + x^{3} + x^{4} + x^{5} + x^{6} +\dots \Leftrightarrow \dfrac{1}{(1-x)} \rightarrow (2)\:\:\:\: [\because\text{Sum of Infinite series}]$

Multiply $'2x'$ both sides,we get

$2x+ 2x^{2} + 2x^{3} + 2x^{4} + 2x^{5} +2x^{6} + 2x^{7} +\dots \Leftrightarrow \dfrac{2x}{(1-x)}$ 

Differentiate both side with respect to $'x'$ and get,

$\dfrac{\mathrm{d} }{\mathrm{d} x}(2x+ 2x^{2} + 2x^{3} + 2x^{4} + 2x^{5} +2x^{6} + 2x^{7} +\dots)\Leftrightarrow \dfrac{\mathrm{d} }{\mathrm{d} x}\left(\dfrac{2x}{1-x}\right)$

$2+ 4x + 6x^{2} + 8x^{3} + 10x^{4} +\dots \Leftrightarrow \dfrac{(1-x).2-2x(-1)}{(1-x)^{2}}$ 

$2+ 4x + 6x^{2} + 8x^{3} + 10x^{4} +\dots \Leftrightarrow \dfrac{2-2x+2x}{(1-x)^{2}}$ 

$2+ 4x + 6x^{2} + 8x^{3} + 10x^{4} +\dots \Leftrightarrow \dfrac{2}{(1-x)^{2}} \rightarrow(3)$

Adding the equation $(2)$ and equation $(3),$we get,

$1+ x + x^{2} + x^{3} + x^{4} + x^{5} + x^{6} +\dots \Leftrightarrow \dfrac{1}{(1-x)}$

$2+ 4x + 6x^{2} + 8x^{3} + 10x^{4} +\dots \Leftrightarrow \dfrac{2}{(1-x)^{2}}$

-----------------------------------------------------------------------------------------------------------------

$3+ 5x + 7x^{2} + 9x^{3} + 11x^{4} +\dots \Leftrightarrow \dfrac{1}{(1-x)} + \dfrac{2}{(1-x)^{2}}$

$G(x) = \dfrac{1}{(1-x)} + \dfrac{2}{(1-x)^{2}}$

$G(x) = \dfrac{(1-x) + 2}{(1-x)^{2}}$

$G(x)=\dfrac{3-x }{(1-x)^{2}}$

$$\textbf{(OR)}$$

From the equation $(2),$

$1+ x + x^{2} + x^{3} + x^{4} + x^{5} + x^{6} +\dots \Leftrightarrow \dfrac{1}{(1-x)} \rightarrow (2)\:\:\:\: [\because\text{Sum of Infinite series}]$

Differentiate both side with respect to $'x'$ and get,

$1+ 2x + 3x^{2} + 4x^{3} + 5x^{4} + 6x^{5} + 7x^{6} +\dots \Leftrightarrow \dfrac{1}{(1-x)^{2}}\rightarrow (3)\:\:\: \left[\because \left(\dfrac{u}{v}\right)^{'} = \dfrac{u'\:v - u\:v'}{v^{2}}\right]$(quotient rule)

In equations $(3)$ multiply $'3'$ both sides, and we get

$3+ 6x + 9x^{2} + 12x^{3} + 15x^{4} + 18x^{5} + 21x^{6} +\dots \Leftrightarrow \dfrac{3}{(1-x)^{2}}\rightarrow (4)$

In equations $(3)$ multiply $'x'$ both sides, and we get

$3x+ 6x^{2} + 9x^{3} + 12x^{4} + 15x^{5} + 18x^{6} +\dots \Leftrightarrow \dfrac{x}{(1-x)^{2}}\rightarrow (5)$

Subtract the equation $(4)$ and equation $(5),$we get,

$3+ 6x + 9x^{2} + 12x^{3} + 15x^{4} + 18x^{5} + 21x^{6} +\dots \Leftrightarrow \dfrac{3}{(1-x)^{2}}\rightarrow (4)$

$3x+ 6x^{2} + 9x^{3} + 12x^{4} + 15x^{5} + 18x^{6} +\dots \Leftrightarrow \dfrac{x}{(1-x)^{2}}\rightarrow (5)$

-----------------------------------------------------------------------------------------------------------------

$3+5x+7x^{2} +9x^{3}+11x^{4} + 13x^{5} + 15x^{6} + \dots \Leftrightarrow \dfrac{3}{(1-x)^{2}}  - \dfrac{x}{(1-x)^{2}}$

$3+5x+7x^{2} +9x^{3}+11x^{4} + 13x^{5} + 15x^{6} + \dots \Leftrightarrow \dfrac{3-x}{(1-x)^{2}}$

So, the correct answer is $(D).$