retagged by
17,507 views
58 votes
58 votes
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 ___________ .
retagged by

9 Answers

9 votes
9 votes
$ \frac {(1+z)}{(1-z)^3}$=$(1+z) \ \sum_{r=o}^{\infty} \binom{3-1+r}{r} z^r$   ( $\because$as we know $ \frac{1}{(1-z)^n}= \sum_{r=o}^{\infty} \binom{n-1+r}{r} z^r $)

           =$(1+z)\binom{2+r}{r} z^r $

           =$\binom{2+r}{r} z^r +\binom{2+r}{r} z^{r+1}  $

   $a_3\ means \ coefficient \ of \ z^3, a_0\ means \ coefficient \ of \ z^0$

for $a_3$ in first term r =3,in second term r=2

$a_3$=$\binom{5}{3}+\binom{4}{2}$=16

for $a_0$ only first term can give $x^0$ coeff. $a_0=\binom{2+0}{0}$=1

$a_3-a_0$=16-1=15.
6 votes
6 votes

Given generating function $G(z) = \dfrac{1 + z}{(1-z)^{3}}$

We know that if given sequence is

$(1,1,1,1,1,1,\dots) \Leftrightarrow \dfrac{1}{1-z}$

$\left[\text{Infinite series summation}\: S = \dfrac{a}{1-r}; r< 1\: \text{(or)}\: S = \dfrac{a}{r-1};r > 1\: \text{Where a = first term and r = common ratio} \right]$

$(1 + z + z^{2} + z^{3} + z^{4} + \dots) \Leftrightarrow \dfrac{1}{1-z}$

Differentiate both side with respect to $z$

$\dfrac{\mathrm{d} }{\mathrm{d} z} (1 + z + z^{2} + z^{3} + z^{4} + \dots) \Leftrightarrow \dfrac{\mathrm{d} }{\mathrm{d}z } \left(\dfrac{1}{1-z}\right)$

$(0+1+2z+3z^{2}+4z^{3}+\dots) \Leftrightarrow \dfrac{1}{(1-z)^{2}}$

$(1+2z+3z^{2}+4z^{3}+\dots) \Leftrightarrow \dfrac{1}{(1-z)^{2}}$

Multiply both side by $z$

$(z+2z^{2}+3z^{3}+4z^{4}+\dots) \Leftrightarrow \dfrac{z}{(1-z)^{2}}$

Again differentiate both side with respect to $z$

$(1+4z+9z^{2}+16z^{3}+\dots) \Leftrightarrow \dfrac{(1-z)^{2}(1) - z(2(1-z))(-1)}{((1-z)^{2})^{2}}$

$(1+4z+9z^{2}+16z^{3}+\dots) \Leftrightarrow \dfrac{1+z^{2}-2z +2z(1-z)}{(1-z)^{4}}$

$(1+4z+9z^{2}+16z^{3}+\dots) \Leftrightarrow\dfrac{1+z^{2}-2z +2z-2z^{2}}{(1-z)^{4}}$

$(1+4z+9z^{2}+16z^{3}+\dots) \Leftrightarrow \dfrac{1+z^{2}-2z^{2}}{(1-z)^{4}}$

$(1+4z+9z^{2}+16z^{3}+\dots) \Leftrightarrow \dfrac{1^{2}-z^{2}}{(1-z)^{4}}$

$(1+4z+9z^{2}+16z^{3}+\dots) \Leftrightarrow\dfrac{(1-z)(1+z)}{(1-z)^{4}}$

$(1+4z+9z^{2}+16z^{3}+\dots) \Leftrightarrow \dfrac{(1+z)}{(1-z)^{3}} = G(z)$

$G(z) = 1+4z+9z^{2}+16z^{3}+\dots\:\:\:\rightarrow(1)$ 

Ordinary Generating Function

$G(z) = a_{0} + a_{1}z +a_{2}z^{2} +a_{3}z^{3}+a_{4}z^{4}+\dots\:\:\:\rightarrow(2)$

Compare equation $(1)$ and equation $(2)$ and we get

$a_{0} =1 $

$a_{3}=16$

Now we can easily find $a_{3} -a_{0}=16-1=15$

So, the correct answer is $15.$

See this pdf for generating function it might be helpful.

see here

______________________________________________________________________

