GATE CSE 2017 | Set 2 | Question: 47

Question

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

Comments

can you please elaborate this sir ?

---

@KUSHAGRA गुप्ता

best solution

---

$\color{red}{\text{Detailed Video Solution:}}$ GATE 2017 Generating Function, Click HERE.

$\color{red}{\text{Generating Function Complete Playlist,}}$ ALL GATE Questions, Extended Binomial Theorem: https://youtube.com/playlist?list=PLIPZ2_p3RNHiu4mkROrhREYsslvp2lL5l 

Knowing the “Extended Binomial Theorem” makes Generating Function topic extremely easy. Watch the above playlist to learn everything, with Proof & Variations.

Answer 1

$\frac{1+z}{(1-z)^3} = (1+z)(1-z)^{-3}$

$(1-z)^{-3} = 1 + \binom{3}{1}z + \binom{4}{2}z^2 + \binom{5}{3}z^3 + \dots \infty$

${(1+z)(1-z)^{-3} = (1+z)*(1 + \binom{3}{1}z + \binom{4}{2}z^2 + \binom{5}{3}z^3 + \dots \infty)}$

$a_0$ is the first term in the expansion of above series and $a_3$ is the fourth term (or) coefficient of $z^3$

$a_0$ = coefficient of $z^0 = 1$
$a_3$ = coefficient of $z^3 = \binom{5}{3} + \binom{4}{2} = 10 + 6$

${\Rightarrow a_3 - a_0 = 16 - 1 = 15}$

Comments

plz suggest some good resource to read this topic

---

This is a good playlist for Discrete u can follow this topic from here or u can follow keneth rosen https://www.youtube.com/playlist?list=PL0862D1A947252D20

---

Generating functions 

Answer 2

Ans : 15

Comments

this is the correct formula.

---

nice and easy explanation

---

good explaination

Answer 3

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

Comments

nice explanation, thanks.

---

Perfect!!

Answer 4

yes 15 is correct ans 

Answer 5

Given any sequence say (a₀,a₁,a₂,a₃,....) we represent in generating functions as

                        a₀ + a₁.z + a₂.z² + a₃.z³ + a₄.z⁴ + ....

                                        where z is called as indicator variable.

Now given in question that

                        a₀ + a₁.z + a₂.z² + a₃.z³ + a₄.z⁴ + .... 

                                     = (1 + z) / (1 - z)³

                                                 = (1 + z).( 1 / (1-z)³ )

                                     = (1 + z).(1 / 1-z)³ 

                                     = (1 + z).(1 + z + z² + z³ +z⁴ + ....)³

                                     = 1.(1 + z + z² + z³ +z⁴ + ....)³ + z.(1 + z + z² + z³ +z⁴ + ....)³ ==> eqn 1

From eqn 1, I can say that a₀ = coefficent of z⁰ and a₃ = coefficient of z³

        1.(1 + z + z² + z³ +z⁴ + ....)³

                 = 1.(1 + z + z² + z³ +z⁴ + ....).(1 + z + z² + z³ +z⁴ + ....).(1 + z + z² + z³ +z⁴ + ....)                

               coefficient of z⁰ = 1 (Because z⁰ is possible only if 1 is taken in all 3 bracket terms)

               coefficient of z³ = number of ways of choosing (1,z,z²) + (1,1,z³) + (z,z,z) 

                                     = (3 * 2) + (3C₂ ) + 1

                                     = 6 + 3 + 1

                                     = 10      

z.(1 + z + z² + z³ +z⁴ + ....)³

                                    = z.(1 + z + z² + z³ +z⁴ + ....).(1 + z + z² + z³ +z⁴ + ....).(1 + z + z² + z³ +z⁴ + ....)

                  coefficient of z⁰ = 0 (as we have a z outside and z⁰ is not possible.

                  coefficient of z³ = coefficient of z² from bracket terms

                                            = number of ways choosing (1,1,z²) + (1,z,z)

                                            = 3C₂ + 3C2

                                            = 6

a₀ = Total coefficient of z⁰ =  1 + 0 = 1 

a₃ = Total coefficent of z³ = 10 + 6

                                  = 16

          a₃ - a₀ = 16 - 1 = 15.

Comments

Best answer, thanks

Answer 6

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