chapter

Recurrences and Generating Functions Notes for GATE CS

Recurrences and Generating Functions notes for GATE CS: 29 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

recurrences and generating functions notes

Chapter Roadmap: Recurrences and Generating Functions

.smart-card { font-family: system-ui, sans-serif; padding: 1.5rem; border-radius: 12px; background: var(--color-bg); color: var(--color-text); border: 1px solid var(--color-border); } .roadmap-header { margin-bottom: 1.5rem; border-bottom: 1px solid var(--color-border); padding-bottom: 1rem; } .roadmap-title { font-size: 1.4rem; font-weight: 700; color: var(--color-primary); margin: 0; } .timeline { position: relative; padding-left: 1.5rem; } .timeline::before { content: ''; position: absolute; left: 0.4rem; top: 0; bottom: 0; width: 2px; background: var(--color-muted); opacity: 0.3; } .milestone { position: relative; margin-bottom: 1.2rem; } .milestone::before { content: ''; position: absolute; left: -1.55rem; top: 0.3rem; width: 10px; height: 10px; border-radius: 50%; background: var(--color-primary); border: 2px solid var(--color-bg); } .milestone.active::before { background: var(--color-primary); box-shadow: 0 0 0 2px color-mix(in srgb, var(--color-primary) 30%, transparent); } .ms-title { font-weight: 600; font-size: 1rem; margin-bottom: 0.2rem; } .ms-desc { font-size: 0.9rem; color: var(--color-muted); line-height: 1.4; } .goal-box { margin-top: 1.5rem; padding: 1rem; background: color-mix(in srgb, var(--color-primary) 10%, transparent); border-radius: 8px; font-size: 0.9rem; font-style: italic; } Chapter Journey 1. Generating Functions for Sequences Algebraic representation, standard transforms, and coefficient extraction. 2. Linear Recurrences & Characteristic Roots Solving constant-coefficient linear difference equations and handling repeated roots. 3. Binary & Divide-and-Conquer Recurrences Master theorem applications and algorithmic time complexity analysis. Goal: Master the translation between discrete sequences and continuous algebraic functions to solve complex exam problems efficiently.

The Core Intuition: What is a Generating Function?

.smart-card { font-family: system-ui, sans-serif; padding: 1.5rem; border-radius: 12px; background: var(--color-bg); color: var(--color-text); border: 1px solid var(--color-border); } h3 { color: var(--color-primary); margin-top: 0; } .formula-box { background: color-mix(in srgb, var(--color-text) 5%, transparent); padding: 1rem; border-radius: 8px; text-align: center; margin: 1rem 0; font-size: 1.1rem; } .benefit-list { list-style: none; padding: 0; } .benefit-list li { margin-bottom: 0.8rem; padding-left: 1.2rem; position: relative; } .benefit-list li::before { content: '→'; position: absolute; left: 0; color: var(--color-primary); } .analogy { margin-top: 1.5rem; font-style: italic; color: var(--color-muted); border-left: 3px solid var(--color-primary); padding-left: 1rem; } The Core Idea A sequence is just a list of numbers: A Generating Function packs this entire infinite list into a single algebraic object (a formal power series): Why do we do this? Algebraic Power: Add, multiply, differentiate, and integrate to perform complex operations on the sequence. Closed Forms: Compress an infinite series into a simple fraction (like ). Extraction: Use algebraic techniques to find a direct formula for the -th term, . Think of it as a data compression algorithm for mathematics.

Operations on Generating Functions

