Recurrences and Generating Functions PYQs for GATE CS

Solve 3+ Recurrences and Generating Functions previous year 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 (3 Problems)

Question 1 · Engineering Mathematics · 2023 MCQ

The Lucas sequence

L_{n}

is defined by the recurrence relation:

L_{n} = L_{n - 1} + L_{n - 2}, for n \geq 3,

with

L_{1} = 1

and

L_{2} = 3

.

Which one of the options given is TRUE?

A.
$L_{n} = (\frac{1 + 5}{2})^{n} + (\frac{1 - 5}{2})^{n}$
B.
$L_{n} = (\frac{1 + 5}{2})^{n} - (\frac{1 - 5}{3})^{n}$
C.
$L_{n} = (\frac{1 + 5}{2})^{n} + (\frac{1 - 5}{3})^{n}$
D.
$L_{n} = (\frac{1 + 5}{2})^{n} - (\frac{1 - 5}{2})^{n}$

Correct Answer:

Step-by-Step Solution

Insight: This is a second-order linear homogeneous recurrence. The characteristic roots are the golden ratio and its conjugate, and the initial conditions perfectly match the sum of their powers.

Exam route: Write the characteristic equation $r^{2} - r - 1 = 0$ . The roots are $α = \frac{1 + 5}{2}$ and $β = \frac{1 - 5}{2}$ . Notice that $α + β = 1$ and $α^{2} + β^{2} = (α + β)^{2} - 2 α β = 1^{2} - 2 (- 1) = 3$ . These exactly match $L_{1} = 1$ and $L_{2} = 3$ . Thus, the coefficients are both 1.

Learning route:

Step 1: Identify the recurrence type. The relation $L_{n} = L_{n - 1} + L_{n - 2}$ is a linear homogeneous recurrence with constant coefficients.

Step 2: Form the characteristic equation. Rewrite as $L_{n} - L_{n - 1} - L_{n - 2} = 0$ . The characteristic equation is $r^{2} - r - 1 = 0$ .

Step 3: Find the roots. Using the quadratic formula, $r = \frac{1 \pm 1 - 4 ( 1 ) ( - 1 )}{2} = \frac{1 \pm 5}{2}$ . Let $α = \frac{1 + 5}{2}$ and $β = \frac{1 - 5}{2}$ .

Step 4: Write the general solution. Since the roots are distinct, $L_{n} = c_{1} α^{n} + c_{2} β^{n}$ .

Step 5: Apply initial conditions.

For $n = 1$ : $c_{1} α + c_{2} β = 1$ .

For $n = 2$ : $c_{1} α^{2} + c_{2} β^{2} = 3$ .

We know $α + β = 1$ (sum of roots) and $α β = - 1$ (product of roots).

Calculate $α^{2} + β^{2} = (α + β)^{2} - 2 α β = 1^{2} - 2 (- 1) = 3$ .

Comparing this with the $n = 2$ condition, we see that $c_{1} = 1$ and $c_{2} = 1$ is a valid solution.

Step 6: Verify with $n = 1$ . $1 \cdot α + 1 \cdot β = α + β = 1$ , which matches $L_{1} = 1$ .

Therefore, the closed form is $L_{n} = α^{n} + β^{n} = (\frac{1 + 5}{2})^{n} + (\frac{1 - 5}{2})^{n}$ .

Answer: A

Question 2 · Engineering Mathematics · 2022 MCQ

Which one of the following is the closed form for the generating function of the sequence ${a_{n}}_{n \geq 0}$ defined below?

