in Combinatory edited by
966 views
4 votes
4 votes

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.$$

  1. $\frac{x(1+x^{2})}{(1-x^{2})^{2}} + \frac{1}{1-x}$
  2. $\frac{x(3-x^{2})}{(1-x^{2})^{2}} + \frac{1}{1-x}$
  3. $\frac{2x}{(1-x^{2})^{2}} + \frac{1}{1-x}$
  4. $\frac{x}{(1-x^{2})^{2}} + \frac{1}{1-x}$
in Combinatory edited by
by
2441 3624 5537
966 views

2 Comments

This is insane how can one solve this is 3 minutes? Should give atleast 3 marks. On top of that they have 'simplified' the options.
0
0
That’s a good question and deserves a good answer ;)
0
0

Subscribe to GO Classes for GATE CSE 2022

4 Answers

5 votes
5 votes
 
Best answer
Answer A

 Corresponding Sequence would be –

$a_0, a_1, a_2, a_3, a_4, \dots \infty $

$=\color{blue}1,  \color{red}2, \color{blue}1,  \color{red}4, \color{blue}1, \color{red}6, \color{blue}1,  \color{red}8, \color{blue}1,  \color{red}{10},  \color{blue}1 \dots \infty$

$ =\color{blue}1x^0+\color{red}2x^1+\color{blue}1x^2+\color{red}4x^3+\color{blue}1x^4+\color{red}6x^5+\color{blue}1x^6+\color{red}8x^7+\color{blue}1x^8+\color{red}{10}x^9+\color{blue}1x^{10} \dots $

$=\underbrace{(\color{blue}1x^0+\color{blue}1x^2+\color{blue}1x^4+ \dots \infty) }_\text{A} +\underbrace{(\color{red}2x^1+\color{red}4x^3+\color{red}6x^5+\color{red}8x^7+\color{red}{10}x^9+ \dots \infty) }_\text{B} $

$A = 1+x^2+x^4+x^6+\dots \infty $

$\qquad =\frac{1}{1-x^2} $

$B= \color{red}2x^1+\color{red}4x^3+\color{red}6x^5+\color{red}8x^7+\color{red}{10}x^9+ \dots \infty \tag{1}$

It is sum of AP and GP.  (Where $\color{red}2, \color{red}4, \color{red}6, \color{red}8, \color{red}{10}$ forms a GP and $x^1, x^3, x^5, x^7, x^9$ forms a GP. )

$x^2B= \color{red}2x^3+\color{red}4x^5+\color{red}6x^7+\color{red}8x^9+\color{red}{10}x^{11}+ \dots \infty \tag{2} $

$B-x^2B = \color{red}2x^1+\color{red}2x^3+\color{red}2x^5+\color{red}2x^7+\color{red}2x^9+ \dots \infty $

$= \color{red}2x(1+x^2+x^4+x^6+x^8+ \dots \infty) $

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

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

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

Since none of the the option is matching hence let’s simplify $A$.
$A = \frac{1}{(1-x)(1+x)} = \frac{1+x-x}{(1-x)(1+x)} = \frac{1+x}{(1-x)(1+x)}- \frac{x}{(1-x)(1+x)} = \frac{1}{1-x}- \frac{x}{(1-x^2)}$

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

Hence A is answer.
edited by
by
221 277 348
2 votes
2 votes
an=an+1 when n is odd
     =1

Series like
a0=1
a1=2
.
.
.
So 1,2,1,4,1,6,.....

We know
 1,1,1...= 1/(1-x)
0,1,1,1,...........=x/(1-x)
1,2,3,4.............=1/(1-x)^2
1,0,1,0,1..........=1/(1-x^2)
1,0,2,0,3...........=1/(1-x^2)^2

Here series be like
(1,1,1,1,1,1.....) + (0,1,0,2,0,3,0.....)+(0,0,0,1,0,2,0,3....)
=(1,2,1,4,1,6)

So (1,1,1,1,1,1.....)= 1/(1-x)

(0,1,0,2,0,3,0.....)=x/(1-x^2)^2

(0,0,0,1,0,2,0,3,....)=x^3/(1-x^2)^2

