Skip to content
GATETECH
Official PYQ · 2017Set 2 · Q47Combinatorics: Counting, Recurrence Relations, Generating FunctionsNAT1 mark

GATE CS 2017 Set 2 Q47 — Combinatorics: Counting, Recurrence Relations, Generating Functions

Explain with AI
If the ordinary generating function of a sequence {an}n=0∞\left \{a_n\right \}_{n=0}^\infty  is 1+z(1−z)3\large \frac{1+z}{(1-z)^3}, then a3−a0a_3-a_0 is equal to ___________ .
View worked solution

Answer: 15

We are given the ordinary generating function of the sequence {an}n=0∞\{a_n\}_{n=0}^\infty:

G(z)=∑n=0∞anzn=1+z(1−z)3G(z) = \sum_{n=0}^\infty a_n z^n = \frac{1+z}{(1-z)^3}

Using the standard binomial expansion for negative integer exponents, we have:

1(1−z)3=∑n=0∞(n+22)zn\frac{1}{(1-z)^3} = \sum_{n=0}^\infty \binom{n+2}{2} z^n

Let's write down the first few terms of this series:

1(1−z)3=(22)+(32)z+(42)z2+(52)z3+…\frac{1}{(1-z)^3} = \binom{2}{2} + \binom{3}{2}z + \binom{4}{2}z^2 + \binom{5}{2}z^3 + \dots 1(1−z)3=1+3z+6z2+10z3+15z4+…\frac{1}{(1-z)^3} = 1 + 3z + 6z^2 + 10z^3 + 15z^4 + \dots

Now, multiply this series by (1+z)(1+z) to obtain G(z)G(z):

G(z)=(1+z)(1+3z+6z2+10z3+15z4+… )G(z) = (1+z) \left( 1 + 3z + 6z^2 + 10z^3 + 15z^4 + \dots \right) G(z)=(1+3z+6z2+10z3+… )+(z+3z2+6z3+10z4+… )G(z) = \left( 1 + 3z + 6z^2 + 10z^3 + \dots \right) + \left( z + 3z^2 + 6z^3 + 10z^4 + \dots \right)

Grouping the terms by powers of zz:

G(z)=1+(3+1)z+(6+3)z2+(10+6)z3+(15+10)z4+…G(z) = 1 + (3+1)z + (6+3)z^2 + (10+6)z^3 + (15+10)z^4 + \dots G(z)=1+4z+9z2+16z3+25z4+…G(z) = 1 + 4z + 9z^2 + 16z^3 + 25z^4 + \dots

Comparing this with G(z)=a0+a1z+a2z2+a3z3+…G(z) = a_0 + a_1 z + a_2 z^2 + a_3 z^3 + \dots, we get:

  • a0=1a_0 = 1
  • a3=16a_3 = 16

Therefore, the required value is:

a3−a0=16−1=15a_3 - a_0 = 16 - 1 = 15

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Combinatorics: Counting, Recurrence Relations, Generating Functions questions