retagged by
22,431 views
42 votes
42 votes

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

  1. $\frac{3}{(1-x)^2}$
  2. $\frac{3x}{(1-x)^2}$
  3. $\frac{2-x}{(1-x)^2}$
  4. $\frac{3-x}{(1-x)^2}$
retagged by

11 Answers

Best answer
67 votes
67 votes
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.
edited by
42 votes
42 votes

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

edited by
8 votes
8 votes

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

edited by
Answer:

Related questions

57 votes
57 votes
17 answers
1
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 ___________.
58 votes
58 votes
9 answers
2
Arjun asked Feb 14, 2017
17,494 views
If the ordinary generating function of a sequence $\left \{a_n\right \}_{n=0}^\infty$ is $\large \frac{1+z}{(1-z)^3}$, then $a_3-a_0$ is equal to ___________ .
2 votes
2 votes
1 answer
3