The Gateway to Computer Science Excellence
+38 votes
7k 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 ___________ .
in Combinatory by Veteran
retagged by | 7k views
0

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

0
can you please elaborate this sir ?

8 Answers

+75 votes
Best answer
$\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 Boss
selected by
+1
(1−z)−3=1+(3c1)z+(4c2)z2+(5c3)z3+…∞

from where this formula come  ?
0
follow rosen .....
0

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?

0
plz suggest some good resource to read this topic
+2

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

+13

Generating functions 

+18 votes

Ans : 15

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

(x+1)^(-n)=1-nx+1/2n(n+1)x^2-1/6n(n+1)(n+2)x^3+....

this is the correct formula.

+9 votes

yes 15 is correct ans 

by Loyal
+9 votes

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 Loyal
edited by
0
Best answer, thanks
+6 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.
by Boss
0
nice explanation, thanks.
0
Perfect!!
+4 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.$

by Veteran
edited by
+2 votes

Ans:15

by Active
0 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$

by Boss
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,223 questions
59,818 answers
201,021 comments
118,091 users