$\textbf{Second Method:}$

  • $1+x+x^{2}+x^{3}+\dots + x^{n} = \dfrac{1-x^{n+1}}{1-x}$
  • $\dfrac{1}{(1-x)^{n}} = \displaystyle{}\sum^{\infty}_{0} \binom{n+k-1}{k}\:x^{k}$

Given generating function $G(z) = \dfrac{1 + z}{(1-z)^{3}}$

$\implies G(z) = (1+z)\:\displaystyle{}\sum^{\infty}_{0} \binom{3+k-1}{k}\:z^{k}$

$\implies G(z) = (1+z)\:\displaystyle{}\sum^{\infty}_{0} \binom{2+k}{k}\:z^{k}$

$\implies G(z) = (1+z)\left[1+3z+6z^{2} + 10z^{3} + \dots \right]$

$\implies G(z) = 1+3z+6z^{2} + 10z^{3} + \dots + z+3z^{2}+6z^{3} + 10z^{4} + \dots$

$\implies G(z) = 1+4z+9z^{2} + 16z^{3} + \dots$

Ordinary Generating Function

$G(z) = a_{0} + a_{1}z +a_{2}z^{2} +a_{3}z^{3}+a_{4}z^{4}+\dots\:\:\:\rightarrow(1)$

$a_{0} =1 ,a_{3}=16$

$ \therefore a_{3} -a_{0}=16-1=15$

So, the correct answer is $15.$

edited by
1 votes
1 votes

If we have given the ordinary generating function then we can use the following approach to find the sequence $\{a_n\}^{\infty}_{n=0}.$ It is a systematic approach and applicable to any type of generating function.

We can write the Taylor series about origin for the given generating function as :

$f(x) = a_{0} x^{0} + a_{1} x^{1} +a_{2} x^{2}+a_3 x^3+........= \sum_{n}^{} \frac{f^{(n)}(0)}{n!}x^n$ for $n=0,1,2,3,....$

So, for any ordinary generating function,

sequence is : $ a_n= \frac{f^{(n)}(0)}{n!},$ for $n=0,1,2,3,.........$

where, $f^{(n)}$ means $n^{th}$ derivative of $f$.

So, here,

$f(z) =\frac{1+z}{(1-z)^3}= a_{0} z^{0} + a_{1} z^{1} +a_{2} z^{2}+a_3 z^3+........=  \sum_{n}^{} \frac{f^{(n)}(0)}{n!}z^n$ for $n=0,1,2,3,....$
 

So,

      $a_0 = \frac{f(0)}{0!}$,

      $a_1 = \frac{f'(0)}{1!}$,

      $a_2 = \frac{f''(0)}{2!}$,

      $a_3 = \frac{f'''(0)}{3!}$ and so on.

Since, here, $f(z) = \frac{1+z}{(1-z)^3}$ $\Rightarrow f(0) = 1$

Now, $f'(z) = \frac{2(z+2)}{(1-z)^4}$

$f''(z) = \frac{6(z+3)}{(1-z)^5}$

$f'''(z) = \frac{24(z+4)}{(1-z)^6}$ $\Rightarrow f'''(0) = 96$

So, $a_0 = \frac{f(0)}{0!} = \frac{1}{0!} = 1$ and $a_3 = \frac{f'''(0)}{3!} = \frac{96}{3!} = 16$

Hence, $a_3 - a_0 = 16 - 1 = 15$

Answer:

Related questions

57 votes
57 votes
17 answers
1
Sandeep Singh asked Feb 12, 2016
25,583 views
The coefficient of $x^{12}$ in $\left(x^{3}+x^{4}+x^{5}+x^{6}+\dots \right)^{3}$ is ___________.
31 votes
31 votes
5 answers
2
Madhav asked Feb 14, 2017
10,827 views
In a B+ Tree , if the search-key value is $8$ bytes long , the block size is $512$ bytes and the pointer size is $2\;\text{B}$ , then the maximum order of the B+ Tree is ...
62 votes
62 votes
6 answers
4
Madhav asked Feb 14, 2017
18,239 views
Consider the following tables $T1$ and $T2.$$$\overset{T1}{\begin{array}{|c|c|c|} \hline \textbf {P} & \textbf {Q} \\\hline \text {2} & \text{2 }\\\hline \text{3} & \te...