So now sum them x(1+x^2)/(1-x^2)^2 + 1/(1-x)

For better understanding:

http://discrete.openmathbooks.org/dmoi2/section-27.html
by
1

1 comment

For me, Your answer is the best among all the answers here your generating function is according to the given answer and take less time. (+1) for the answer.

It is not in latex, if you allow me, I can edit it.

Instead of breaking original sequence into 3 parts, I had broken into 2 parts:

$<1,2,1,4,1,6,1,8,…..>\; =\; <1,2,3,4,5,6,...>\; – \; <0,0,2,0,4,0,...>$

$\leftrightarrow \frac{1}{(1-x)^2} - \frac{2x^2}{(1 – x^2)^2}$

But it is not matching with the options because I have to include $<1,1,1,...>$ sequence for $\frac{1}{1 – x}.$ I was thinking to add this here but since you have already posted here, so I have added answer with another approach.
0
0
2 votes
2 votes
This answer is for those who don’t know how to solve Arithmetico–Geometric series.

$\sum_{n=0}^{\infty} x^n = 1+x + x^2 + x^3 +…… = \frac{1}{1-x}$                      $(1)$

Differentiating with respect to $x$

$n \sum_{n=0}^{\infty}x^{n-1} = \frac{1}{(1-x)^2}$

$n \sum_{n=1}^{\infty}x^{n-1} = \frac{1}{(1-x)^2}$

So, $<1,2,3,…..>\;\; \leftrightarrow \;\;\frac{1}{(1-x)^2}$                                    $(2)$

Replace $x$ with $x^2$ in $(1)$

$\sum_{n=0}^{\infty} x^{2n} =  \frac{1}{1-x^2}$

$\sum_{n=0}^{\infty} <1,1,…..> x^{2n} =  \frac{1}{1-x^2}$                                                 $(3)$

Suppose, sequence $\{g_n\}$ has a generating function is $G(z).$ i.e. $\sum_{n}^{}g_n z^n = G(z),$ So,

$G(z) + G(-z) = \sum_{n}^{}g_n (1+(-1)^n) z^n$

It means, $\frac{G(z) + G(-z)}{2} = \sum_{n}^{}g_{2n} z^{2n}$ (Formula to get even-numbered sequence i.e. $g_0,g_2,g_4,..$)

Similarly, $\frac{G(z) - G(-z)}{2} = \sum_{n}^{}g_{2n+1} z^{2n+1}$ (Formula to get odd-numbered sequence i.e. $g_1,g_3,g_5,..$)

So, from $(2),$ we get the odd-numbered sequence,

$ \sum_{n=0}^{\infty}<2,4,6,….> x^{2n+1}= \frac{\frac{1}{(1-x)^2} – \frac{1}{(1+x)^2}}{2}$                               $(4)$

Now, comes to given sequence in the question,

$<1,2,1,4,1,6,….>\;\; \leftrightarrow \;\; G(x)$

Applying the formula to get even and odd numbered sequence and from $(4)$ and $(3)$

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

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

Adding these $2$ equations to eliminate $G(-x)$,

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

To get the correct option, we need to simplify it which I will not do.

Since, $G(x)$ is simply a formula, so, I can put $x=0,1,2,..$ (For $x \neq 1$, $G(x)$ is not defined ) and check options which does match with our $G(x)$ since all options have $\frac{1}{1-x}$ and $(1 – x^2)^2$ in denominator of first part, we would have to compute it once.

 For, $x=0$ all options give $G(0) = 1$ and our $G(0)=1$ also.

Now, for $x=2,$ our not good-looking $G(x)$ gives, $G(2) = \frac{1}{9}$

In options, $G(2)$ in $ A) \frac{10}{9} – 1 = \frac{1}{9}$, $(B) \frac{-2}{9} – 1 = -ve,$ $(C) \frac{4}{9} – 1 = -ve,$ $(D) \frac{2}{9} – 1 = -ve$

Hence, Answer is $(A)$
edited by
by
51 106 307
0 votes
0 votes
$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}$
Hence,  $(A)$
edited by
by
51 106 307
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true