.smart-card { font-family: system-ui, sans-serif; padding: 1.5rem; border-radius: 12px; background: var(--color-bg); color: var(--color-text); border: 1px solid var(--color-border); } h3 { color: var(--color-primary); margin-top: 0; } .op-block { margin-bottom: 1.2rem; padding-bottom: 1.2rem; border-bottom: 1px dashed var(--color-border); } .op-block:last-child { border-bottom: none; } .op-title { font-weight: 700; margin-bottom: 0.5rem; display: block; } .math-display { background: color-mix(in srgb, var(--color-text) 5%, transparent); padding: 0.8rem; border-radius: 6px; margin: 0.5rem 0; overflow-x: auto; } .effect { font-size: 0.9rem; color: var(--color-muted); font-style: italic; } Algebraic Operations Let A (x) = \sum_{n = 0}^{\infty} a_{n} x^{n} be the GF for sequence {a_{n}} . 1. Shifting Right (Delay) x A (x) = n = 1 \sum \infty a_{n - 1} x^{n} Effect: Sequence becomes 0, a_{0}, a_{1}, a_{2}, \dots 2. Shifting Left (Advance) \frac{A ( x ) - a _{0}}{x} = n = 0 \sum \infty a_{n + 1} x^{n} Effect: Sequence becomes a_{1}, a_{2}, a_{3}, \dots 3. Differentiation (Multiply by index) x A^{'} (x) = n = 0 \sum \infty n a_{n} x^{n} Effect: Sequence becomes 0, a_{1}, 2 a_{2}, 3 a_{3}, \dots

26 more cards in this chapter

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

Level 1: Warm-up

Consider the recurrence a_{n} = 5 a_{n - 1} - 6 a_{n - 2} . Which of the following statements about its characteristic equation is TRUE?

Question 2

Level 1: Warm-up

The generating function for a sequence is A (x) = \frac{1}{1 - 3 x} . What is the maximum value of n for which the coefficient of x^{n} is strictly less than 100?

Question 3

Level 1: Warm-up

Assertion (A): The general solution to the recurrence a_{n} = 4 a_{n - 1} - 3 a_{n - 2} is a_{n} = α_{1} 3^{n} + α_{2} 1 . Reason (R): The characteristic roots of the recurrence are 3 and 1 .

Question 4

Level 1: Warm-up

For the divide-and-conquer recurrence T (n) = 8 T (n /2) + n^{k}, what is the maximum integer value of k for which the Master Theorem yields T (n) = Θ (n^{3}) ?

Question 5

Level 1: Warm-up

Consider the recurrence defined by: f (1) = 1 f (2 n) = 2 f (n) f (2 n + 1) = 2 f (n) + 1 Assertion (A): The value of f (7) is 7. Reason (R): f (7) = 2 f (3) + 1 = 2 (2 f (1) + 1) + 1 = 7 .

Question 6

Level 1: Warm-up

Let A (x) = \frac{1}{1 - x} be the generating function for the sequence a_{n} = 1 . We form a new generating function B (x) = x^{3} A (x) . What is the minimum number of leading zero coefficients in the sequence corresponding to B (x) ?

Question 7

Level 1: Warm-up

Consider the recurrence relation for Binary Search: T (n) = T (n /2) + Θ (1) . Which of the following bounds is TRUE for the solution of this recurrence?

Question 8

Level 1: Warm-up

A generating function packs the sequence a_{n} into A (x) = \sum_{n = 0}^{\infty} a_{n} x^{n} . If the sequence is defined by a_{n} = 2^{n}, what is the value of the coefficient of x^{3} in A (x) ?

Question 9

Level 1: Warm-up

Which of the following recurrence relations is a linear homogeneous recurrence with constant coefficients?

Question 10

Level 1: Warm-up

For the Merge Sort algorithm, the recurrence relation is T (n) = 2 T (n /2) + Θ (n) . What is the minimum depth of the recursion tree when the input size is n = 32 ?

Free preview ends here

Login to view the complete notes

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Recurrences and Generating Functions Notes for GATE CS

Recurrences and Generating Functions notes for GATE CS: 29 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Chapter Roadmap: Recurrences and Generating Functions

Chapter Journey

1. Generating Functions for Sequences

Algebraic representation, standard transforms, and coefficient extraction.

2. Linear Recurrences & Characteristic Roots

Solving constant-coefficient linear difference equations and handling repeated roots.

3. Binary & Divide-and-Conquer Recurrences

Master theorem applications and algorithmic time complexity analysis.

Goal: Master the translation between discrete sequences and continuous algebraic functions to solve complex exam problems efficiently.

The Core Intuition: What is a Generating Function?

The Core Idea

A sequence is just a list of numbers: $a_{0}, a_{1}, a_{2}, a_{3}, \dots$

A Generating Function packs this entire infinite list into a single algebraic object (a formal power series):

A (x) = a_{0} + a_{1} x + a_{2} x^{2} + a_{3} x^{3} + \dots = n = 0 \sum \infty a_{n} x^{n}

Why do we do this?

Algebraic Power: Add, multiply, differentiate, and integrate to perform complex operations on the sequence.
Closed Forms: Compress an infinite series into a simple fraction (like $\frac{1}{1 - x}$ ).
Extraction: Use algebraic techniques to find a direct formula for the $n$ -th term, $a_{n}$ .

Think of it as a data compression algorithm for mathematics.

Operations on Generating Functions

Algebraic Operations

Let $A (x) = \sum_{n = 0}^{\infty} a_{n} x^{n}$ be the GF for sequence ${a_{n}}$ .

1. Shifting Right (Delay)

x A (x) = n = 1 \sum \infty a_{n - 1} x^{n}

Effect: Sequence becomes

0, a_{0}, a_{1}, a_{2}, \dots

2. Shifting Left (Advance)

\frac{A ( x ) - a _{0}}{x} = n = 0 \sum \infty a_{n + 1} x^{n}

Effect: Sequence becomes

a_{1}, a_{2}, a_{3}, \dots

3. Differentiation (Multiply by index)

x A^{'} (x) = n = 0 \sum \infty n a_{n} x^{n}

Effect: Sequence becomes

0, a_{1}, 2 a_{2}, 3 a_{3}, \dots

Multiplication and Convolution

The Cauchy Product (Convolution)

If $A (x) = \sum a_{n} x^{n}$ and $B (x) = \sum b_{n} x^{n}$ , then their product $C (x) = A (x) B (x) = \sum c_{n} x^{n}$ has coefficients:

c_{n} = k = 0 \sum n a_{k} b_{n - k}

Why this matters:

Combinatorics: If $a_{k}$ is ways to choose $k$ items of type A, and $b_{n - k}$ is ways to choose remaining items of type B, then $c_{n}$ is total ways to choose $n$ items.
Recurrences: Convolution appears in non-linear recurrences and nested loop analysis.

Recurrences and Generating Functions: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Engineering Mathematics MCQ

Consider the recurrence $a_{n} = 5 a_{n - 1} - 6 a_{n - 2}$ . Which of the following statements about its characteristic equation is TRUE?

A.
The characteristic equation is $r^{2} - 5 r - 6 = 0$ .
B.
The characteristic roots are $2$ and $3$ .
C.
The characteristic equation is $r^{2} + 5 r + 6 = 0$ .
D.
The characteristic roots are $- 2$ and $- 3$ .

Correct Answer:

Step-by-Step Solution

Key idea: For a recurrence $a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2}$ , the characteristic equation is $r^{2} - c_{1} r - c_{2} = 0$ .

Step 1: Identify coefficients from $a_{n} = 5 a_{n - 1} - 6 a_{n - 2}$ . Here $c_{1} = 5$ and $c_{2} = - 6$ .

Step 2: Form the characteristic equation: $r^{2} - 5 r - (- 6) = 0 ⟹ r^{2} - 5 r + 6 = 0$ .

Step 3: Solve the quadratic equation. Factor it: $(r - 2) (r - 3) = 0$ .

Step 4: The roots are $r = 2$ and $r = 3$ .

Answer: The characteristic roots are 2 and 3.

Question 2 · Engineering Mathematics MCQ

The generating function for a sequence is $A (x) = \frac{1}{1 - 3 x}$ . What is the maximum value of $n$ for which the coefficient of $x^{n}$ is strictly less than 100?

A.
3
B.
5
C.
4
D.
6

Correct Answer:

Step-by-Step Solution

Key idea: The generating function $\frac{1}{1 - r x}$ corresponds to the geometric sequence $a_{n} = r^{n}$ . Here, $r = 3$ , so $a_{n} = 3^{n}$ .

Step 1: Identify the sequence formula. $A (x) = \frac{1}{1 - 3 x} ⟹ a_{n} = 3^{n}$ .

Step 2: We need the maximum $n$ such that $3^{n} < 100$ .

Step 3: Test powers of 3:

$3^{1} = 3$

$3^{2} = 9$

$3^{3} = 27$

$3^{4} = 81$

$3^{5} = 243$

Step 4: Since $3^{4} = 81 < 100$ and $3^{5} = 243 > 100$ , the maximum $n$ is 4.

Answer: 4

Question 3 · Engineering Mathematics MCQ

Assertion (A): The general solution to the recurrence $a_{n} = 4 a_{n - 1} - 3 a_{n - 2}$ is $a_{n} = α_{1} 3^{n} + α_{2} 1$ .

Reason (R): The characteristic roots of the recurrence are $3$ and $1$ .

A.
Both A and R are true and R is the correct explanation of A.
B.
Both A and R are true but R is not the correct explanation of A.
C.
A is false but R is true.
D.
A is true but R is false.

Correct Answer:

Step-by-Step Solution

Key idea: For distinct characteristic roots $r_{1}, r_{2}$ , the general solution is $a_{n} = α_{1} r_{1}^{n} + α_{2} r_{2}^{n}$ . Both roots must be raised to the power $n$ .

Step 1: Evaluate Reason (R). The recurrence is $a_{n} - 4 a_{n - 1} + 3 a_{n - 2} = 0$ .

Step 2: Characteristic equation: $r^{2} - 4 r + 3 = 0 ⟹ (r - 3) (r - 1) = 0$ . Roots are 3 and 1. So R is TRUE.

Step 3: Evaluate Assertion (A). The general solution must be $a_{n} = α_{1} 3^{n} + α_{2} 1^{n}$ .

Step 4: The assertion writes the second term as $α_{2} 1$ , omitting the exponent $n$ . This is mathematically incorrect for a sequence solution. So A is FALSE.

Answer: A is false but R is true.

Question 4 · Engineering Mathematics MCQ

For the divide-and-conquer recurrence $T (n) = 8 T (n /2) + n^{k}$ , what is the maximum integer value of $k$ for which the Master Theorem yields $T (n) = Θ (n^{3})$ ?

A.
1
B.
2
C.
3
D.
4

Correct Answer:

Step-by-Step Solution

Key idea: The Master Theorem compares $f (n)$ against $n^{E}$ where $E = lo g_{b} a$ . Case 1 applies when $f (n)$ grows strictly slower than $n^{E}$ .

Step 1: Identify parameters from $T (n) = 8 T (n /2) + n^{k}$ . Here $a = 8$ , $b = 2$ , and $f (n) = n^{k}$ .

Step 2: Compute the critical exponent $E = lo g_{2} 8 = 3$ .

Step 3: We want $T (n) = Θ (n^{3}) = Θ (n^{E})$ . This corresponds to Case 1 (Leaves dominate).

Step 4: Case 1 requires $f (n) = O (n^{E - ϵ})$ for some $ϵ > 0$ . This means $n^{k}$ must grow strictly slower than $n^{3}$ , so $k < 3$ .

Step 5: The maximum integer value of $k$ strictly less than 3 is 2.

Answer: 2

Question 5 · Engineering Mathematics MCQ

Consider the recurrence defined by:

$f (1) = 1$

$f (2 n) = 2 f (n)$

$f (2 n + 1) = 2 f (n) + 1$

Assertion (A): The value of $f (7)$ is 7.

Reason (R): $f (7) = 2 f (3) + 1 = 2 (2 f (1) + 1) + 1 = 7$ .

A.
Both A and R are true and R is the correct explanation of A.
B.
Both A and R are true but R is not the correct explanation of A.
C.
A is true but R is false.
D.
A is false but R is true.

Correct Answer:

Step-by-Step Solution

Key idea: To evaluate piecewise even-odd recurrences, apply the correct rule based on the parity of the index, working down to the base case.

Step 1: Evaluate Assertion (A) by computing $f (7)$ .

Since 7 is odd, use $f (2 n + 1) = 2 f (n) + 1$ with $2 n + 1 = 7 ⟹ n = 3$ .

$f (7) = 2 f (3) + 1$ .

Step 2: Compute $f (3)$ . Since 3 is odd, use the odd rule with $2 n + 1 = 3 ⟹ n = 1$ .

$f (3) = 2 f (1) + 1 = 2 (1) + 1 = 3$ .

Step 3: Substitute back into $f (7)$ .

$f (7) = 2 (3) + 1 = 7$ . Assertion (A) is TRUE.

Step 4: Evaluate Reason (R).

R states: $f (7) = 2 f (3) + 1 = 2 (2 f (1) + 1) + 1 = 7$ .

This matches our exact derivation step-by-step. Reason (R) is TRUE and correctly explains (A).

Answer: Both A and R are true and R is the correct explanation of A.

Question 6 · Engineering Mathematics MCQ

Let $A (x) = \frac{1}{1 - x}$ be the generating function for the sequence $a_{n} = 1$ . We form a new generating function $B (x) = x^{3} A (x)$ . What is the minimum number of leading zero coefficients in the sequence corresponding to $B (x)$ ?

A.
3
B.
2
C.
4
D.
5

Correct Answer:

Step-by-Step Solution

Key idea: Multiplying a generating function by $x^{k}$ shifts the entire sequence to the right by $k$ positions, inserting $k$ zeros at the beginning.

Step 1: Identify the shift operation. $B (x) = x^{3} A (x)$ means the sequence is shifted right by 3.

Step 2: The original sequence is $1, 1, 1, 1, \dots$ (starting at $n = 0$ ).

Step 3: Shifting right by 3 inserts three zeros at indices $n = 0, 1, 2$ .

Step 4: The new sequence is $0, 0, 0, 1, 1, \dots$ .

Step 5: The number of leading zero coefficients is exactly 3.

Answer: 3

Question 7 · Engineering Mathematics MCQ

Consider the recurrence relation for Binary Search: $T (n) = T (n /2) + Θ (1)$ . Which of the following bounds is TRUE for the solution of this recurrence?

A.
$T (n) = Θ (n)$
B.
$T (n) = Θ (lo g n)$
C.
$T (n) = Θ (n lo g n)$
D.
$T (n) = Θ (1)$

Correct Answer:

Step-by-Step Solution

Key idea: The Master Theorem solves $T (n) = a T (n / b) + f (n)$ by comparing $f (n)$ to $n^{E}$ where $E = lo g_{b} a$ .

Step 1: Identify parameters from $T (n) = T (n /2) + Θ (1)$ . Here $a = 1$ , $b = 2$ , and $f (n) = Θ (1)$ .

Step 2: Compute the critical exponent $E = lo g_{2} 1 = 0$ .

Step 3: Compare $f (n)$ with $n^{E}$ . We have $f (n) = Θ (1)$ and $n^{E} = n^{0} = 1$ .

Step 4: Since $f (n) = Θ (n^{E})$ , this falls under Case 2 of the Master Theorem.

Step 5: Case 2 yields $T (n) = Θ (n^{E} lo g n) = Θ (1 \cdot lo g n) = Θ (lo g n)$ .

Answer: $T (n) = Θ (lo g n)$

Question 8 · Engineering Mathematics MCQ

A generating function packs the sequence $a_{n}$ into $A (x) = \sum_{n = 0}^{\infty} a_{n} x^{n}$ . If the sequence is defined by $a_{n} = 2^{n}$ , what is the value of the coefficient of $x^{3}$ in $A (x)$ ?

A.
8
B.
6
C.
9
D.
16

Correct Answer:

Step-by-Step Solution

Key idea: The coefficient of $x^{n}$ in the generating function $A (x)$ is exactly the $n$ -th term of the sequence $a_{n}$ .

Step 1: Identify the sequence formula from the problem statement, which is $a_{n} = 2^{n}$ .

Step 2: We need the coefficient of $x^{3}$ , which corresponds to the index $n = 3$ .

Step 3: Substitute $n = 3$ into the sequence formula: $a_{3} = 2^{3} = 8$ .

Answer: 8

Question 9 · Engineering Mathematics MCQ

Which of the following recurrence relations is a linear homogeneous recurrence with constant coefficients?

A.
$a_{n} = 3 a_{n - 1} + 2$
B.
$a_{n} = n a_{n - 1} - a_{n - 2}$
C.
$a_{n} = 4 a_{n - 1} - 3 a_{n - 2}$
D.
$a_{n} = a_{n - 1}^{2} + 2 a_{n - 2}$

Correct Answer:

Step-by-Step Solution

Key idea: A linear homogeneous recurrence with constant coefficients must have previous terms multiplied only by fixed constants, with no standalone terms and no non-linear operations.

Step 1: Check option A: $a_{n} = 3 a_{n - 1} + 2$ . The "+ 2" makes it non-homogeneous.

Step 2: Check option B: $a_{n} = n a_{n - 1} - a_{n - 2}$ . The multiplier " $n$ " means it does not have constant coefficients.

Step 3: Check option C: $a_{n} = 4 a_{n - 1} - 3 a_{n - 2}$ . The terms are linear, coefficients (4 and -3) are constant, and there is no standalone term. This fits all criteria.

Step 4: Check option D: $a_{n} = a_{n - 1}^{2} + 2 a_{n - 2}$ . The squared term makes it non-linear.

Answer: $a_{n} = 4 a_{n - 1} - 3 a_{n - 2}$

Question 10 · Engineering Mathematics MCQ

For the Merge Sort algorithm, the recurrence relation is $T (n) = 2 T (n /2) + Θ (n)$ . What is the minimum depth of the recursion tree when the input size is $n = 32$ ?

A.
4
B.
5
C.
16
D.
32

Correct Answer:

Step-by-Step Solution

Key idea: In a divide-and-conquer recurrence $T (n) = a T (n / b)$ , the problem size is divided by $b$ at each level. The depth of the recursion tree is the number of times you can divide $n$ by $b$ until you reach the base case (size 1).

Step 1: Identify the division factor $b$ from the recurrence. Here, $b = 2$ .

Step 2: The depth $d$ satisfies $n / b^{d} = 1$ , which means $b^{d} = n$ .

Step 3: Substitute $n = 32$ and $b = 2$ : $2^{d} = 32$ .

Step 4: Solve for $d$ : $d = lo g_{2} 32 = 5$ .

Answer: 5

recurrences and generating functions notes

Chapter Roadmap: Recurrences and Generating Functions

Chapter Journey

The Core Intuition: What is a Generating Function?

The Core Idea

Operations on Generating Functions

Algebraic Operations

Try a question

Login to view the complete notes

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Recurrences and Generating Functions Notes for GATE CS

Chapter Roadmap: Recurrences and Generating Functions

Chapter Journey

The Core Intuition: What is a Generating Function?

The Core Idea

Operations on Generating Functions

Algebraic Operations

Multiplication and Convolution

The Cauchy Product (Convolution)

Recurrences and Generating Functions: Solved Questions with Step-by-Step Explanations (10 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More notes in this unit