in Combinatory retagged ago by
2,171 views
9 votes
9 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 retagged ago by
by
2.2k 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.
1
1
That’s a good question and deserves a good answer ;)
1
1

5 Answers

10 votes
10 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

2 Comments

An easier way to solve:-

After we get $A+B = \frac{1}{1-x^2} + \frac{2x}{(1-x^2)^2}$, we can do option elemination very fast. Assuming x=3, we get $A+B = \frac{1}{1-9} + \frac{6}{(1-9)^2}$ which simplifies to be $\frac{-1}{32}$.

If we solve option A, $\frac{x(1+x^{2})}{(1-x^{2})^{2}} + \frac{1}{1-x}$ by putting x = 3, we get

$\frac{3(1+3^{2})}{(1-3^{2})^{2}} + \frac{1}{1-3} = \frac{3(1+9)}{(-8)^{2}} - \frac{1}{2} = \frac{30}{64} - \frac{1}{2} = \frac{-1}{32}$, which is exactly same as our result. Hence option A is true.
6
6
excellent answer
1
1
6 votes
6 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

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
4 votes
4 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
2 votes
2 votes
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.
edited by