Ordinary generating functions and coefficients
Objectives and prerequisites
Encode a sequence as a formal power series, use sums/products/shifts, translate counting restrictions into factors, extract coefficients, and turn a linear recurrence into a rational generating function. Prerequisites: counting principles, binomial coefficients and recurrence relations. Our focus is ordinary generating functions (OGFs); exponential generating functions, analytic convergence and asymptotic singularity methods require separate treatment.
All sequences start at index 0. We work with formal power series over the rational or real numbers. Here x is a bookkeeping symbol; we do not need an infinite numerical sum to converge. A rational denominator with a nonzero constant term has a formal series expansion around x=0. Substituting a number such as x=1 into an infinite formal identity requires additional convergence reasoning and is not automatic.
1. A coefficient records one sequence term
For a₀,a₁,a₂,… define A(x)=Σₙ≥₀aₙxⁿ=a₀+a₁x+a₂x²+… . The notation [xⁿ]A(x) means “the coefficient of xⁿ,” so it equals aₙ. It is not the value obtained by replacing x with n.
The sequence 1,1,1,… has OGF 1+x+x²+…=1/(1−x). Multiplying by 1−x cancels every positive-degree term, leaving 1; this verifies the identity coefficient by coefficient. More generally, 1,c,c²,… has OGF 1/(1−cx).
The sequence 0,1,1,1,… has OGF x/(1−x), not 1/(1−x), because its constant coefficient is 0. The sequence 1,0,1,0,1,… has OGF 1/(1−x²). Always inspect the first few coefficients as an index check.
2. Addition and shifts
If A encodes aₙ and B encodes bₙ, then αA+βB encodes αaₙ+βbₙ. Multiplication by xᵏ, for a nonnegative integer k, inserts k leading zeros: [xⁿ]xᵏA(x)=aₙ₋ₖ for n≥k and 0 for n<k. It shifts coefficients; it does not multiply the nth coefficient by nᵏ.
Removing an initial term requires care. Σₙ≥1aₙxⁿ=A(x)−a₀. Also Σₙ≥1aₙ₋₁xⁿ=xA(x). For a sum beginning at n=2, Σₙ≥2aₙ₋₁xⁿ=x(A(x)−a₀), while Σₙ≥2aₙ₋₂xⁿ=x²A(x). These lower limits produce the numerators in recurrence solutions.
For example, if A=1+3x+5x²+…, then x²A= x²+3x³+5x⁴+… . Its x⁴ coefficient is a₂=5, not a₄. An off-by-one error can survive extensive algebra, so write two or three terms before simplifying.
3. Multiplication is convolution
The coefficient of xⁿ in A(x)B(x) is Σₖ₌₀ⁿ aₖbₙ₋ₖ. To obtain total exponent n, choose xᵏ from the first factor and xⁿ⁻ᵏ from the second, then sum all possible splits. This is convolution, not termwise multiplication aₙbₙ.
Worked finite example: (1+2x)(1+x+x²)=1+3x+3x²+2x³. The x² coefficient is 1·1+2·1=3. A termwise product would incorrectly give 0 because the first polynomial has no x² term.
Squaring 1/(1−x) counts ordered nonnegative pairs (u,v) by u+v. For total n, the pairs are (0,n),(1,n−1),…,(n,0), so [xⁿ](1−x)⁻²=n+1. Thus 1/(1−x)² encodes 1,2,3,…, while x/(1−x)² encodes 0,1,2,… . The extra x is an indexing difference, not a cosmetic change.
4. Build one factor for each independent choice
If a quantity u may be any nonnegative integer, its factor is 1+x+x²+… . If 0≤u≤m, use 1+x+…+xᵐ. If u must be even, use 1+x²+x⁴+… . If u≥r, use xʳ/(1−x). The exponent records the chosen quantity; the coefficient records how many distinguishable choices give that quantity.
Multiply factors for independent labeled variables. For u+v=4 with 0≤u≤2 and v≥0, use (1+x+x²)/(1−x). The x⁴ coefficient is 3, corresponding to (0,4),(1,3),(2,2). Do not divide by 2!: u and v are named variables, so swapping their values can produce a different solution.
If two distinct item types each have the same allowed weight 1, their alternatives contribute 2x, not x. A generating function models the problem's actual distinguishability; algebra cannot repair a missing interpretation of what one outcome means.
5. Nonnegative solutions and bounded solutions
For k labeled nonnegative integer variables summing to n, the OGF is (1−x)⁻ᵏ. The coefficient is C(n+k−1,k−1), for integers k≥1 and n≥0. One counting proof arranges n identical stars and k−1 separators: the number of stars before, between and after separators gives the ordered variable values. Adjacent separators represent zero; no positivity assumption should be inserted.
For positive variables, first subtract 1 from each, or multiply by xᵏ. If u≥2, v≥1, w≥0 and u+v+w=7, remove the compulsory total 3. The remaining three nonnegative quantities sum to 4, giving C(6,2)=15 solutions. The OGF is x³/(1−x)³, whose x⁷ coefficient is the same.
Worked bounded example: 0≤u,v,w≤2 and u+v+w=4. The OGF is (1+x+x²)³=(1−x³)³/(1−x)³. For coefficient x⁴, only numerator terms 1−3x³ matter; higher terms have degree at least 6. Therefore the count is C(6,2)−3C(3,2)=15−9=6.
Check directly: permutations of (2,2,0) give 3 solutions and permutations of (2,1,1) give 3, totaling 6. In inclusion–exclusion language, 15 counts all nonnegative solutions; each of three variables violating the upper bound is at least 3, leaving total 1 and C(3,2)=3 solutions. Two violations would need total at least 6, impossible here.
6. Derive a recurrence's rational OGF
Let b₀=3,b₁=7 and bₙ=3bₙ₋₁−2bₙ₋₂ for n≥2. Write B(x)=Σₙ≥₀bₙxⁿ. Multiply the recurrence by xⁿ and sum only over n≥2:
B(x)−3−7x = 3x(B(x)−3)−2x²B(x).
Collecting terms gives (1−3x+2x²)B(x)=3−2x, so
B(x)=(3−2x)/[(1−x)(1−2x)] = −1/(1−x)+4/(1−2x).
The last equality is partial fractions; combining its right-hand side gives numerator −(1−2x)+4(1−x)=3−2x. Extracting coefficients yields bₙ=−1+4·2ⁿ. Check b₀=3,b₁=7 and b₂=15. The denominator describes the recurrence, but the initial values determine the numerator. Omitting them gives a different sequence.
7. Repeated factors and a forced recurrence
The coefficient identity [xⁿ](1−cx)⁻²=(n+1)cⁿ follows by replacing x with cx in the convolution result. Repeated denominator factors therefore produce polynomial factors in n, matching repeated-root behavior in recurrence solutions.
Let e₀=1 and eₙ=2eₙ₋₁+2ⁿ for n≥1. With E(x)=Σₙ≥₀eₙxⁿ, summing gives
E(x)−1=2xE(x)+2x/(1−2x).
Hence (1−2x)E(x)=1+2x/(1−2x)=1/(1−2x), and E(x)=1/(1−2x)². Therefore eₙ=(n+1)2ⁿ, including the correct initial value. This independently matches the earlier divide-by-2ⁿ method.
8. Counting recurrence and index audit
For binary strings with no consecutive 1s, f₀=1,f₁=2 and fₙ=fₙ₋₁+fₙ₋₂ for n≥2. Summing gives F(x)−1−2x=x(F(x)−1)+x²F(x), so F(x)=(1+x)/(1−x−x²).
By contrast, the standard Fibonacci sequence F₀=0,F₁=1 has OGF x/(1−x−x²). The denominators agree but the numerators do not: they encode different initial values. The binary-string count starts 1,2,3,5,8,…, not 0,1,1,2,3,… . Do not identify sequences from the denominator alone.
Working checklist
Name the counted objects and index 0 term. Construct factors from allowed choices, not memorized appearances. For products, add exponents and sum all splits. For recurrence sums, preserve starting indices and subtract initial terms. Extract the requested coefficient, then check by a small enumeration or direct recurrence. Report an exact coefficient, not the whole generating function, when a numerical count is requested.
Original practice: six single-correct MCQs
Original questions, not previous-year questions. Choose exactly one option. Keep all stated index, domain and graph conventions.
C01. What is [x⁴] x²/(1−x)²?
A. 3 B. 5 C. 4 D. 10
Answer: A
A: The x² factor shifts the request to [x²](1−x)⁻²=2+1=3.
B: 5 is [x⁴](1−x)⁻² without the leading x² shift.
C: This treats the exponent as the coefficient and misses both the shift and n+1 rule.
D: 10 is not the coefficient of the shifted series x²+2x³+3x⁴+… .
C02. What is the coefficient of x² in (1+2x)(1+x+x²)?
A. 2 B. 0 C. 3 D. 1
Answer: C
A: This counts only the product (2x)·x and misses 1·x².
B: Coefficient multiplication is convolution, not the product of the two x² coefficients.
C: The contributing terms are 1·x² and (2x)·x, giving 1+2=3.
D: This counts only 1·x² and misses (2x)·x.
C03. How many labeled integer triples (u,v,w) satisfy u+v+w=4 and 0≤u,v,w≤2?
A. 15 B. 9 C. 3 D. 6
Answer: D
A: 15 counts all nonnegative triples without the upper bounds.
B: 9 counts the invalid triples where one coordinate is at least 3, not the valid ones.
C: There are three permutations of (2,2,0) but also three of (2,1,1).
D: The coefficient of x⁴ in (1+x+x²)³ is 15−3·3=6; direct disjoint types give 3+3.
C04. How many labeled integer solutions have u+v+w=7 with u≥2,v≥1,w≥0?
A. 21 B. 15 C. 10 D. 6
Answer: B
A: The mandatory lower bounds total 3, leaving 4, not 5.
B: Set u′=u−2 and v′=v−1; three nonnegative variables sum to 4, giving C(6,2)=15.
C: This incorrectly requires a positive value for another variable and removes allowed zero cases.
D: The upper bound of 2 from the previous problem is not present here; it must not be carried over.
C05. For b₀=3,b₁=7 and bₙ=3bₙ₋₁−2bₙ₋₂ (n≥2), which numerator N(x) gives B(x)=N(x)/(1−3x+2x²)?
A. 3 B. 3+7x C. 3−2x D. 7−3x
Answer: C
A: It would give coefficient b₁=9, failing the required initial value 7.
B: This does not subtract the 3xb₀ contribution arising when the shifted sum starts at n=2.
C: B−3−7x=3x(B−3)−2x²B gives numerator 3+(7−9)x=3−2x.
D: Its constant coefficient would make b₀=7 instead of 3.
C06. What is the OGF for the count fₙ of length-n binary strings with no consecutive 1s, including f₀=1?
A. (1+x)/(1−x−x²) B. x/(1−x−x²) C. 1/(1−x−x²) D. (1−x)/(1−x−x²)
Answer: A
A: The initial values f₀=1,f₁=2 give numerator f₀+(f₁−f₀)x=1+x.
B: This is the standard Fibonacci OGF with initial values 0,1, not the required 1,2.
C: Its first two coefficients are 1,1, so the length-1 count is wrong.
D: Its first two coefficients are 1,0, again failing f₁=2.
Sources and scope
This original lesson develops a specified Discrete Mathematics topic from Section 1 of the official GATE 2027 CS syllabus. It is not a declaration that the whole subject or syllabus is complete. The syllabus confirms relevance; the institutional course chapter is a further-study reference. Worked examples, wording and practice are original.
Sources opened and checked 2026-10-14.
Sign in to keep your progress. Sign in