GATE CSE 2022 | Question: 26

Question

Which one of the following is the closed form for the generating function of the sequence $\{ a_{n} \}_{n \geq 0}$ defined below?

$$ a_{n} = \left\{\begin{matrix} n + 1, & \text{n is odd} & \\ 1, & \text{otherwise} & \end{matrix}\right.$$

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

Comments

Solving This problem in 3 minutes is a: 

---

https://gateoverflow.in/371910/gate-cse-2022-question-26?show=384705#a384705  😃🏆

---

$\color{red}{\text{Detailed Video Solution:}}$ GATE 2022 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

The purpose of writing this answer is to show different approaches so that you can use it accordingly. The last method which is a limit based approach might be new for everyone here.

$\textbf{Method 1:}$

$G(x) = 1 + 2x + x^2 + 4x^3 + x^4 + 6x^5 +…$

$= (1 + x^2 + x^4 + ...) + (2x + 4x^3 + 6x^5 +...)$

$= (1 + x + x^2 + x^3 + x^4 + ...) \; – \;(x + x^3 + x^5 + ...) + (2x + 4x^3 + 6x^5 +...)$

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

Here, to get the answer, we need to evaluate $(2x + 4x^3 + 6x^5 +...) $ which can be written as $\Sigma_{n=0}^{\infty} (2n+2) x^{2n+1}$ which is the derivative of $\Sigma_{n=0}^{\infty} x^{2n+2} = \frac{x^2}{1-x^2}$

And, the derivative of  $\frac{x^2}{1-x^2} = \frac{x^2-1+1}{1-x^2} = -1 + \frac{1}{1-x^2}$ is $\frac{2x}{(1-x^2)^2}$

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

$ \textbf{Hence,  (A)} $

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

$\textbf{Method 2:}$

$G(x) = 1 + 2x + x^2 + 4x^3 + x^4 + 6x^5 + ... $
$G(x) = (1 + x^2 + x^4 + ….) + \underbrace{(2x + 4x^3 + 6x^5 +...)}_\text{g’(x)}$
$G(x) = (1 + x^2 + x^4 + ….) + g’(x)$
$G(x) = (1 + x + x^2 +x^3+x^4+ ….)\; – (x + x^3 + x^5 + ...) + g’(x)$
$$G(x) = \frac{1}{1-x} – \frac{x}{1-x^2} + g’(x) $$
Now, $g’(x)= 2x + 4x^3 + 6x^5 +…,$ and integration of $g’(x)$ wrt $x$ gives

$g(x) = (x^2 + x^4 + x^6 +…) + c = \frac{x^2}{1-x^2} + c=  \frac{x^2 -1 + 1}{1-x^2} + c = -1 + \frac{1}{1-x^2} + c,$ where $c$ is arbitrary constant.
And so differentiation of $g(x)$ is,  $g’(x) = \frac{2x}{(1 – x^2)^2}$
It means, $G(x) = \frac{1}{1-x} – \frac{x}{1-x^2} + \frac{2x}{(1 – x^2)^2} = \frac{1}{1-x} – \frac{x(1-x^2)}{(1-x^2)^2} + \frac{2x}{(1 – x^2)^2} = \frac{x(1+x^2)}{(1-x^2)^2} + \frac{1}{1-x}$
$ \textbf{Hence,  (A)} $

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

$\textbf{Method 3:}$

There is a theorem which tells that If $f(x)$ is a generating function for which $f’(a),…,f^{(n)}(a)$ exist

and $a_k = \frac{f^{(k)}(a)}{k!}$ for $0 \leq k \leq n$ and define $P_{n,a} (x) = a_0 + a_1(x-a) + ...+a_n(x-a)^n,$ Then for $\forall n$

$$\lim_{x \rightarrow a} \frac{f(x) - P_{n,a}(x)}{(x-a)^n} = 0$$

So, For $a=0,$ we have, $P_{1,a} (x) = 1+2x ; \ P_{2,a} (x) = 1+2x + x^2 ; \ P_{3,a} (x) = 1+2x+x^2 + 4x^3$

So, we have to find  $\lim_{x \rightarrow 0} \frac{f(x) - P_{n,0}(x)}{x^n}$ where $f(x)$ is a generating function which can be taken from

each option.

If we take $n=1,$ then options $(B), (C)$ will be eliminated and when $n=3$ then $(D)$ will be eliminated. Because

$B)$ $\lim_{x \rightarrow 0} \frac{\frac{x(3-x^2)}{(1-x^2)^2} + \frac{1}{1-x} - 1 -2x }{x} = 2$

$C)$ $\lim_{x \rightarrow 0} \frac{\frac{2x}{(1-x^2)^2} + \frac{1}{1-x} - 1 -2x }{x} = 1$

$D)$ $\lim_{x \rightarrow 0} \frac{\frac{x}{(1-x^2)^2} + \frac{1}{1-x} - 1 -2x – x^2 -4x^3 }{x^3} = -1$

$ \textbf{Hence,  (A)} $

Here, to solve limits, you don’t have to use L’Hopital's rule which involves the differentiation. Here, you can find limits by some manipulation and also proof of this theorem is not difficult. If anyone wants a proof then I will add it.

Answer 2

$<a,b,c,d,e,f...>$ = $a + bx + cx^{2} + dx^{3} + ex^{4} + fx^{5} + ...$

$<1,2,1,4,1,6...>$ = $<1,1,1,1,1,1...> + <0,1,0,3,0,5,...>$

$<1,2,1,4,1,6...>$ = $\frac{1}{1-x} + <0,1,0,3,0,5,...>$

$<1,3,5,7,9,11...>$ = $<1,1,1,1,1,1,...> + <0,2,4,6,8,10...>$

$<1,3,5,7,9,11...>$ = $\frac{1}{1-x} + <0,2,4,6,8,10...>$

$<2,4,6,8,10,12...>$ = $2<1,2,3,4,5,6...>$

$<1,2,3,4,5,6...>$ = $\frac{\mathrm{d} }{\mathrm{d} x} <1,1,1,1,1,1,...>$ =$\frac{\mathrm{d} }{\mathrm{d} x}$ $\frac{1}{(1-x)}$ = $\frac{1}{(1-x)^{2}}$

$<2,4,6,8,10...>$ = $2<1,2,3,4,5,6...>$ =  $\frac{2}{(1-x)^{2}}$

$<0,2,4,6,8,10...>$ = $\frac{2x}{(1-x)^{2}}$ (Multiply by $x$ on both sides of the above equation)

$<1,3,5,7,9,11...>$ = $\frac{2x}{(1-x)^{2}} + \frac{1}{1-x}$ = $\frac{2x}{(1-x)^{2}} + \frac{1-x}{(1-x)^{2}}$ = $\frac{1+x}{(1-x)^{2}}$

$<1,0,3,0,5,0,7,...>$ = $\frac{1+x^{2}}{(1-x^{2})^{2}}$ (Substitute $x$ with $x^{2}$ on both sides of the above equation)

$<0,1,0,3,0,5,...>$ = $\frac{x(1+x^{2})}{(1-x^{2})^{2}}$ (Multiply by $x$ on both sides of the above equation)

$<1,2,1,4,1,6...>$ = $\frac{x(1+x^{2})}{(1-x^{2})^{2}} + \frac{1}{1-x} $

Refer generating functions from Oscar Levin to become good at manipulating sequences. https://discrete.openmathbooks.org/pdfs/dmoi-tablet.pdf

Comments

@ankitgupta.1729 I used the notation that you used in one of the comments. Can you verify this answer?

---

It is correct.