retagged by
9,290 views
26 votes
26 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}$
retagged by

6 Answers

3 votes
3 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
2 votes
2 votes

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

Answer:

Related questions

17 votes
17 votes
3 answers
2
Arjun asked Feb 15, 2022
10,225 views
The number of arrangements of six identical balls in three identical bins is _____________ .
57 votes
57 votes
17 answers
3
Sandeep Singh asked Feb 12, 2016
25,578 views
The coefficient of $x^{12}$ in $\left(x^{3}+x^{4}+x^{5}+x^{6}+\dots \right)^{3}$ is ___________.