Recurrences and Generating Functions Practice Questions for GATE CS

Solve 48+ Recurrences and Generating Functions practice questions for GATE CS with answers and detailed solutions. Free sample questions below.

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.

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

Try a question

Login to view the complete practice questions and solutions

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 Practice Questions for GATE CS

Chapter Roadmap: Recurrences and Generating Functions

Chapter Journey

The Core Intuition: What is a Generating Function?

The Core Idea

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 practice questions in this unit