$a_{n} = {n + 1, 1, n is odd otherwise$

A.
$\frac{x ( 1 + x ^{2} )}{( 1 - x ^{2} ) ^{2}} + \frac{1}{1 - x}$
B.
$\frac{x ( 3 - x ^{2} )}{( 1 - x ^{2} ) ^{2}} + \frac{1}{1 - x}$
C.
$\frac{2 x}{( 1 - x ^{2} ) ^{2}} + \frac{1}{1 - x}$
D.
$\frac{x}{( 1 - x ^{2} ) ^{2}} + \frac{1}{1 - x}$

Correct Answer:

Step-by-Step Solution

Key idea: This is a generating function problem where the sequence has different rules for even and odd indices. We split the generating function into two parts: one for even indices and one for odd indices.

Step 1: Write out the first few terms of the sequence.

$a_{0} = 1$ (even)

$a_{1} = 2$ (odd, $1 + 1$ )

$a_{2} = 1$ (even)

$a_{3} = 4$ (odd, $3 + 1$ )

$a_{4} = 1$ (even)

$a_{5} = 6$ (odd, $5 + 1$ )

The sequence is $1, 2, 1, 4, 1, 6, \dots$

Step 2: Split the generating function $A (x) = \sum_{n = 0}^{\infty} a_{n} x^{n}$ .

$A (x) = \sum_{k = 0}^{\infty} a_{2 k} x^{2 k} + \sum_{k = 0}^{\infty} a_{2 k + 1} x^{2 k + 1}$

Step 3: Evaluate the even part.

For even indices, $a_{2 k} = 1$ .

$\sum_{k = 0}^{\infty} 1 \cdot x^{2 k} = 1 + x^{2} + x^{4} + \dots = \frac{1}{1 - x ^{2}}$ .

Step 4: Evaluate the odd part.

For odd indices, $a_{2 k + 1} = (2 k + 1) + 1 = 2 k + 2$ .

$\sum_{k = 0}^{\infty} (2 k + 2) x^{2 k + 1} = x \sum_{k = 0}^{\infty} (2 k + 2) (x^{2})^{k} = 2 x \sum_{k = 0}^{\infty} (k + 1) (x^{2})^{k}$ .

We know the standard generating function $\sum_{k = 0}^{\infty} (k + 1) y^{k} = \frac{1}{( 1 - y ) ^{2}}$ .

Substitute $y = x^{2}$ :

$2 x \frac{1}{( 1 - x ^{2} ) ^{2}} = \frac{2 x}{( 1 - x ^{2} ) ^{2}}$ .

Step 5: Combine the parts.

$A (x) = \frac{1}{1 - x ^{2}} + \frac{2 x}{( 1 - x ^{2} ) ^{2}}$ .

Step 6: Match with the given options.

The options are in the form $\dots + \frac{1}{1 - x}$ .

We can rewrite $\frac{1}{1 - x ^{2}}$ as $\frac{1}{1 - x} - \frac{x}{1 - x ^{2}}$ .

So $A (x) = \frac{1}{1 - x} - \frac{x}{1 - x ^{2}} + \frac{2 x}{( 1 - x ^{2} ) ^{2}}$ .

Combine the terms with $(1 - x^{2})^{2}$ in the denominator:

$- \frac{x}{1 - x ^{2}} = - \frac{x ( 1 - x ^{2} )}{( 1 - x ^{2} ) ^{2}} = \frac{- x + x ^{3}}{( 1 - x ^{2} ) ^{2}}$ .

Add this to $\frac{2 x}{( 1 - x ^{2} ) ^{2}}$ :

$\frac{- x + x ^{3} + 2 x}{( 1 - x ^{2} ) ^{2}} = \frac{x + x ^{3}}{( 1 - x ^{2} ) ^{2}} = \frac{x ( 1 + x ^{2} )}{( 1 - x ^{2} ) ^{2}}$ .

Thus, $A (x) = \frac{x ( 1 + x ^{2} )}{( 1 - x ^{2} ) ^{2}} + \frac{1}{1 - x}$ .

This matches Option A.

Answer: A

Question 3 · Engineering Mathematics · 2022 MSQ

Consider the following recurrence:

$f (1) f (2 n) f (2 n + 1) = 1; = 2 f (n) - 1, for n \geq 1; = 2 f (n) + 1, for n \geq 1.$

Then, which of the following statements is/are TRUE?

A.
$f (2^{n} - 1) = 2^{n} - 1$
B.
$f (2^{n}) = 1$
C.
$f (5 \cdot 2^{n}) = 2^{n + 1} + 1$
D.
$f (2^{n} + 1) = 2^{n} + 1$

Correct Answer:

["A","B","C"]

Step-by-Step Solution

Insight: This is a piecewise divide-and-conquer recurrence. Instead of forcing a closed form immediately, compute the first few terms and use mathematical induction to verify each option.

Exam route: Compute $f (1)$ through $f (5)$ . Check each option for small $n$ . If it holds, prove by induction using the parity of the index (even vs. odd).

Learning route:

Step 1: Compute initial values.

$f (1) = 1$

$f (2) = 2 f (1) - 1 = 1$

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

$f (4) = 2 f (2) - 1 = 1$

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

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

$f (10) = 2 f (5) - 1 = 5$

Step 2: Check Option A: $f (2^{n} - 1) = 2^{n} - 1$ .

For $n = 1$ , $f (1) = 1$ . True.

Assume true for $n = k$ : $f (2^{k} - 1) = 2^{k} - 1$ .

For $n = k + 1$ , the index is $2^{k + 1} - 1 = 2 (2^{k} - 1) + 1$ , which is odd.

$f (2^{k + 1} - 1) = 2 f (2^{k} - 1) + 1 = 2 (2^{k} - 1) + 1 = 2^{k + 1} - 1$ .

By induction, Option A is TRUE.

Step 3: Check Option B: $f (2^{n}) = 1$ .

For $n = 1$ , $f (2) = 1$ . True.

Assume true for $n = k$ : $f (2^{k}) = 1$ .

For $n = k + 1$ , the index is $2^{k + 1} = 2 (2^{k})$ , which is even.

$f (2^{k + 1}) = 2 f (2^{k}) - 1 = 2 (1) - 1 = 1$ .

By induction, Option B is TRUE.

Step 4: Check Option C: $f (5 \cdot 2^{n}) = 2^{n + 1} + 1$ .

For $n = 0$ , $f (5) = 3$ . Formula gives $2^{1} + 1 = 3$ . True.

Assume true for $n = k$ : $f (5 \cdot 2^{k}) = 2^{k + 1} + 1$ .

For $n = k + 1$ , the index is $5 \cdot 2^{k + 1} = 2 (5 \cdot 2^{k})$ , which is even.

$f (5 \cdot 2^{k + 1}) = 2 f (5 \cdot 2^{k}) - 1 = 2 (2^{k + 1} + 1) - 1 = 2^{k + 2} + 1$ .

By induction, Option C is TRUE.

Step 5: Check Option D: $f (2^{n} + 1) = 2^{n} + 1$ .

For $n = 1$ , $f (3) = 3$ . Formula gives $2^{1} + 1 = 3$ . True.

For $n = 2$ , $f (5) = 3$ . Formula gives $2^{2} + 1 = 5$ .

Since $3 \neq = 5$ , Option D is FALSE.

Answer: A, B, C

Try a question

Login to view the complete previous-year 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 PYQs 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 (3 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More previous year questions (pyqs) in this unit