12,947 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 ___________ .

$\sum_{n=0}^{\infty }a_{n}z^n=(1+z) \sum_{n=0}^{\infty }\ ^{3-1+n}C_{n}z^{n}$

$\sum_{n=0}^{\infty }a_{n}z^n=(1+z) \sum_{n=0}^{\infty }\ ^{2+n}C_{n}z^{n}$

$\sum_{n=0}^{\infty }a_{n}z^n=\sum_{n=0}^{\infty }\ ^{2+n}C_{n}z^{n}+z\sum_{n=0}^{\infty }\ ^{2+n}C_{n}z^{n}$

$for\ a_{3}:put\ n=3+ put\ n=2$

$a_{3}=\ ^{5}C_{3}+\ ^{4}C_{2}=16$

$for\ a_{0}:put\ n=0+ can't\ provide\ coefficient\ for\ a_{0}\ because\min\ z\ is\ always\ present$

$a_{0}=\ ^{2}C_{0}=1$

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

can you please elaborate this sir ?

### Subscribe to GO Classes for GATE CSE 2022

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

$\color{navy}{(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$

$\color{maroon}{\Rightarrow a_3 - a_0 = 16 - 1 = 15}$
by
64 106 319

(1−z)−3=1+(3c1)z+(4c2)z2+(5c3)z3+…∞

from where this formula come  ?

For the coefficient of z3=($\binom{5}{3}$)+($\binom{4}{2}$) = 10+6 .. why are you taking both the terms? why co-eff of z2 as well as z3 are you evaluating?

Won't only z3 co-eff do?

I know I'm wrong somewhere. But couldn't find where?

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

Ans : 15

by
2 6 10

can you explain the step after 'solving'
Open the brackets and multiply (1+z) to the terms inside. Simple calculation.

this is the correct formula.

yes 15 is correct ans

by
20 56 84

Given any sequence say (a0,a1,a2,a3,....) we represent in generating functions as

a0 + a1.z + a2.z2 + a3.z3 + a4.z4 + ....

where z is called as indicator variable.

Now given in question that

a0 + a1.z + a2.z2 + a3.z3 + a4.z4 + ....

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

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

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

= (1 + z).(1 + z + z2 + z3 +z4 + ....)3

= 1.(1 + z + z2 + z3 +z4 + ....)3 + z.(1 + z + z2 + z3 +z4 + ....)3 ==> eqn 1

From eqn 1, I can say that a0 = coefficent of z0 and a3 = coefficient of z3

1.(1 + z + z2 + z3 +z4 + ....)3

= 1.(1 + z + z2 + z3 +z4 + ....).(1 + z + z2 + z3 +z4 + ....).(1 + z + z2 + z3 +z4 + ....)

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

coefficient of z3 = number of ways of choosing (1,z,z2) + (1,1,z3) + (z,z,z)

= (3 * 2) + (3C2 ) + 1

= 6 + 3 + 1

= 10

z.(1 + z + z2 + z3 +z4 + ....)3

= z.(1 + z + z2 + z3 +z4 + ....).(1 + z + z2 + z3 +z4 + ....).(1 + z + z2 + z3 +z4 + ....)

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

coefficient of z3 = coefficient of z2 from bracket terms

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

= 3C2 + 3C2

= 6

a0 = Total coefficient of z0 =  1 + 0 = 1

a3 = Total coefficent of z3 = 10 + 6

= 16

a3 - a0 = 16 - 1 = 15.

by
50 174 282

### 1 comment

$\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.
by
19 51 119

nice explanation, thanks.
Perfect!!

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

by
637 1330 876

Ans:15

by
2 8 34

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$

by
51 106 307